CGAL users discussion list

[Martin Uhrin <>]

Dear CGAL community,

I'd like to traverse a Delaunay graph in-order going over all Delaunay edges
that are dual to unbounded Voronoi edges like so:

<http://cgal-discuss.949826.n4.nabble.com/file/n4658419/Delaunay_Voronoi.png> 

Where latin letters show the order I'd like to traverse edges in.  Numbers
show my attempted solution which involves the following:

1) Start at edge a
2) Use delaunay.incident_edges(vertex 1) to circulate starting from the next
edge ccw from a
3) When a Delaunay edge that has an unbounded dual is found (b will be the
first) repeat from step 2) using the vertex at the other side of the edge
from the one currently being circulated (2 will be first)

One of my main sticking points was I couldn't convince myself that I was
correctly finding the edge-incident vertex opposite the one I am currently
circulating.

My (non-working) attempt at coding this:

    DG::Edge_circulator cl = delaunay.incident_edges(
        delaunay.incident_vertices(delaunay.infinite_vertex()));
    DG::Edge_circulator first = cl;
    do
    {
      if(delaunay.is_infinite(cl->first->vertex(cl->second)) &&
          voronoi.dual(*cl)->is_unbounded())
      {
        // Found initial edge
        break;
      }
      ++cl;
    } while(cl != first);

    first = cl;
    do
    {
      const DG::Edge_circulator starting = cl;
      do
      {
        ++cl;
        if(voronoi.dual(*cl)->is_unbounded())
        {
          cl =
delaunay.incident_edges(cl->first->vertex(delaunay.ccw(cl->second)),
cl->first);
          break;
        }
      } while(cl != starting);

    } while(cl != first);

Any help is much appreciated.

-Martin



--
View this message in context: 
http://cgal-discuss.949826.n4.nabble.com/In-order-traversal-of-Delaunay-edges-corresponding-to-unbounded-Voronoi-edges-tp4658419.html
Sent from the cgal-discuss mailing list archive at Nabble.com.