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 20:42:17

Mateusz Loskot wrote:
> Simonson, Lucanus J wrote:
>> 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 was thinking of MA implementation for discrete space in Boost.Polygon with the potential that a floating point MA algorithm might be added to BG at some future point and we would want them to interoperate reasonably well.  In other words either library's interface ought to be able to provide access to both algorithms, and conversely, both algorithms should be easily integratable into either interface.

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

No, isotropy is not a factor in compatibility since the adaptor is trivial.  I've explained these issues in the past, but the volume of communication from me in the archives may overwhelm your search.  You can focus on my feedback during the review of Boost.Geometry, but I provided similar feedback in each preview of the library.
 
>> 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.

Yes, the other way around would be easier to achieve.  Are you proposing a GSoC project to provide adaptors for Boost.Polygon algorithms to Boost.Geometry geometry concepts?  It sounds interesting and more a student's speed.  I think, however, that this effort might require some interaction between the authors of the two libraries and it is better for us to interact directly and do the work ourselves rather than put a third party in the middle because there may be some changes to the libraries themselves.  Ideally we should work together on this sort of thing before we release the interfaces in an official boost release and make breaking changes to the interfaces harder to introduce.

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

It may be possible, but I very carefully chose the word practical in my statement above.  It is more than just syntactical differences related to member function names of stl containers, but semantical differences that are troublesome.  Non-const reference to data stored in a geometry object is something I avoided in the design of my concepts.  Consider a polygon that stores its geometry data in a compressed format that provides lazy iterator decompression and accepts an iterator pair for compression.  How do I provide non-const references to objects that model point concept to satisfy the interface of polygon concept for this kind of data structure?  Other examples are presumptions of polygon winding direction known at compile time based on object type and last vertex of polygon duplicates first vertex.
 
>> 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.

Problems I'm aware of that in adapting Boost.Polygon interfaces to Boost.Geometry algorithms:

Non-const references to data members for interior_type.
Stl container syntax for data access for interior_type.
Assumed winding direction of polygon and holes known at compile time.
Assumed "closed" polygon with redundant last vertex.
Exterior ring and hole rings assumed to be same type.

What I would like to see:

Value semantics for access to data stored in geometry objects with direct access implemented as an optimization for data types that provide it.
No assumptions about member functions (even if stl standard) for accessing data, and adaptor traits instead, or at least the option for adaptors instead.
A trait for getting the winding direction at run time.
Handle both "open" and "closed" polygons of the same type.
Provide hole_ring_type that defaults to ring type but can be overridden.

My wish list touches on many of the traits of the Polygon concept and implicit assumptions (documented of course) about data types that model it, which would require changes to algorithms and not just interfaces.  

I think my proposed changes are each an improvement to the design of the Boost.Geometry concepts interface because they make it more generic.  To the greater extent my suggestions can be implemented in a way that doesn't break existing usage of the Boost.Geometry library.  I hope that you do consider them.

Thanks,
Luke