Re: [boost] [Review Request] Inclusion of the Boost.Polygon Voronoi Library

Subject: Re: [boost] [Review Request] Inclusion of the Boost.Polygon Voronoi Library
From: Phil Endecott (spam_from_boost_dev_at_[hidden])
Date: 2012-04-14 06:26:56

Andrii Sydorchuk wrote:
>> It does seem to create a triangulation as you can see here:
>>  http://chezphil.org/tmp/delaunay.png
>
> I would also appreciate if you post your system configuration, number of
> input points on that image and time it took to construct Delaunay
> triangulation.

There are about 2e5 input points and 6e5 output edges, and generation 
takes about 35 seconds on a 1.2GHz Marvell Feroceon 88FR131 (a QNAP 
TS-119) using g++ version 4.4.2 -O3.

It needs to be quite a lot faster than that, but it's not a bad start 
:-)  I don't have exactly equivalent numbers for s-hull, but it is 
certainly similar.

My main performance concern is the overhead of doing O(log N) lookup to 
get from the output vertices back to the corresponding input points.  I 
will also need to investigate how much RAM is needed.

Some sort of incremental mode could also be useful as I currently think 
I will need to do 3 iterations.

Regards,  Phil.