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-10 13:37:08

Mateusz Loskot wrote:
> 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 ?

Are you proposing using the algorithms in Boost.Polygon with interfaces in Boost Geometry, or allowing similar algorithms implemented in Boost Geometry to be used with Boost.Polygon interfaces?  Both are the sort of thing I would like to support.  I don't provide a "strategy" argument for calling algorithms.  I select the algorithm to invoke for a given function call based on the conceptual type of the geometry passed into the function.  For cases where this doesn't uniquely identify an algorithm I use different function names to call different algorithms.  I expect that if a medial axis implementation were available in Boost.Geometry it would implement a floating point based algorithm for floating point coordinates.  I could add in the ability to select that algorithm based on the coordinate traits of the coordinate type used in the geometry argument.  I would have to add a "float_like" trait to the coordinate traits that selects the Boost.Geometry algorithm if present and results in SFINAE if absent.  That is all easy enough.  The trouble I would run into is if Boost.Geometry doesn't provide polygon concept interfaces that support the full range of polygon data types supported by the Boost.Polygon concept interfaces.  That would make integrating a Boost.Geometry algorithm into the Boost.Polygon interface awkward.  Specifically I would prefer not to require STL container semantics for the data stored in a geometry object.  The practical implication of such a requirement is only data structure that provide public access to data members that are stl containers can model the geometry concept.  The only reasonable way to interoperate with such an interface is data copy conversion.  If your project is considering changing the concept interfaces I'd be interested in reviewing those design decisions so that I can provide feedback on the implications for interoperability with Boost.Polygon.

Regards,
Luke