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

No.

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

     http://www.boost.org/doc/libs/1_49_0/libs/graph/doc/bundles.html

Regards,  Phil.