CGAL users discussion list

[Andreas Fabri <>]

Bernhard Kornberger wrote:
>  schrieb:
> > Bernhard Kornberger wrote:
> > >  schrieb:
> >
> > > > > Is it true that I have to implement the conversion from
> > > > > the power diagram to a graph of the power diagram by myself
> > > > > or is there already a function that I didn't find?
> > > >
> > > >
> > > > The graph is dual to the triangulation (up to degeneracies), do you 
> > > > need to convert the triangulation to its dual that you would store 
> > > > in addition ?
> > > >
> > > >     Monique
> > >
> > >
> > > Right. I need a function like this:
> > >
> > > Regular_triangulation Tr;
> > > Tr.insert(p1);
> > > Tr.insert(p2);
> > > Tr.insert(p3);
> > > Tr.insert(p4);
> > >
> > > UndirectedGraph g=Tr.dual();
> > >
> > > ..such that I can traverse along the edges of $g afterwards.
> >
> > but you can traverse edges of g by just following adjacency relations 
> > between tetrahedra in Tr, without storing g.
> >     Monique
>
> I need functions like breath-first search on the edges of the
> power diagram and I need to label edges as already visited or
> not. This is complicated to implement (and horrible to debug)
> if the power-diagram is not explicitly given as a graph.

Hi Bernhard,

If you implement it anyway as you need it, and CGAL doesn't offer it,
you might implement a graph_traits and the some global functions
to explore adjacencies in a graph, so that the Voronoi diagram
becomes model of a boost::graph.

You can see how to do this in the chapter http://www.cgal.org/Pkg/BGL
The advantage is that you then can use the algorithms of the BGL
on this graph.

And if once you done you contribute it back.....

andreas


> Best
> Bernhard