Boost logo

Boost :

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

Boost list run by bdawes at, gregod at, cpdaniel at, john at