CGAL users discussion list

["Wesley Smith" <>]

Here's a tricky problem I've been wrestling with that I'm wondering if
anyone has any insight into.

If a vertex is part of the convex hull of a 3D delaunay triangulation,
then in the set of adjacent facets forms a conical structure which can
be iterated over to derive a circulator over the corresponding voronoi
edges with the addition of a rule that says if there is a facet not on
the crust between 2 such facets, it must be visited before moving to
the adjacent crust facet.

This is what I've implemented so far.  Now the trick is to extend this
to delaunay vertices internal to the triangulation.  From what I can
see, the adjacent facets to such a vertex form a number of closed
loops which need to be iterated over.  Now my question is, is there a
geometric property that can be exploited to uniquely iterator over all
such facets such that each successive facet in the iteration is
adjacent to the previous using only local information (i.e. I'm at
facet f and with vertex v as my pivot, what is the "next" facet)?

For instance, imagine a 3x3x3 grid.  The dual of the point at the
center of the grid is a cube.  Thus there are 6 loops to visit.  How
does one move between the loops with only local information?  Or, is
this not possible and I need to keep track of when a loop is closed
and move on to the next one?

thanks,
wes