CGAL users discussion list

Dear CGAL developers,

I've come across a bug in the dual arrangement representation for Boost 
graphs in current CGAL 3.3 (probably present in earlier versions too).

In this graph representation, graph vertices correspond to arrangement faces, 
and graph edges correspond to arrangement halfedges.

The Face_neighbor_iterator class (graph_traits_dual_arrangement_2.h:112) 
provides the iteration over all outgoing graph edges (arrangement halfedges) 
for a given graph vertex (arrangement face).

The iterator first considers the outer boundary of the face and then the 
boundaries of the holes inside the face. In the constructor, the 
'_outer_ccb_circ' halfedge circulator is initialized to the "first" halfedge 
of the outer boundary. Likewise, the '_curr_hole_circ' halfedge circulator is 
initialized to the "first" halfedge of the first hole.

Initially, each time the iterator is incremented, '_outer_ccb_circ' is 
incremented until it reaches the "first" halfedge for the second time 
(graph_traits_dual_arrangement_2.h:252). When this happens, the outer 
boundary circulation "falls through" to hole boundary circulation, and 
'_curr_hole_circ' is immediately incremented.

The bug is that this way the "first" halfedge of the first hole is being 
skipped (no problems with subsequent holes though). The graph will be missing 
one graph edge per arrangement face containing at least one hole.

Suggested fix: replace lines 252 and 253 of graph_traits_dual_arrangement_2.h:
-        if (_outer_ccb_circ != _face->outer_ccb())
-          return;
by
+        if ((_outer_ccb_circ == _face->outer_ccb())
+            && (_hole_iter == _face->holes_end()))
+          _end = true;     // Report "the end" if we are there.
+        return;            // This return is unconditional.

Is it possible to fix this in the next release?

Kind regards,

Michiel De Wilde