Sign in to follow this  

Closest point to polynomial curve? (or spline)

This topic is 3729 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Recommended Posts

Suppose we have a curve Ax^3 + Bx^2 + Cx + D where x is in the range [0,1]. Is there any way to mathematically find the closest point along the curve to a given point? (This is for a cubic spline - I want to be able to find the closest point on a spline to another point)

Share this post


Link to post
Share on other sites
Use a numeric method to optimize x for the shortest squared distance from <x, y> to your point. I came up with one for a problem like this once, but it's not actually guarantied to converge; I think it only worked for me by luck. I'll write it out if no-one responds with anything better.

Share this post


Link to post
Share on other sites
The curve is the set of all points [x, Ax3+Bx2+Cx+D] over your target domain. The target point is [u, v]. You want to minimize the squared-distance function (x - u)2 + (Ax3+Bx2+Cx+D - v)2. We can tell from inspection that there isn't going to be a closed-form analytical solution - it's a degree-6 polynomial, and its derivative is a degree-5 polynomial. So you'll need to use a numerical approach to solve the problem, something like Newton-Raphson.

Share this post


Link to post
Share on other sites
One way to approximate the solution is to discretize the curve into a polyline, then find the nearest point to each linear segment, and from among all those choose the nearest. Some problems with this approach are: 1) of course, loss of accuracy, though it can give a starting point for an iterative refinement; and, perhaps more problematic, 2) the discretization might produce a candidate solution that is pretty far off from the real solution...you might end up on a completely different part of the curve due to geometric errors between the real curve and the polyline.

The more segments, the closer you can potentially get, but a large # of segments can take more time to do the search. So, even for this simple problem, can potentially be beneficial to introduce spatial partitioning...use a Kd-tree or similar to help cull out segments that are not in the closest neighborhood to the point.

Share this post


Link to post
Share on other sites
Sign in to follow this