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

Subject: Re: [boost] [polygon] [GSOC] voronoi diagram of line segments
From: David Abrahams (dave_at_[hidden])
Date: 2010-10-17 05:01:08

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)?

> Since the sweepline algorithm implementation is optimal O (n log n)
> and can be made robust given the techniques employed to compute
> predicates I believe we may be able to release new features in
> Boost.Polygon based on this work in 2011.  

So that makes this a very significant achievement.

> The code isn't yet ready for preview or experimentation, but I
> thought the community would appreciate the update and sneak peek at
> the early results generated by the solution to this very challenging
> computatinal geometry problem.  I also want to publically recognize
> and congratulate the student, Andrii Sydorchuk, for his good work
> and great achievement.

Indeed, congratulations to student and mentor alike!

Best Regards,

-- 
Dave Abrahams
BoostPro Computing
http://www.boostpro.com