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