CGAL users discussion list

["Gao Zhan, Jimmy" <>]

Bonjour Andreas

Thanks for your suggestion and reminder.
For me, I need to generate a safe 2D path for nano manipulation path 
planner. I need to create a graph and then use it to obtain the shortest 
path.

best,

Zhan


Andreas Fabri wrote:
> Hi Michael, Hi Zhan,
>
> It would be best if you explain what you expect. The edges are
> hyperbola arcs, so you are on the right track by looking at
> the hyperbola class.  It is not documented as it is not in
> the CGAL kernel concept.  The endpoints of the hyperbola arcs
> are only given implicitely, that is you can get the sites
> (circles) which are equidistant to the Voronoi vertex.
> For the unbounded Voronoi cells they have linear rays at the
> two "ends" (unless your input consists of only two disks.
>
> Hope this helps,
>
> andreas
>
> ps.: Just out of curiosity: What problem do you want to solve
>      with the Voronoi diagram of disks ?
>
>
>
>
> Michael Balzer wrote:
> > Hi,
> >
> > I'm currently working on the same problem (for the third time):
> > extracting the regions of the Apollonius diagram from the underlying
> > Apollonius graph. I'm either too stupid for it, or it's really tricky
> > with CGAL (probably it's the first of the two alternatives).
> >
> > My first approach some years ago was to use the method
> > draw_dual_edge(Edge e, Stream& str) of Apollonius_graph_2 for which I
> > implemented my own special stream class. It worked, but I had major
> > problem to create the complete polygons for a regions du to the fact
> > that this method just draw the edges with no particular scheme that
> > allows me too know their orientation and order in the resulting
> > polygon.
> >
> > My second approach was to utilize the CGAL classes Hyperbola_2 and its
> > derivatives. They are not in the manual, but used by the Apollonius
> > classes and not hard to understand. With the edge traversal around an
> > Apollonius site and my own hyperbola classes based on Hyperbola_2 I
> > built my polygonal regions. This approach worked much better, but I
> > still had some problems, especially with the infinite regions.
> >
> > I would really appreciate to get a comment from one of the CGAL
> > auhtors on this topic of extracting the polygonal regions of an
> > Apollonius diagram from the underlying Apollonius graph. Is there
> > something I overlook, or another CGAL package that provides a solution
> > to this problem. I as well tried the Voronoi_diagram_2 adaptor class
> > but could not get a sufficient result for others than the normal
> > Delauney graph.
> >
> >
> > Kind regards,
> > Michael
> >
> >
> >
> >
> > On Fri, Mar 13, 2009 at 15:30, Gao Zhan, Jimmy <> 
> > wrote:
> > > Hello CGAL friends
> > >
> > >
> > > I want to use the 2D Apollonius Graphs module to obtain the voronoi 
> > > diagram
> > > of some disks on a plane. My question is how to get the edge 
> > > information?
> > > What’s the geometric representation of the edges? I can get the edge
> > > iterator, but after that how do I get the information?
> > >
> > >
> > > Any suggestion or hints are appreciated.
> > >
> > > Best,
> > >
> > > Zhan
> > >
> > > --
> > > You are currently subscribed to cgal-discuss.
> > > To unsubscribe or access the archives, go to
> > > https://lists-sop.inria.fr/wws/info/cgal-discuss