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
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
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.
Boost list run by bdawes at acm.org, gregod at cs.rpi.edu, cpdaniel at pacbell.net, john at johnmaddock.co.uk