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