search

sadaszewski / concaveman-cpp

C++ port of mapbox's JS concaveman, with a Python wrapper
BSD 2-Clause "Simplified" License
153 stars 41 forks source link

Faster concaveman with delta pointset? #20

Open Desperado17 opened 2 years ago

Desperado17 commented 2 years ago

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 commented 2 years ago

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 commented 2 years ago

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

sadaszewski commented 2 years ago

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

Desperado17 commented 2 years ago

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 commented 2 years ago

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