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