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

Subject: [ggl] Proposal for Delauney triangulation algorithm
From: John Swensen (jpswensen)
Date: 2011-10-28 03:17:41

On Oct 25, 2011, at 4:26 PM, Barend Gehrels wrote:

> 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
> 

That did help a lot.  I think I am kindof getting the hang of it.  I at least have the algorithm, dispatch, and detail in place such that things are called properly when applied to different geometries.  I kindof decided against trying to use the poly2tri code exactly, but instead reimplement their modification of the line sweep Delauney triangulation.  I am mostly just following their documentation and referring to their code when I need some clarification.  This has seemed a lot easier than trying to munge their code exactly.

That being said, I have a few questions:
1) What is the appropriate way to split a polygon?  In the detail portion of the algorithm, in the specialization for polygon, it would be easiest to define portions of the Ranges for the exterior and interior ranges to be combined to make a new polygon.  Maybe this isn't possible, but would be interested in an example of this if one exists.

2) Return types for algorithms.   Is the approach taken in the union_ algorithm the correct approach to get one geometry in and another geometry (or better said a multi_geometry) out?

I know I could figure these things out if I mess around enough (and will in the meantime), but little tips here and there sure help me learn faster.

John