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