Andrii Sydorchuk wrote:
It does seem to create a triangulation as you can see here: http://chezphil.org/tmp/delaunay.png
I would also appreciate if you post your system configuration, number of input points on that image and time it took to construct Delaunay triangulation.
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 certainly similar. 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. Regards, Phil.