Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. It only takes a minute to sign up.
Sign up to join this community
In chapter 3 book how to triangulate a polygon is explained, however it doesn't seems to me that how to handle the faces are explained. My guess would to add two new face and erase the old one every time a diagonal is inserted (both while decomposing the polygon in monotone pieces, and during the actual triangulation). Is my guess correct?
Is there a smarter way to do that?
For the algorithm that triangulates a monotone polygon: every time you add a diagonal, you actually find a triangle. So, you can indeed explicitly relabel the face-value associated with all edges of that triangle. That does not affect the asymptotic running time.
For the algorithm that splits a simple polygon in to monotone polygons you cannot really afford that, as you may have to relabel an (half)edge multiple times. Hence, a solution there is just to be lazy: i.e. use the sweep just to update the vertex/edge fields in the DCEL, and ignore the face values. When you are done with the sweep: use the vertex/edge fields, in particular the next-fields on the half-edges, to walk around every face, and set the face values appropriately.
