Re: [boost] [SoC] Summer of Code Project Ideas -- Polygon

Subject: Re: [boost] [SoC] Summer of Code Project Ideas -- Polygon
From: Simonson, Lucanus J (lucanus.j.simonson_at_[hidden])
Date: 2010-03-09 19:11:17

Andrew Sutton wrote:
> I'm officially soliciting ideas for student projects for this year's
> 2010 Summer of Code.
...
> ==Extensions for Existing Libraries==
> There are a number of Boost libraries that are very amenable to
> extension (e.g., BGL, GIL, Math, etc.). Basically any library that
> doesn't have a finite feature space. Non-intrusive changes (i.e.,
> those that don't require hacking on the existing bits) typically make
> good summer of code projects. 
...
> If you have any ideas, let's hear them. And remember, funded projects
> need mentors.

2D medial axis, veronoi diagrams and delaunay triangulation are three classical problems in computational geometry.  Veronoi diagrams are well known to be the dual graph of delaunay triangulation, so if you solve one you have solved the other.  Medial axis is also related to the other two because it can also be solved with sweepline.  All three could be solved by a single generic-parameterized implementation of a sweepline algorithm.  These problems are difficult to solve primarily due to numerical robustness challenges.  If we limit the scope of the problem to inputs with integer coordinates only the numerical robustness challenge is much reduced.  I'd be willing to mentor a student to work on solving these classical computational geometry problems as an extension to the features provided by my Boost.Polygon library.  This would be a natural extension on the existing functionality provided by Boost.Polygon (it came up during review to ask if I planned on implementing them.)  Since my library already provides algorithms that require integer coordinates it is acceptable to me to have extensions with that limitation.  I don't believe it is reasonable to expect a student to solve the floating point versions of these problems (with an efficient implementation) in a single summer, but for integer coordinates a strong student could succeed with some expert guidance. 

If the project produces something of value I would be willing to take on responsibility for maintaining it if the student loses interest.

Regards,
Luke