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

Subject: [ggl] Proposal for Delauney triangulation algorithm
From: John Swensen (jpswensen)
Date: 2011-10-25 19:39:21

On Oct 23, 2011, at 4:49 AM, Barend Gehrels wrote:

> Hi John,
> 
> On 23-10-2011 2:01, John Swensen wrote:
>> 
>> 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)?
>> 
> 
> Good question. There are different kind of concepts:
> 1) concepts for geometries (followed and used by all geometries in the library)
> 2) concepts for strategies (followed by some)
> 
> We're now talking about the first, the concepts for geometries. That means that, e.g., you should not use point.x() but geometry::get<0>(point) instead.  This makes sure that any point type (provided it fulfils the concepts) can be used. The same for linestrings but that is as a range, so it is just using the boost::range algorithms. And for polygons, and that uses geometry::exterior_ring() and geometry::interior_rings() and further ranges as well. For multi-geometries it is also all ranges.
> 
> So it is not really difficult. It is somewhere in that paper we wrote (available on <http://trac.osgeo.org/ggl/wiki/BoostCon>, the 2010 one) , but there it is more worked out from design perspective and not from user perspective. Maybe a good idea once.
> 
> Regards, Barend
> 

Sorry for still being a little dense.  I went and read through the two papers and looked at the presentation slides from 2010 and still have a few questions.

1) I see how the concepts allow the specific type of geometric object for an algorithm to be arbitrary given in adheres to a set of concepts.  What I don't see is where in an algorithm or algorithm+strategy that the set of concepts is defined.
2) There is already a simplify algorithm with the Douglas Peucker as a strategy.  Is the Delauney triangulation not just a "simplify" algorithm with a different output?
        a) Does there need to be a new concept, algorithm, and strategy created to properly implement the Delauney triangulation?
                or
        b) Can the Delauney triangulation just be implemented as a new strategy for the simplify algorithm?
3) I guess I am trying to wrap my head around what the appropriate additional files I need to add to "do this right".  
        a) Is it a new concept+new algorithm+new strategy.
        b) Is there a good example in the code base of something that was added that is similar in structure to 

I guess my biggest problem is I still don't understand fully the generic programming and the exact relationship between the hierarchy of concept/algorithm/strategy.  I will read the 2010 paper again and keep looking at the source code, but any direction you could give me would help me out a lot.

John