• Create Account

## Closest point to polynomial curve? (or spline)

Old topic!

Guest, the last post of this topic is over 60 days old and at this point you may not reply in this topic. If you wish to continue this conversation start a new topic.

3 replies to this topic

### #1Fuza  Members

122
Like
0Likes
Like

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)

### #2StealthNinja  Members

163
Like
0Likes
Like

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.

### #3Zipster  Members

1717
Like
0Likes
Like

Posted 01 November 2007 - 06:11 PM

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.

### #4grhodes_at_work  Members

1377
Like
0Likes
Like

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.

Graham Rhodes Moderator, Math & Physics forum @ gamedev.net

Old topic!

Guest, the last post of this topic is over 60 days old and at this point you may not reply in this topic. If you wish to continue this conversation start a new topic.