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 14:02:56

Hi Andrii,

Andrii Sydorchuk wrote:
>> 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.

Correction: those numbers are correct, but the PNG that I linked before
is for approximately 1/4 of that data.

> I am wondering if this also includes image generation time.


> On my nettop
> with an Intel Celeron U3400 1.07 GHz, g++ 4.4.1 it takes around 3-4 seconds
> and on my PC with i5-7600 2.8 GHz, g++ 4.6.1 just 0.6 seconds.

Try it on your phone.

>> It needs to be quite a lot faster than that, but it's not a bad start :-)
> Actually it's already very fast.

Please compare it with q-hull and s-hull, and perhaps with whatever
CGAL offers.

> By performance, construction of Voronoi
> diagram of 2e5 input points is equivalent to insertion of 2e6 pair<int,
> int> into std::set. So I guess your result of 35 seconds is very
> architecture specific or hides some details.

I'm not hiding anything; I posted most of the code. But this test was
not constructed as a benchmark, so don't read too much into it.

I suspect that the main difference between this test system and yours
is the cache size.

>> 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.
> As I mentioned I could expose index of the site event within the initial
> input set, thus this will require O(1) time.

Have a look at how Boost.Graph does "bundled properties":

Regards, Phil.

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