As in the title of the question, how to triangulate a simple polygon that grows dynamically that's say whenever a new vertex is added by user or by a computer dynamically the polygon should get triangulated again. So rather than running some triangulation algorithm after each new vertex is added is there any clever/efficient(possibly easy to implement also) way for each new input it should take say <= O(n) time to triangulate the polygon. The newly added vertex will be adjacent with the first and last vertices of the current polygon.
4
votes
Does the polygon stay convex? Then if a new vertex C is added between A and B just make ABC an additional triangle.
– Henry
not necessarily, but it is always a simple polygon.
– mcertitude
well, when a new vertex adds a triangle, it's pretty straightforward, but if it 'subtracts' it (i.e. when the vertex is inside the existing polygon), it can change the internal traingulation very dramatically, and i doubt there's a way to simplify that. so maybe you only handle addition as a special case.
– Anton Knyazyev
how about y-monotonicity? say if polygon is being divided into y-monotone polygons dynamically, would adding a new vertex would require more than O(n) time to change the structure ?
– mcertitude
If I am right, there are situations such that adding a vertex will force you to redo the whole triangulation (if the new edges cross all diagonals).
– Yves Daoust
2 Answers
2
votes
When you insert a new vertex and replace an edge with two, the triangle they form may overlap a number of triangles of the triangulation. The overlapped triangles form a subpolygon. Build the outline of this polygon and insert the new vertex. Then retriangulate the updated subpolygon.
I guess that the overlapping triangles can be efficiently found by exploring the neighbors of the starting triangle, recursively, and checking them for overlap. The outline of the subpolygon is formed of the edges not shared by two triangles.
1
votes
I'm assuming that the polygon is augmented, at each step, by adding a vertex C, removing the segment AB, and adding segments AC and CB. I'm also assuming no degeneracies.
If ABC winds positively (that is, the polygon is expanded "outwards"), simply add ABC to the triangulation.
Otherwise, consider the triangle ABD in the previous triangulation. If C is in that triangle, remove the triangle ABD and add triangles BDC and DAC. If it is not, then it is in the subpolygon on the AD side, or the one on the BD side. Remove ABD and recurse into the appropriate subpolygon, adding C to (say) the segment BD. Once the recursion completes, add triangles BDC and DAC as before.
This solution relies on both the old and the new polygons being simple (non-self-intersecting). Otherwise, adding the triangles following the recursive step might not be valid.
