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

Subject: Re: [boost] [SoC] Summer of Code Project Ideas -- Polygon
From: Mateusz Loskot (mateusz_at_[hidden])
Date: 2010-03-09 20:21:36

Simonson, Lucanus J wrote:
> 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.

Luke, these are indeed very good ideas for SoC projects I think.

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

Would it make sense for you to consider designing parametrized
interface of these algorithms, that later could be shared with
potential implementation provided by Boost Geometry ?

Best regards,
-- 
Mateusz Loskot, http://mateusz.loskot.net
Charter Member of OSGeo, http://osgeo.org