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)
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.
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.
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.
Graham Rhodes Moderator, Math & Physics forum @ gamedev.net