CGAL users discussion list

[Efraim Fogel <>]

The bug you found was real, and the suggestion you made to fix it was 
good. I've applied it as is. The coming release 3.3.1 already includes 
the fix. Thanks!


 wrote:
> 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
>   
--
 ____  _        ____             _
/_____/_) o    /__________  __  //
(____ (   (    (    (_/ (_/-(-'_(/
                       _/