given an array of diagonals (as corners) of a polygon and the deg of the polygon derive the internal triangles of the polygon as an array (as corners).
for example…
case1: #(3, 5, 3, 6, 2, 6) should produce #(3, 4, 5, 3, 5, 6, 2, 3, 6, 1, 2, 6)
case2: #(1, 3, 3, 5, 3, 6) should produce #(1, 2, 3, 3, 4, 5, 3, 5, 6, 1, 3, 6)
case3: #(1, 3, 3, 5, 1, 5) should produce #(1, 2, 3, 3, 4, 5, 1, 3, 5, 1, 5, 6)
note the order of the tri triplets within the array is unimportant though the order of the tri triplet is (should be ccw). The rules are no sdk as that would be too easy (MNFace::GetTriangles()).
the order of the “triplets” is unimportant
1, 2, 3, 3, 4, 5, or 3, 4, 5, 1, 2, 3, is ok
for the first “triplet” of corners…
1,2,3 – 2,3,1 or 3,1,2 is ok (ccw) where as 2, 1 , 3 or 1, 3, 2 and 3, 2, 1 is not (cw)
Not optimized, not very clean, but works:
(
fn findTriangles inputArray orderedVerts outputTrianglesArray: #()=
(
local vertsToDelete = #()
for i = 1 to inputArray.count by 2 do
(
if (v2 = findItem orderedVerts inputArray[i+1]) == (v1 = findItem orderedVerts inputArray[i]) + 2 do
(
append outputTrianglesArray #(orderedVerts[v1], orderedVerts[v1+1], orderedVerts[v2])
deleteItem orderedVerts (v1+1)
append vertsToDelete i
append vertsToDelete (i+1)
)
)
sort vertsToDelete
for i = vertsToDelete.count to 1 do deleteItem inputArray vertsToDelete[i]
if orderedVerts.count == 3 then
(
append outputTrianglesArray orderedVerts
return (outputTrianglesArray)
)
else
(
findTriangles inputArray orderedVerts outputTrianglesArray:outputTrianglesArray
)
)
numCorners = 6
--inputCornersArray = #(3, 5, 3, 6, 2, 6)
--inputCornersArray = #(1, 3, 3, 5, 3, 6)
inputCornersArray = #(1, 3, 3, 5, 1, 5)
orderedVerts = for v = 1 to numcorners collect v
result = findTriangles inputCornersArray orderedVerts
format "Result Triangles are: %
" result
)
Algorithm: recursive finding corners that are consecutive by 2, then deleting the intermediate corner from array
blimey that was quick
Here’s an optimized one: (doing more eliminations by loop and avoiding sorting)
fn findTriangles2 inputArray orderedVerts outputTrianglesArray: #()=
(
i = -1
do
(
i += 2
if (v2 = findItem orderedVerts inputArray[i+1]) == (v1 = findItem orderedVerts inputArray[i]) + 2 do
(
append outputTrianglesArray #(orderedVerts[v1], orderedVerts[v1+1], orderedVerts[v2])
deleteItem orderedVerts (v1+1)
deleteItem inputArray (i+1)
deleteItem inputArray (i)
i -= 2
)
)
while i < inputArray.count
if orderedVerts.count == 3 then
(
append outputTrianglesArray orderedVerts
return (outputTrianglesArray)
)
else
(
findTriangles2 inputArray orderedVerts outputTrianglesArray:outputTrianglesArray
)
)
The sorting can be avoided if the input matrix has always the lowest vertex from each edge first.
Edit:
In fact, these two functions won’t work at all if the lowest vertex of each edge is not the first one.
New function to allow input corner array to have the edge vertex in any order:
fn findTriangles2 inputArray orderedVerts outputTrianglesArray: #()=
(
if mod inputArray.count 2 != 0 do return (format "Input array must had an even number of elements
")
i = -1
do
(
i += 2
v1 = findItem orderedVerts inputArray[i]
v2 = findItem orderedVerts inputArray[i+1]
if v2 < v1 do swap v1 v2
if (v2 == v1 + 2) do
(
append outputTrianglesArray #(orderedVerts[v1], orderedVerts[v1+1], orderedVerts[v2])
deleteItem orderedVerts (v1+1)
deleteItem inputArray (i+1)
deleteItem inputArray (i)
i -= 2
)
)
while i < inputArray.count
if orderedVerts.count == 3 then
(
append outputTrianglesArray orderedVerts
return (outputTrianglesArray)
)
else
(
findTriangles2 inputArray orderedVerts outputTrianglesArray:outputTrianglesArray
)
)
impressive stuff aaandres
Thanks Klvnk.
You know, I’m right know developping an FTP reader and I’m saturated with so many recursive functions to read the directory tree, names, sizes… Do non recursive functions exist!!!
I was trying to get a reverse look up to work to to avoid using the finditem but i’ve not managed to get it to work correctly with the “ear clipping” technique.
how did you get these numbers with no using SDK ? — >case1: #(3, 5, 3, 6, 2, 6) should produce #(3, 4, 5, 3, 5, 6, 2, 3, 6, 1, 2, 6)