Faster concaveman with delta pointset?

[Desperado17]

Greetings,

I use the C++ version of concaveman to calculate concave hulls on 2d point sets of size 100000. This takes about 20 seconds for me, so I think about how to speed it up.

My question is: If you have two point sets that only differ in a small set of points, can the underlying algorithm use this information to speed up subsequent calculations?

Regards

[sadaszewski]

You could do it but you would need to modify the source code. The idea is very simple, to build the rtree with common points once and then copy it to subsequent calls, adding the delta point sets each time. Look at src/main/cpp/concaveman.h#L569. Also, since concaveman-cpp delegates hull computation to the user, you might have to figure out how to recycle hull computations as well, depending on how much they affect the performance.

[Desperado17]

Unfortunately I cannot modify external sourcecode due to our auditing policies...

[sadaszewski]

Then you would have to fork it and make it internal source code ;) The license is quite permissive.

[Desperado17]

Ah this would yield all soirt of additinoal problems.

Btw: Do you know if there is a concave hull algorithm that is faster than the point algorithm if the points are nodes on a graph? Think intersections on a road map.

[Desperado17]

Oh, and what influence do duplicate points have on performance?