CGAL arrangements: how to parse the faces inside a hole?

Question

Let's take Figure 34.2 of the user manual. f1 contains two holes. When parsing the holes using f1->holes_begin() and f1->holes_end(), how can I get the list of the faces inside each hole? For example, from the hole "f3+f4", how can I get the list (f3, f4)?

Of course, I could iterate over all the halfedges bounding the hole and access the face it bounds on its interior side using the twin() to get the opposite halfedge, and then face() to get the face that the opposite halfedge bounds, then remove duplicates, but I'm wondering if there is a simpler solution.

Thanks!

Answer 1

You need to iterate over the ccbs. For example, the code in draw_arrangement_2.h does it; see an explanation below. Observe that the face member functions holes_begin() and holes_end() are the same as inner_ccbs_begin() and inner_ccbs_end(). (The latter come from the base class Arrangement_on_syrface_2.)

We maintain a Boolean flag for each face called m_visited that indicates whether we visited the face. In the code this is done via an std:unordered_map. You can also extend the face record with a Boolean flag for instance.

We start with the unbounded faces (see add_faces()) and descend down to their holes. For each face f we call add_face(f); in this function we traverse the face inner ccbs and outer ccbs. For each ccb c we call add_ccb(c). For a ccb c we traverse the halfedges of c; for each halfedge h we visit the face f incident to the twin of h. If we visited f we discard it; otherwise, we mark it as visited and recurse to process f by calling add_face(f).

Notice that in the drawing function we process the ccbs such that we draw the regions bounded by the outer ccb of the faces in the opposite order of containment; see the call to draw_region().