Started by Nov 01 2007 04:07 PM

,
3 replies to this topic

Posted 01 November 2007 - 04:07 PM

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)

Posted 01 November 2007 - 04:22 PM

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.

Posted 01 November 2007 - 06:11 PM

The curve is the set of all points [x, Ax^{3}+Bx^{2}+Cx+D] over your target domain. The target point is [u, v]. You want to minimize the squared-distance function (x - u)^{2} + (Ax^{3}+Bx^{2}+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.

Posted 01 November 2007 - 06:33 PM

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.

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