Polygon triangulation: decomposition of a polygon into triangles with AS3
In some cases, better said in most cases, dealing with arbitrary polygons is harder than dealing with a given number of triangles forming such polygons. That’s why polygon triangulation, the decomposition of a polygonal area into a set of triangles which may have vertices only at the vertices of the starting polygon, is a must know.
There are several ways to split a polygon into triangles, and in this post I am trying to do the easiest, but also suboptimal way. It’s just the beginning so there’s no need to start with complex concepts at the moment.
When i said “suboptimal”, it’s because of two main reasons:
1) It won’t work with nonsimple polygons (polygons whose edge intersect)
2) It won’t work with polygons with holes
Obviously, during next posts, I will show you how to triangulate any kind of polygon, and above all some practical examples of stuff you can do with triangulation.
At the moment, we will triangulate a polygon following these steps:
1) Find the leftmost vertex
2) Consider the triangle formed by the leftmost vertex, the previous and the next vertices
3) If any of the other vertices is into this triangle, then restart from step 1, finding the next leftmost vertex
4) If no other vertices are inside the triangle, draw the triangle and apply the whole process to the polygon resulting by the starting polygon without the lefmost vertex found
As you can see, it’s a recursive process which can be easily turned into an algorithm, assuming you already know the algorithm to determine if a point is inside a triangle with mathematics.
Here is the script:
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 |
package { import flash.display.Sprite; import flash.geom.Point; public class Main extends Sprite { // thePoly is the vector of points making the polygon. They must be in clockwise or counter-clockwise order private var thePoly:Vector.<Point>=new Vector.<Point>(); // discardedPoints is the vector of indexes of leftmost points discarded because the triangle includes other vertices private var discardedPoints:Vector.<int>=new Vector.<int>(); // theCanvas is just the sprite where we will draw the polygon and the triangles private var theCanvas:Sprite=new Sprite(); public function Main() { // adding the sprite where to draw addChild(theCanvas); // definePoly function pushes polygon points into thePoly vector definePoly(); // drawPoly function just draws the polygon on theCanvas sprite drawPoly(); // triangulate is the core of the script, the recursive function which triangulates the polygon triangulate(); } private function triangulate():void { // success is a Boolean variable which will say if we found a valid triangle var success:Boolean = true; // triangleA is the leftmost vertex of the polygon, according to discarded points var triangleA:int = leftmostPoint(); // triangleB is next vertex var triangleB:int = (triangleA + 1) % thePoly.length; // triangleC is previous vertex so in the end we have a triangle var triangleC:int = (triangleA - 1); if (triangleC<0) { triangleC = thePoly.length - 1; } // now it's time to see if any of the remaining vertices is inside the triangle for (var i:int=0; i<thePoly.length; i++) { if (i!=triangleA && i!=triangleB && i!=triangleC) { if (isInsideTriangle(thePoly[triangleA],thePoly[triangleB],thePoly[triangleC],thePoly[i])) { // if one vertex is inside the triangle, we discard the leftmost point just found discardedPoints.push(triangleA); // then we set success variable to false success = false; break; } } } if (success) { // if we have just found a valid triangle, we draw it drawTriangle(triangleA,triangleB,triangleC); // then we remove the leftmost point found from the polygon, obtaining a smaller polygon thePoly.splice(triangleA,1); // we also clear the vector of discarded points discardedPoints=new Vector.<int>(); } // if there are still more than three points in the polygon (it's not a triangle) then execute triangulate function once more if (thePoly.length > 3) { triangulate(); } else { // otherwise draw the remaining triangle drawTriangle(0,1,2); } } // here points are pushed into the polygon private function definePoly():void { thePoly.push(new Point(220,140)); thePoly.push(new Point(420,140)); thePoly.push(new Point(420,340)); thePoly.push(new Point(320,210)); thePoly.push(new Point(220,340)); thePoly.push(new Point(100,240)); } // this function just draws a polygon private function drawPoly():void { theCanvas.graphics.lineStyle(5,0x000000); theCanvas.graphics.moveTo(thePoly[0].x,thePoly[0].y); for (var i:int=1; i<thePoly.length; i++) { theCanvas.graphics.lineTo(thePoly[i].x,thePoly[i].y); } theCanvas.graphics.lineTo(thePoly[0].x,thePoly[0].y); } // and this function just draws a triangle private function drawTriangle(a:int,b:int,c:int):void { theCanvas.graphics.lineStyle(1,0xff0000); theCanvas.graphics.moveTo(thePoly[a].x,thePoly[a].y); theCanvas.graphics.lineTo(thePoly[b].x,thePoly[b].y); theCanvas.graphics.lineTo(thePoly[c].x,thePoly[c].y); theCanvas.graphics.lineTo(thePoly[a].x,thePoly[a].y); } // function to find the leftmost point private function leftmostPoint():int { // first, I look for the first undiscarded point for (var i:int=0; i<thePoly.length; i++) { if (discardedPoints.indexOf(i) == -1) { var minIndex:int = i; break; } } // then I check for all undiscarded points to find the one with the lowest x value (the leftmost) for (i=0; i<thePoly.length; i++) { if (discardedPoints.indexOf(i) == -1 && thePoly[i].x < thePoly[minIndex].x) { minIndex = i; } } return minIndex; } // these two functions have already been explained in the post "Algorithm to determine if a point is inside a triangle with mathematics (no hit test involved)" private function isInsideTriangle(A:Point,B:Point,C:Point,P:Point):Boolean { var planeAB:Number = (A.x-P.x)*(B.y-P.y)-(B.x-P.x)*(A.y-P.y); var planeBC:Number = (B.x-P.x)*(C.y-P.y)-(C.x - P.x)*(B.y-P.y); var planeCA:Number = (C.x-P.x)*(A.y-P.y)-(A.x - P.x)*(C.y-P.y); return sign(planeAB)==sign(planeBC) && sign(planeBC)==sign(planeCA); } private function sign(n:Number):int { return Math.abs(n)/n; } } } |
And this is the result:
Feel free to change the polygon and share your thoughts.
(5 votes, average: 5.00 out of 5)
Loading ...
They can be easily customized to meet the unique requirements of your project.
This post has 4 comments
Wilson Silva
I have needed this algorithm some months ago, but I since I was short on time, and didn’t find a proper way to do this, I decided to drop the feature I was developing. Now I’m coding the next release of the same solution and this code will be very, very handy. Many thanks :D
Paolo Di Stefano
Grazie! And good work with the low linecount too!
Rinalds
Is this method of collision detection faster then Seperaring Axis Theorem?
Slicedtoad
I don’t think this algorithm works for all simple polygons.
Don’t have flash installed atm, so I can’t test it though.
Could someone try running it with the the following vertices (assuming 0,0 is bottom left):
– x , y
A: 0 , 0
B: 50,100
C: 45,50
D: 60,60
E:200,40
This is what I assume should happen:
ABE is tested and found to be invalid.
A is discarded, next leftmost point is C.
BCD is tested and found to be valid and drawn.
This is wrong. Drawing BCD would be mean drawing a line between B and D which is outside of the polygon.
I might be missing something but that’s what it looks like to me. Could someone either correct me or point me to a fix for this problem?