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-11 16:32:45

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

OK, to me personally, sounds good.

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

Thanks for pointing relevant parts. I'll read it back to catch up.

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

I'd rather say, I'm brainstorming it or proposing but not specifically
for GSoC, because I can't get involved myself in the GSoC time frame.

I'm more thinking along this:
During reviews folks were discussing and suggesting it, so as this
subject emerged from GSoC discussions, perhaps it's a good idea to
discuss further details. And, perhaps there would be a student
interested in and capable to take it up proposing implementation.

> It sounds interesting and more a student's speed.

That's what I thought too.

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

This is a very good point. In case we start working on that, that's
seems as best appraoch.

However, as things are moving off the GSoC a bit and toward
Boost.Polygon and Boost.Geometry collaboration, I owe you explanation.

I personally think it's good and that's what Boost Community suggested.
Although, as perhaps you've noticed, I suggested Boost.Geometry related
projects for GSoC not as official proposal from BG team, but as my own
ideas. In Boost.Geometry team, we're focused on after-review tasks now.

I don't want to make any official statements and or promise you
any changes in Boost.Geometry on my own, without agreement from
Boost.Geometry team.

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

OK, it summarizes nature of the issue very well.

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

It's a good catch and a practical use case indeed.
Actually, I've been considering very same use case: processing
point clouds in compressed form. That would be indeed an obstacle
in such situations.

I'd like to see this issue addressed in Boost.Geometry myself.

> Other examples are presumptions of polygon winding direction known at
>  compile time based on object type and last vertex of polygon 
> duplicates first vertex.

I assume, you mean in Boost.Geometry. I'm not sure how this could
be fixed really.

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

I'll forward this and the following points to the BG mailing list.

> Assumed "closed" polygon with redundant last vertex. Exterior ring 
> and hole rings assumed to be same type.

I suppose this "padlock" is a kind of inheritance from
geospatial domains. We have got used to it pretty well in GIS :-)

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

Yes, as I mentioned I support this idea.

> No assumptions about member functions (even if stl standard) for 
> accessing data, and adaptor traits instead, or at least the option 
> for adaptors instead.

I'm not sure I get this point well. I don't see it solved that way
in Boost.Polygon.

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

Ouch! :-) Open polygon is quite well against the fundamental concepts
in Boost.Geometry. It may be a limitation, but there is variety of types
in BG, so users can support their problems well.

However, I understand that this stays in contradiction with
principles of Boost.Polygon. Considering Boost.Polygon as a user of
Boost.Geometry, then it's clear that boost::geometry::polygon does not
meet the user's (BP's) requirements, thus boost::geometry::linestring
should be used.,

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

Yes, I'm getting now much better picture of the differences
between the two library.

> I think my proposed changes are each an improvement to the design of 
> the Boost.Geometry concepts interface because they make it more 
> generic.

I see they are differences. However, I don't see these differences
in terms of bad and good choices. I understand well that specifying the
requirement of closed polygon is a bad choice in terms of concepts of
Boost.Polygon. Though, one may argue that open polygon is a bad choice.

To me, it's not black and white, thus I don't agree with the statement
that "are each improvement".

> To the greater extent my suggestions can be implemented in a way that
>  doesn't break existing usage of the Boost.Geometry library.

I'm sure it's feasible, programmatically. What disturbs me, however,
changing principle semantics of current design by dropping the winding
requirement and closed vs open polygon are

> I hope that you do consider them.

Personally, I am considering it. I can't give any promises on behalf of
the whole Boost.Geometry project team.
I'm keen to discuss it with Barend and Bruno, so I will forward our
discussion to BG list.

Luke, thank you for your all the clarifications you've provided.

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