Jump to content

  • Log In with Google      Sign In   
  • Create Account

We need your feedback on a survey! Each completed response supports our community and gives you a chance to win a $25 Amazon gift card!


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.

  • You cannot reply to this topic
3 replies to this topic

#1 Fuza   Members   -  Reputation: 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)

Sponsor:

#2 StealthNinja   Members   -  Reputation: 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.

#3 Zipster   Crossbones+   -  Reputation: 886

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.

#4 grhodes_at_work   Moderators   -  Reputation: 1361

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.



PARTNERS