Re: [boost] [polygon] [GSOC] voronoi diagram of line segments

Subject: Re: [boost] [polygon] [GSOC] voronoi diagram of line segments
From: laurent.rineau__boost_at_[hidden]
Date: 2010-10-28 05:17:19

Le dimanche 17 octobre 2010 11:01:08, David Abrahams a écrit :
> At Fri, 15 Oct 2010 19:54:07 -0700,
> 
> Simonson, Lucanus J wrote:
> > I just wanted to update the boost dev community on the progress of
> > the GSOC project from this summer implementing voronoi diagram of
> > points and line segments, which leads to delauney triangulation,
> > medial axis of polygons and nearest neighbor.  The student has the
> > sweepline implementation of voronoi for line segments working for
> > several test cases and has provision in the code to handle numerical
> > robustness with the caveot that input coordinates must be integer.
> > I have attached an appealing screenshot showing the result produced
> > by the new code for a small test case.
> 
> Hey, very appealing!  I have a soft place in my heart for
> computational geometry, but it's been a long time since I've studied
> it and I'd never seen a voronoi diagram for points *and* line segments
> before.  So (just guessing when I could look it up), every line
> segment gets a perpendicular line through its endpoints and the curved
> lines are equidistant between each line segment and its nearest
> point(s)?

There is an implementation of that class of diagram in CGAL:
http://www.cgal.org/Manual/latest/doc_html/cgal_manual/Segment_Delaunay_graph_2/Chapter_main.html

It could be interresting to compare with.