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

Subject: Re: [boost] [polygon] [GSOC] voronoi diagram of line segments
From: Simonson, Lucanus J (lucanus.j.simonson_at_[hidden])
Date: 2010-10-29 14:05:00

laurent.rineau__boost_at_[hidden] wrote:
> 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.

Yes, we know of CGAL, vroni and Johnathan Shewchuk's Triangle implementations of voronoi diagram for points and, CGAL, vroni for voronoi diagram of line segments.  We are intersted in comparing with all three, but observe that none have free licenses and want to complete our implementation before looking too closely at any of the commercially licensed code to avoid IP contamination.

Regards,
Luke