Well, wasn’t able to figure out how to make the undo work, but I found a different solution to that particular problem, and have taken it a couple steps further.
The code I have now gives the following result:
What I would like to do is, by extending the various edges that make up the polygon to their intersection points, create every possible quadrangle made up of those lines, and then determine which has the smallest area.
While this is not guaranteed to give me the smallest possible enclosing quadrangle, it will ensure that the resulting quadrangle has 4 matching sides with the polygon.
The current script is as follows (white: new code):
global pointA, pointB
theDist = 0
-- Function courtesy of Martijn van Herk
fn AlignPivotTo Obj Tgt =
(
-- Get matrix from object
if classOf Tgt != matrix3 then Tgt = Tgt.transform
-- Store child transforms
local ChldTFs = in coordSys Tgt (for c in Obj.children collect c.transform)
-- Current offset transform matrix
local TF_Scale = scaleMatrix Obj.objectOffsetScale
local TF_Rot = Obj.objectOffsetRot as matrix3
local TF_Pos = transMatrix Obj.objectOffsetPos
local TF_Offset = TF_Scale * TF_Rot * TF_Pos
-- New offset transform matrix
TF_Offset *= obj.transform * inverse Tgt
-- Apply matrix
Obj.transform = Tgt
-- Restore offsets
Obj.objectOffsetPos = TF_Offset.translation
Obj.objectOffsetRot = TF_Offset.rotation
Obj.objectOffsetScale = TF_Offset.scale
-- Restore child transforms
for i = 1 to Obj.children.count do Obj.children[i].transform = ChldTFs[i] * inverse Tgt * Obj.transform
) -- end function
--remove concave vertices
undo on
(
vertCount = $.numVerts
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)
)
) -- undo off
-- find the diameter of the polygon
for i = 1 to $.numVerts do
(
for j = 1 to $.numVerts where j != i do
(
a = polyOp.getVert $ i
b = polyOp.getVert $ j
d = distance a b
if d > theDist do (pointA = a; pointB = b; theDist = d)
) -- end j loop
) -- end i loop
--define matrix values
faceNormal = polyOp.getFaceNormal $ 1 -- "1" is the only face in a single polygon editable poly
dVector = normalize (pointA - pointB)
crossVector = normalize (cross dVector faceNormal)
theMatrix = matrix3 crossVector dVector faceNormal ((pointA + pointB) / 2)
alignPivotTo $ theMatrix
-- extend edges as lines
for i = 1 to polyOp.getNumEdges $ do
(
thePoints = polyOp.getVertsUsingEdge $ i as array
theStart = polyOp.getVert $ thePoints[1]
theEnd = polyOp.getVert $ thePoints[2]
--create a line matching the edge
fn drawLineBetweenTwoPoints pointA pointB =
(
ss = SplineShape pos:pointA
addNewSpline ss
addKnot ss 1 #corner #line PointA
addKnot ss 1 #corner #line PointB
updateShape ss
ss
)
theSpline = drawLineBetweenTwoPoints theStart theEnd
eVector = normalize (theStart - theEnd)
cVector = normalize (cross eVector faceNormal)
edgeMatrix = matrix3 cVector eVector faceNormal ((theStart + theEnd) / 2)
alignPivotTo theSpline edgeMatrix
--extend the points forward and backward locally using the edgeMatrix coordsys
in coordsys edgeMatrix setKnotPoint theSpline 1 1 [0, theDist, 0]
in coordsys edgeMatrix setKnotPoint theSpline 1 2 [0, -theDist, 0]
)
Okay, figured out how to find all the intersection points…
NEXT: I need to
- Figure out every possible quadrangle using these points as corners
- Keep only those quadrangles which still enclose the original shape.
- Keep the quadrangle with the smallest area as my solution.
Of these 3 steps, 2 is the only one I am going to have a problem with. How do I determine whether one polygon is contained within the bounds of another?
script in progress:
-- Function courtesy of Martijn van Herk
fn alignPivotTo Obj Tgt =
(
-- Get matrix from object
if classOf Tgt != matrix3 then Tgt = Tgt.transform
-- Store child transforms
local ChldTFs = in coordSys Tgt (for c in Obj.children collect c.transform)
-- Current offset transform matrix
local TF_Scale = scaleMatrix Obj.objectOffsetScale
local TF_Rot = Obj.objectOffsetRot as matrix3
local TF_Pos = transMatrix Obj.objectOffsetPos
local TF_Offset = TF_Scale * TF_Rot * TF_Pos
-- New offset transform matrix
TF_Offset *= obj.transform * inverse Tgt
-- Apply matrix
Obj.transform = Tgt
-- Restore offsets
Obj.objectOffsetPos = TF_Offset.translation
Obj.objectOffsetRot = TF_Offset.rotation
Obj.objectOffsetScale = TF_Offset.scale
-- Restore child transforms
for i = 1 to Obj.children.count do Obj.children[i].transform = ChldTFs[i] * inverse Tgt * Obj.transform
) -- end function
global pointA, pointB
theDist = 0
--remove concave vertices
undo on
(
vertCount = $.numVerts
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)
)
) -- undo off
-- find the diameter of the polygon
for i = 1 to $.numVerts do
(
for j = 1 to $.numVerts where j != i do
(
a = polyOp.getVert $ i
b = polyOp.getVert $ j
d = distance a b
if d > theDist do (pointA = a; pointB = b; theDist = d)
) -- end j loop
) -- end i loop
--define matrix values
faceNormal = polyOp.getFaceNormal $ 1 -- "1" is the only face in a single polygon editable poly
dVector = normalize (pointA - pointB)
crossVector = normalize (cross dVector faceNormal)
theMatrix = matrix3 crossVector dVector faceNormal ((pointA + pointB) / 2)
alignPivotTo $ theMatrix
-- create an array of the start/end points for all edges
edgeArray = #()
for i = 1 to polyOp.getNumEdges $ do
(
thePoints = polyOp.getVertsUsingEdge $ i as array
theStart = polyOp.getVert $ thePoints[1]
theEnd = polyOp.getVert $ thePoints[2]
append edgeArray #(theStart, theEnd)
)
-- 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))) )
p = point size:0.1 pos:((i1 + i2) / 2)
)
-- find the intersections of all edges with all other edges
iArray = #()
for i = 1 to edgeArray.count do
(
for j = 1 to edgeArray.count where j > i do
(
theIntersect = lineLineIntersect edgeArray[i][1] edgeArray[i][2] edgeArray[j][1] edgeArray [j][2]
)
)
Just after a quick glance, I think you may be better off not using the intersecting points, but sticking with the lines because you’re guaranteed that any quad made from 4 of those lines will include the shape. (Actually, if the shape of the intersection corners is the convex hull, you’re guaranteed that NONE of the quads cut from it will include the entire shape.)
Keep in mind that I haven’t really thought this through yet, but picking all the possible quads from those lines shouldn’t be too hard. You have the fact that not all of the line combos make a quad to help you out. The steps would look something like this:
- Find the convex hull.
- Calculate lines between all adjacent points (ordered around the shape)
- Calculate the angle of each line off the origin.
- Pick the smallest angled line and then find the next line around the shape that is both 3 lines away and greater than 180 deg off your first line (all others won’t make a quad).
- Calculate the area for all the remaining combos
- Do the same for every line (that’s the ugly part, but you only need to do this once for each shape, right?)
- Pick the one with the smallest area.
Something like that.
Actually, it’s possible that the smallest area will be made by the combination of lines where the deviation of the difference between the angles is closest to 90 deg (meaning, the combo closest to a rectangle). This seems to work for all the shapes I can come up with in my head, but there may be some cases I haven’t considered yet.
Sorry, you lost me about halfway through…
- Find the convex hull.
- Calculate lines between all adjacent points (ordered around the shape)
I’ve done that…
- Calculate the angle of each line off the origin.
A line doesn’t have an angle, so I assume you mean the vector. And origin in local or world space? (I’m guessing local.)
- Pick the smallest angled line and then find the next line around the shape that is both 3 lines away and greater than 180 deg off your first line (all others won’t make a quad).
Okay wait, I’m lost. Smallest angled line means what? And what do you mean by 3 lines away and greater than 180 degrees? (Also… won’t any 4 non parallel lines make a quadrangle? :D) I’m sure that made sense to you when you typed it but maybe you could explain it in a little clearer terms. I don’t understand what you’re suggesting, much less how to approach doing it.
- Calculate the area for all the remaining combos
- Do the same for every line (that’s the ugly part, but you only need to do this once for each shape, right?)
- Pick the one with the smallest area.
That part sounds pretty close to what I was already thinking about. Not sure what you mean by “the same for every line” though.
Actually, it’s possible that the smallest area will be made by the combination of lines where the deviation of the difference between the angles is closest to 90 deg (meaning, the combo closest to a rectangle). This seems to work for all the shapes I can come up with in my head, but there may be some cases I haven’t considered yet.
I’m not sure if I am reading that right. It sounds like you are saying that the quadrangle closest to a rectangle would be the smallest possible area. That’s clearly not true; the smallest rectangle for a trapezoid or parallelogram shape contains a lot of extra space. If this WERE true there would be no point in what I’m doing, and I would be best off just using the optimal bbox solution you provided
Okay, I’m really, really close here… Now I just have to figure out how to make quadrangles from these lines:
Latest version of the script:
-- Function courtesy of Martijn van Herk
fn alignPivotTo Obj Tgt =
(
-- Get matrix from object
if classOf Tgt != matrix3 then Tgt = Tgt.transform
-- Store child transforms
local ChldTFs = in coordSys Tgt (for c in Obj.children collect c.transform)
-- Current offset transform matrix
local TF_Scale = scaleMatrix Obj.objectOffsetScale
local TF_Rot = Obj.objectOffsetRot as matrix3
local TF_Pos = transMatrix Obj.objectOffsetPos
local TF_Offset = TF_Scale * TF_Rot * TF_Pos
-- New offset transform matrix
TF_Offset *= obj.transform * inverse Tgt
-- Apply matrix
Obj.transform = Tgt
-- Restore offsets
Obj.objectOffsetPos = TF_Offset.translation
Obj.objectOffsetRot = TF_Offset.rotation
Obj.objectOffsetScale = TF_Offset.scale
-- Restore child transforms
for i = 1 to Obj.children.count do Obj.children[i].transform = ChldTFs[i] * inverse Tgt * Obj.transform
) -- end function
global pointA, pointB
theDist = 0
--remove concave vertices
undo on
(
vertCount = $.numVerts
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)
)
) -- undo off
-- find the diameter of the polygon
for i = 1 to $.numVerts do
(
for j = 1 to $.numVerts where j != i do
(
a = polyOp.getVert $ i
b = polyOp.getVert $ j
d = distance a b
if d > theDist do (pointA = a; pointB = b; theDist = d)
) -- end j loop
) -- end i loop
--define matrix values
faceNormal = polyOp.getFaceNormal $ 1 -- "1" is the only face in a single polygon editable poly
dVector = normalize (pointA - pointB)
crossVector = normalize (cross dVector faceNormal)
theMatrix = matrix3 crossVector dVector faceNormal ((pointA + pointB) / 2)
alignPivotTo $ theMatrix
-- create an array of the start/end points for all edges
edgeArray = #()
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)
)
-- 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)
)
-- find the points at which the edge lines intersect
iArray = #()
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
lineArray = #()
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
sideArray = #()
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
)
-- function taken from MaxScript Reference
fn drawLineBetweenTwoPoints pointA pointB =
(
ss = SplineShape pos:pointA
addNewSpline ss
addKnot ss 1 #corner #line PointA
addKnot ss 1 #corner #line PointB
updateShape ss
ss
)
for theSide in sideArray do drawLineBetweenTwoPoints theSide[1] theSide[2]
It’s frustrating that this board won’t allow you to nest quotes…
I used origin, but any arbitrary line that passes through the shape will do. The trick is to calculate the relative differences between the lines’ angles.
Okay wait, I’m lost. Smallest angled line means what? And what do you mean by 3 lines away and greater than 180 degrees? (Also… won’t any 4 non parallel lines make a quadrangle? :D) I’m sure that made sense to you when you typed it but maybe you could explain it in a little clearer terms. I don’t understand what you’re suggesting, much less how to approach doing it.
Yes, any 4 non-parallel lines will make a quadrangle, but not necessarily one that surrounds your shape. To ensure that the shape is enclosed, the angles between the first line and the 4th have to total greater than 180. Think of it this way: you have a line. The next one turns just 5 deg – then next 5 more and the last just 5 more. Because the total of the angles is only 15 deg, the quad that these lines makes as somewhere off in space. It does not surround your shape. But, if the lines turn 60, 60 and 61 deg, you know that they enclose your shape because the last line has turned enough to intersect the first line “around” the shape (this is simple to draw, hard do describe).
I’m not sure if I am reading that right. It sounds like you are saying that the quadrangle closest to a rectangle would be the smallest possible area. That’s clearly not true; the smallest rectangle for a trapezoid or parallelogram shape contains a lot of extra space. If this WERE true there would be no point in what I’m doing, and I would be best off just using the optimal bbox solution you provided
Almost. The quad made up of the lines tangent to convex hull closest to a rectangle will give you the smallest ares (those are the lines you’ve already calculated, right?). So in your parallelogram example, the rectangle you describe won’t even be considered because it uses lines that aren’t tangent to the hull. The 4 lines that make up the parallelogram are the only lines considered so the parallelogram itself is the best quad (trivially).
But this holds true for more complex shapes:
- find the lines tangent to the convex hull (which you’ve already done)
- calculate the differences in angle between the lines
- find the 4 lines whose 4 angles deviate from 90 deg the least and you’ve got your best quad
I don’t have time today, but maybe tonight I’ll bang out some maxstript to do this.
I’d very much appreciate it if you get the chance. Now I understand most of what you were saying, but still can’t figure out how to make the jump from here to there…
Unfortunately my theory was wrong. The closest quad to a rect does not guarantee the smallest area. See this shape as an example:
___
| \
| \
| \
| \
| |
--------
Yeah, I thought that sounded too convenient to be true…
Anyway, it sounded like you had an idea for determining which combinations of four lines fully surround the polygon. If you could show me how to script that, I would very much appreciate it, since I think that’s all I still need.