Hello Community,
is there a method of defining something that roughly resembles a curve and allows to rapidly find the nearest point on the curve to another point?
Bezier curves unfortunately do not meet that criteria because you need an iterative algorithm to find nearest.
Unfortunately I need this for a special image preprocessing and have to perform a nearest-point calc for about half a million pixels/points against about a dozen short curves. With parallel burst and just finding nearest points on a dozen lines, it leads to ~100ms calculation time. Don’t wanna exceed this by more than a magnitude if possible.
The only thing that comes to mind is representing the curve as a circle segment. That enforces point-symetric curves, but it’d be fast at least.
Any other ideas?
Huge thanks 
Would a Catmull-Rom Spline be good enough?
If you are doing the nearest point calculation from a lot (most) pixels in an image have you consider inverting the problem: instead of starting from pixels and looking up nearest point on curve, start with curve and fill whole 2d image with information about from which curve point you reached it first.
Dijkstra like floodfill with priority queue should work. Since you probably want nearest point based on euclidean distance in straight line, instead of shortest path between neighbor pixels the correctness arguments of Dijkstra algorithm doesn’t quite apply. But since there are no obstacles it should still produce correct result.
Depending on the quality of curve you need and amount of points. You could split the curve into short discrete segments and then use some of the existing spacial query structures like k-d tree too lookup nearest segment. And afterwards if necessary fine tune the result by finding the nearest point in specific segment, thus avoiding to iterate through whole curve path. Somewhat similar you can split the curve into points and then create voronoi diagram from those points.
As far as I see the solution for nearest distance isn’t easier/faster for catmull-rom splines, is it?
@karliss_coldwild
Interesting approach! Will have to think about that, thank you.
The priority queue floodfill approach wouldn’t parallelize well (which can be fine depending on your needs and exact input sizes). But after thinking about it a bit, that reminded me the “jump flooding” algorithm which achieves similar thing but can be parallelized even for gpu level of parallelism.