success is a Boolean variable which will say if we found a valid triangle triangulate is the core of the script, the recursive function which triangulates the polygon drawPoly function just draws the polygon on theCanvas sprite definePoly function pushes polygon points into thePoly vector Private var theCanvas:Sprite=new Sprite() theCanvas is just the sprite where we will draw the polygon and the triangles discardedPoints is the vector of indexes of leftmost points discarded because the triangle includes other vertices They must be in clockwise or counter-clockwise order thePoly is the vector of points making the polygon. 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.Īt the moment, we will triangulate a polygon following these steps:Ģ) Consider the triangle formed by the leftmost vertex, the previous and the next verticesģ) If any of the other vertices is into this triangle, then restart from step 1, finding the next leftmost vertexĤ) 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Īs 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. When i said “suboptimal”, it’s because of two main reasons:ġ) It won’t work with nonsimple polygons (polygons whose edge intersect)Ģ) It won’t work with polygons with holes It’s just the beginning so there’s no need to start with complex concepts at the moment. 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. 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. 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.
0 Comments
Leave a Reply. |