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.