# Closest point to polynomial curve? (or spline)

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

## 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 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 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 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.

1. 1
Rutin
29
2. 2
3. 3
4. 4
5. 5

• 13
• 13
• 11
• 10
• 14
• ### Forum Statistics

• Total Topics
632961
• Total Posts
3009485
• ### Who's Online (See full list)

There are no registered users currently online

×