Map overlay, any algorithm for face updating step?

Question

In chapter 2 of this book the map overlay algorithm, which takes as inputs two doubly connected edge lists, is explained. "Basically" a line intersection algorithm allows to update both the half edges records and the vertices records. After such step the detection of boundary cycles is applied, and later a graph is built, where each connected component represents a new face record. It is explained how to detect whether a boundary cycle is clockwise or not, but I'm not sure how an overall module that implements this part should work. Say I have a DCEL where the face records are not valid, but both the half-edges and the vertices are, do you know any detailed algorithm the actually build the graph? Even a pseudocode is fine.

I can understand how to implement the boundary cycles detection, I would iterate through the half-edges list, navigate through the "next" record, remove such record from the list and when I reach the initial half-edge I would go to the next half-edge of the list and repeat. I would put such sub list of half edges into another list so I would have a list of boundary cycles. I would also label each element of the boundary cycles list as "clock wise" or "anti-clockwise" based on the trick the book explains. Once I have such a list how do I figure out what boundary cycles are incident to the same face? In practice what's the test applied?

Answer 1

Before we 'fill in' the value for the new faces at the halfedges, we wait until the rest of the algorithm is finished, so we know which faces are still present in the end and only have to traverse every edge once. We do this by getting the halfedge that we have considered as a 'representative' and traverse the proper cycle until we return at our edge. So, our complexity is bounded by the sum of the faces and the edges, instead of their product, giving $O(n)$ instead of $O(n^2)$.

That book tends to ignore the subtleties that arise in dealing with DCELs. At first, it seems strange that updating faces would take only $O(n)$ time, since the face of the edge would get updated multiple times. Here, $n$ is 'the complexity of the subdivision', i.e. the sum of the edges and faces of the DECL.

However, since we only want to store the final face value at the end, we wait with the updating the face values of the half-edges until we have filled in everything else. We can store the new value at only one half-edge, which will be the 'representative' of that face and maintain a list of those half-edges.

Then, at the final step, we fill in the face values for the cycles of the stored representative edges, by traversing the cycle associated with the half-edge until we return to the edge where we started and remove a (different) representative if we encounter it, since this means that the face it belonged to no longer exists. By doing so for every representative in the correct order (i.e. from the last created face to the first), we avoid traversing cycles for faces that do not occur in the final DECL. So, we are able to check every face and visit all edges after that, which means we get the required complexity of $O(n)$.