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

Subject: [ggl] Proposal for Delauney triangulation algorithm
From: Simonson, Lucanus J (lucanus.j.simonson)
Date: 2011-10-20 18:02:36

-----Original Message-----
From: ggl-bounces_at_[hidden] [mailto:ggl-bounces_at_[hidden]] On Behalf Of Barend Gehrels
Sent: Thursday, October 20, 2011 12:54 PM
To: Generic Geometry Library Discussion
Subject: Re: [ggl] Proposal for Delauney triangulation algorithm

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

As I tried to explain before, you cannot simply throw a big number type such as ttmath at voronoi diagram to make it numerically robust because the sqrt introduces an irrational.  The idea that making the coordinate datatype a template parameter is sufficient to make a computational geometry algorithm numerically robust just doesn't pan out and isn't practical even if it did because the constant factor overhead can be 50 to 100X slower than built-in types.

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

Andrii's implementation should be released as part of Polygon soon.  He has been making steady progress.  I don't think we need to port it to Boost.Geometry (implies forking) and we wouldn't want to maintain two version of the code.  Instead we ought to be able to wrap it with interfaces that require Boost.Geometry concepts rather than Boost.Polygon concepts.  The core algorithm doesn't really rely on Boost.Polygon data types and could be used in an extension to Boost.Geometry that introduces a dependency on the algorithm in the Polygon details.  In general we want to start building bridges and this could be a good next step in the process of bringing the two libraries closer together.

Regards,
Luke