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?