Hi I was wondering if it was possible to get the closest point to another point across a bezier curve? If so, how? If not, why not? Thanks,

---

"If you gaze long into an abyss, the abyss will gaze back into you." - Friedrich Nietzsche (1844-1900) (my site)

Does this help?

http://www1.acm.org/pubs/tog/GraphicsGems/gems.html#gems
(Schneider, Philip J., Solving the Nearest-Point-on-Curve Problem, p. 607-611, code: p. 787-796, NearestPoint.c.)

Also, search google groups for: "distance from a point to a bezier curve"

Author, "Real Time Rendering Tricks and Techniques in DirectX", "Focus on Curves and Surfaces"

[edited by - CrazedGenius on January 7, 2003 12:35:31 AM]

It is certainly possible. There is some point closest or set of points equidistance. As far as finding it one way is to use the fact that a line from a point to the closest point on a curve is orthogonal to the curve. You can derive a formula for the tangent vector to the curve and you also have a formula for the curve itself. The point minus the formula for the curve is a vector equation for a displacement vector from the curve to the point. The tangent vector equation is a quadradic and the displacement vector equation is a cubic. When their dot produce, a sixth order polynomial, is zero then you have a candidate for being the closest point.

Finding the roots of a sixth order polynomial can only be done numerically in the general case. That gives you six values of the parameter some of which may be complex and most likely some will be. You then have to plug the real ones back into the original equation to find the candidate points, calculate the distance for each and take the smallest one. So while possible it may not be practical depending upon what you are doing.

As far as practical though you could most likely just check the points matching parameter values of 0, .1, .2, ... , 1 and see which is closest. Then say is is .4 check .3 and .5 to see which is closer. If it was .5 then check .41, .42, ... , .49 and repeat the process until you are close enough. Since you generally don''t draw the curve for a parameter value less than zero or greater than one you most likely just want the point on the segment closest rather than the point on the curve closest. If you are doing something graphically or a similation for a game then who is going to know it isn''t really the closest point. Oh, no, it should have been 1/100th of a pixel to the right. The scale will certainly matter. Within .1 on the parameter for a bezier curve with an arc length of a couple of thousand pixels isn''t going to look too good. Also how radical the curve is will matter was well. A very long curve with a very small loop might be very apparently wrong without a high degree of precision. It just doesn''t seem that if you are using a bezier to model something that you are likely to use a real radical curve.

So being right to a high degree of precision could be very computationally complex, but you should be able to get close enough without anything extreme.