Geometry Boost List: [ggl] Proposal for Delauney triangulation algorithm

Subject: [ggl] Proposal for Delauney triangulation algorithm
From: John Swensen (jpswensen)
Date: 2011-10-22 20:15:13

On Oct 20, 2011, at 3:53 PM, Barend Gehrels wrote:

> Hi John, Bruno, Andrii, Luke, List,
> 
> On 19-10-2011 14:18, John Swensen wrote:
>> On Oct 19, 2011, at 8:07 AM, Bruno Lalande wrote:
>> 
>>> Hi John,
>>> 
>>> Ii could be interesting.
>>> 
>>> First, have you checked that the license used by this library is compatible with what you want to do?
>>> 
>>> Second, not sure you get well what implementing a Boost.Geometry algorithm really is about. You're talking about replacing the classes in the library (point, polygon) by the ones provided by Boost.Geometry. But that's not the point: the purpose of Boost.Geometry algorithms is to be able to work on any data type, as long as it meets some requirements. So basically your algorithm will not know/use geometries from Boost.Geometry directly, but its concepts. You'll have to use all the metafunctions and other mechanisms that allow us to manipulate our data through concepts and not directly. Was this your intention?
>>> 
>>> Regards
>>> Bruno
>> I guess maybe I don't understand the architecture of Boost.Geometry very well.  How do you differentiate between algorithms that only work on polygons or only work on sets of points (using the term "algorithm" loosely here to describe the mathematical definition rather than the Boost.Geometry definition)?  Or do operations that are specific to a very specific instantiation of a template not belong in Boost.Geometry?
>> 
>> I was proposing to create a class that takes a  model::polygon or  model::multi_polygon (regardless of the point type) and performs Delauney triangulation on the polygon(s) and spits out a  model::multi_polygon containing the resulting triangles as model::polygon's.  Does such a thing belong in Boost.Geometry or does it not fit the paradigm of having an operation work on any data type?  If it doesn't fit into Boost.Geometry, then I can easily just start a github project for the purpose of "algorithms" that operate on Boost.Geometry objects but don't meet the generic-ness requirements.  Either way is fine with me, but let me know.
>> 
>> John
>> 
>> P.S. It is BSD license and the two core maintainers think it is an awesome idea._______________________________________________
> 
> I think too that this is an awesome idea.
> 
> About the plan above, I agree with Bruno that it is indeed better to use the concepts and not the model::polygon itself. That is slightly more complex, but if you get the idea it is perfectly doable. Well, that is if it should be part of Boost.Geometry, if it is for your own purpose of course you can use model::polygon. It sounds af their implementation is pretty comparable.
> 
> If it uses the concept, it gets automatically rid of double's (Andrii's first conclusion). We have to be careful with comparisons indeed. About the complexity, second conclusion, we probably have to investigate more.
> 
> I don't know the status of Andrii's Voronoi implementation, what is the status of it? Will it be included in Boost.Polygon? And when? Is it possible to port it to a Boost.Geometry based implementation? Is someone interested in porting this?
> 
> So in short we've two (or more) possibilities now...
> 
> Thanks for all input.
> Regards, Barend

I don't quite understand the "concept" concept.  I looked through the sources and looked at the boost documentation on concepts and have a rough idea.  Should I create a new "concept" called the divide_simplify_concept.hpp in boost/geometry/strategies/concepts?  Then the implementation of this will do different things for different models (e.g.  Bezier curves for linestrings, triangles, for polygons, etc)?

I guess my questions is what is the appropriate concept for simplifying a geometry by breaking it up in simpler pieces (of the same or different geometry)?

John