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

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

Hi Luke,

On 20-10-2011 22:21, Simonson, Lucanus J wrote:
> -----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.

Right, I was not clear enough. We get rid of double's, but not yet of 
all robustness problems. I agree, for that you have to do (sometimes 
much) more than that.

>
>> 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.
>
About bringing the libraries more together, I agree and would like that. 
But I don't think Boost.Geometry should depend on Boost.Polygon, because 
of compilation on different platforms and other things (don't remember 
the details but there are platforms on which Boost.Polygon could not be 
used, is that still the case?).

I agree that maintaining two versions is not a good idea, so wrapping 
the Voronoi with interfaces sounds as a good approach. I've seen 
screenshots and a presentation on Andrii's work but don't know the details.

Regards, Barend