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

Subject: [ggl] Proposal for Delauney triangulation algorithm
From: Barend Gehrels (barend)
Date: 2011-10-25 20:24:58

Hi John,

On 25-10-2011 21:43, John Swensen wrote:
> 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.

I understand that it is not that easy. First, I understand that you 
categorize Delauney as simplify, but I don't think that makes it easier. 
We (also internally) had difference about the border between strategy 
and algorithm, and sometimes it is just not that easy.

In this case, the simplify of a polygon (one polygon) might result in a 
multipolygon of sometimes maybe 10000 polygons, so it is more simple to 
render, but in other aspects it is much more complex. So personally I 
would not consider this as a case of simplify. In the GIS world simplify 
is often known as generalization, omitting points (or even polygons) 
from a shape.

Further, though the geometry-concepts are relatively easy to use, 
designing a strategy-concept is way more difficult. I would not 
certainly start with that approach, also not if I would do it myself. 
There are many algorithms in Boost.Geometry without strategies, and for 
some it might be that they will not come at all. The pattern is that 
there is an overload without strategy, and sometimes one with a 
strategy, so starting without is a convenient apporach, we can always 
add an overload later without breaking the interface.

So I would start with just a new algorithm, no strategy, and using 
geometry-concepts. This would (I think) also be the most straightforward 
port of the existing algorithm.

Does this help?

Regards, Barend