[Closed] Smallest volume box to fit a shape?

Success!

The script has a bunch of steps and a LOT of arrays, but it works. If anyone wants to take a shot at improving it, please go ahead. I post the code in its entirety here:

polyArea = polyOp.getFaceArea $ 1
 vertCount = $.numVerts
 
 edgeArray		= #() -- array for start and end points of polygon edges
 iArray			= #() -- array for intersection points of polygon edges
 lineArray		= #() -- array for lines parallel with polygon edges
 sideArray		= #() -- array for lines overlapping polygon edges
 cornerArray	= #() -- array for viable corners for quads
 setArray		= #() -- array for sets of 4 points created from opposing corners
 areaArray		= #() -- array for areas of enclosing quadrangles
 
 -- modified from a function by prettyPixel (finds the closest passing point of two lines)
 fn lineLineIntersect pA pB pC pD =
 (
 	i1 = (pA + ((pB-pA) * ((dot (cross (pC-pA) (pD-pC)) (cross (pB-pA) (pD-pC) ) ) / ((length (cross (pB-pA) (pD-pC) ) )^2))) )
 	i2 = (pC + ((pD-pC) * ((dot (cross (pA-pC) (pB-pA)) (cross (pD-pC) (pB-pA) ) ) / ((length (cross (pD-pC) (pB-pA) ) )^2))) )
 	
 	((i1 + i2) / 2)
 )
 
 --remove concave vertices
 for i = vertCount to 1 by -1 do
 (
 	prevObj = $
 	theArea = polyOp.getFaceArea $ 1
 		
 	theHull = copy $
 	theHull.name = "Hull"
 	select theHull
 		
 	polyOp.setVertSelection $ #{i}
 	$.editablePoly.remove selLevel:#Vertex
 	newArea = polyOp.getFaceArea $ 1
 		
 	if newArea > theArea
 		then (delete prevObj; select theHull)
 		else (delete theHull;	select prevObj)
 )
 
 -- find the the start/end points for all edges
 for i = 1 to polyOp.getNumEdges $ do
 (
 	thePoints = polyOp.getVertsUsingEdge $ i as array
 	theStart	= polyOp.getVert $ thePoints[1]
 	theEnd		= polyOp.getVert $ thePoints[2]
 	theVector = normalize (theEnd - theStart)
 
 	append edgeArray #(theStart, theEnd, theVector)
 )
 
 -- find the points at which the edge lines intersect
 for i = 1 to edgeArray.count do
 (
 	for j = 1 to edgeArray.count where j > i do
 	(
 		append iArray (lineLineIntersect edgeArray[i][1] edgeArray[i][2] edgeArray[j][1] edgeArray [j][2])
 	)
 )
 
 -- create an array of the lines that match the rotation of the lines in edgeArray
 for i = 1 to iArray.count do
 (
 	for j = 1 to iArray.count where j > i do
 	(
 		n = normalize (iArray[j] - iArray[i])
 		
 		for k = 1 to edgeArray.count do
 		(
 			o = edgeArray[k][3]
 			if abs(n[1]) - abs(o[1]) < .00001 and abs(n[2]) - abs(o[2]) < .00001 and abs(n[3]) - abs(o[3]) < .00001 do
 			(
 				append lineArray #(iArray[i], iArray[j], k)
 			)
 		) -- end k loop
 	) -- end j loop
 ) -- end i loopd
 
 -- create an array of the lines that overlap polygon edges
 for theLine in lineArray do
 (
 	theLength = distance theLine[1] theLine[2]
 	e = theLine[3]
 	
 	d1 = distance edgeArray[e][1] theLine[1]
 	d2 = distance edgeArray[e][1] theLine[2] 
 	d3 = distance edgeArray[e][2] theLine[1] 
 	d4 = distance edgeArray[e][2] theLine[2] 
 
 	if d1 < theLength and d2 < theLength and d3 < theLength and d4 < theLength do append sideArray theLine
 )
 
 -- determine the sides for all viable corners
 for a = 1 to sideArray.count do
 (
 	-- find the angles of sides with shared corners
 	for b = (a + 1) to sideArray.count do
 	(
 		local pointA, pointB, pointC
 		
 		case of
 		(
 			(sideArray[b][1] == sideArray[a][1]): (pointA = sideArray[a][2]; pointB = sideArray[a][1]; pointC = sideArray[b][2])
 			(sideArray[b][2] == sideArray[a][1]): (pointA = sideArray[a][2]; pointB = sideArray[a][1]; pointC = sideArray[b][1])
 			(sideArray[b][1] == sideArray[a][2]): (pointA = sideArray[a][1]; pointB = sideArray[a][2]; pointC = sideArray[b][2])
 			(sideArray[b][2] == sideArray[a][2]): (pointA = sideArray[a][1]; pointB = sideArray[a][2]; pointC = sideArray[b][1])
 		)
 		
 		-- if the lines share a corner 
 		if pointC != undefined do
 		(
 			-- find the angle of the corner
 			theAngle = acos (dot (normalize (pointB - pointA)) (normalize (pointB - pointC)))
 			
 			--if the corner is not 0 or 180
 			if theAngle > 0 and theAngle < 180 do
 			(
 				append cornerArray #()
 				join cornerArray[cornerArray.count] #(pointA, pointB, pointC)
 			) -- end if (theAngle > 0)
 		) -- end if (pointC != undefined)
 	) -- end b loop
 ) -- end a loop
 
 -- find opposing corners to make quad sets
 for a = 1 to cornerArray.count do
 (
 	for b = (a + 1) to cornerArray.count do
 	(
 		if (cornerArray[b][1] == cornerArray[a][1] and cornerArray[b][3] == cornerArray[a][3]) \
 			or (cornerArray[b][1] == cornerArray[a][3] and cornerArray[b][3] == cornerArray[a][1]) do
 			(
 				append setArray #(cornerArray[a][1], cornerArray[a][2], cornerArray[a][3], cornerArray[b][2])
 			)
 	) -- end b loop
 ) -- end a loop
 
 -- determine the area for each quad set
 for s in setArray do
 (
 	dist1 = distance s[1] s[2]
 	dist2 = distance s[2] s[3]
 	dist3 = distance s[3] s[4]
 	dist4 = distance s[4] s[1]
 	dist5 = distance s[1] s[3]
 	semiP = (dist1 + dist2 + dist3 + dist4) / 2
 
 	theArea = sqrt(semiP * (semiP - dist1) * (semiP - dist2) * (semiP - dist5)) + \
 		sqrt(semiP * (semiP - dist1) * (semiP - dist2) * (semiP - dist5))
 
 	if theArea > polyArea do append areaArray theArea
 )
 
 -- use the quad set with the smallest area to create a 4 sided polygon
 theMin = aMin areaArray
 for i = 1 to areaArray.count where areaArray[i] == theMin do
 (
 	p = plane lengthsegs:1 widthsegs:1
 	convertToPoly p
 	
 	polyOp.setVert p 1 setArray[i][1]
 	polyOp.setVert p 2 setArray[i][2]
 	polyOp.setVert p 3 setArray[i][4]
 	polyOp.setVert p 4 setArray[i][3]
 )

Hmm… after a little more testing it’s proven to be unreliable. Sometimes it works correctly (as far as I can tell), other times it creates a quadrangle that is CLEARLY not optimal, or fails to create one at all.

Fo Co or anyone else… help please? :hmm:

hopefully tonight I’ll have a few cycles to look at this…

I guess you never got a chance to look into it further? :shrug:

That is correct.