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-10 18:47:12

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

Initially, I was thinking about the latter option. However, I think that
for BG (Boost.Geometry) geometry types instantiated with integer,
it would make sense to call implementations from BP (Boost.Polygon).
At least, shortly after GSoC delivers those algorithms for BP,
with parametrized interfaces, then perhaps they would be
applicable to integer-based geometries from BG straight away.

> Both are the sort of thing I would like to support.

Sounds as an ideal target.

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

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

Yes, that's probably the option to go if implemented in BG.
Though, speaking of SoC, it may be a problem for student to switch
between the two libraries, BP and BG.

Are you thinking of MA implementation for discrete space in Boost
Polygon or you mean pushing this functionality to BG completely?

(I don't have in-depth knowledge about possible/best algorithmic
solutions for MA myself)

> 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 r 
> esults in SFINAE if absent.  That is all easy enough.

Sound good.

In case that BG applies algorithms from BP to integer-based geometries,
it would be nice to be able to pass BP algorithm as strategy.

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

Does it mean that, basically, BG is missing the concept of isotropy
and associated properties? Perhaps you've already explained this issue
in details on the list, so I can just scan the archives, haven't you?

> That would make integrating a Boost.Geometry algorithm into the 
> Boost.Polygon interface awkward.

Sound like the other way around should be easier to achieve, right?
Perhaps that would be a good direction to go for GSoC project.

> Specifically I would prefer not to require STL container semantics 
> for the data stored in a geometry object.

It's availability or adaptability to this semantic is one of the
fundamental of types in BG. It seems the significant difference
lies down here.

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

I'm not sure that's correct. OK, at the deep end BG does require
geometry to look & feel like standard containers, but it does not
require geometry to be actual standard container.

Wouldn't it be possible to address this issues with adapters?

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

I can't speak for the rest of the team. We would need to discuss it.
Could you list conflicts you've observed so far and give overview of
required changes? It Perhaps it would be easier to analyse it.

I have to admit, I have not yet evaluated Boost Polygon regarding
such adaption, so I may be missing some significant details still.
I hope I'll catch up during further discussions.

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