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

Subject: [boost] [polygon] [GSOC] voronoi diagram of line segments
From: Simonson, Lucanus J (lucanus.j.simonson_at_[hidden])
Date: 2010-10-15 22:54:07

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.  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.  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.

Regards,
Luke