Nearest point on a quadratic bezier curve

问题:

I am having some issues calculating the nearest point on a quadratic curve to the mouse position. I have tried a handful of APIs, but have not had any luck finding a function for this that works. I have found an implementation that works for 5th degree cubic bezier curves, but I do not have the math skills to convert it to a quadratic curve. I have found some methods that will help me solve the problem if I have a t value, but I have no idea how to begin finding t. If someone could point me to an algorithm for finding t, or some example code for finding the nearest point on a quadratic curve to an arbitrary point, I'd be very grateful.

Thanks

回答1:

I can get you started on the math. I'm not sure how quadratic Bezier is defined, but it must be equivalent to:

(x(t), y(t)) = (a_x + b_x t + c_x t^2, a_y + b_y t + c_y t^2),

where 0 < t < 1. The a, b, c's are the 6 constants that define the curve.

You want the distance to (X, Y):

sqrt( (X - x(t))^2 + (Y - y(t))^2  )

Since you want to find t that minimizes the above quantity, you take its first derivative relative to t and set that equal to 0. This gives you (dropping the sqrt and a factor of 2):

0 = (a_x - X + b_x t + c_x t^2) (b_x + 2 c-x t) + (a_y - Y + b_y t + c_y t^2) ( b_y + 2 c_y t) 

which is a cubic equation in t. The analytical solution is known and you can find it on the web; you will probably need to do a bit of algebra to get the coefficients of the powers of t together (i.e. 0 = a + b t + c t^2 + d t^3). You could also solve this equation numerically instead, using for example Newton-Raphson.

Note however that if none of the 3 solutions might be in your range 0 < t < 1. In that case just compute the values of the distance to (X, Y) (the first equation) at t = 0 and t = 1 and take the smallest distance of the two.

EDIT:
actually, when you solve the first derivative = 0, the solutions you get can be maximum distances as well as minimum. So you should compute the distance (first equation) for the solutions you get (at most 3 values of t), as well as the distances at t=0 and t=1 and pick the actual minimum of all those values.

回答2:

There's an ActionScript implementation that could easily be adapted to Java available online here.

It's derived from an algorithm in the book "Graphics Gems" which you can peruse on Google Books here.

回答3:

The dumb, naive way would be to iterate through every point on the curve and calculate the distance between that point and the mouse position, with the smallest one being the winner. You might have to go with something better than that though depending on your application.