二次贝塞尔曲线上的最近点 [英] Nearest point on a quadratic bezier curve

问题描述

我在计算鼠标位置的二次曲线上的最近点时遇到了一些问题。我已经尝试了一些API，但是没有运气找到一个有效的功能。我找到了一个适用于5度三次贝塞尔曲线的实现，但我没有数学技能将其转换为二次曲线。我发现一些方法可以帮助我解决问题，如果我有一个t值，但我不知道如何开始找到t。如果有人可以指向我找到t的算法，或者用于找到二次曲线上最近点到任意点的一些示例代码，我将非常感激。

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.

谢谢

推荐答案

我可以让你开始数学。
我不确定如何定义二次Bezier，但它必须等于
到：

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),

其中 0< t< 1 。 a，b，c是定义曲线的6个常数。

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

你想要到（X，Y）的距离：

You want the distance to (X, Y):

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

由于您希望找到最小化上述数量的 t ，您可以使用
相对于 t 的一阶导数，并设置为等于0.
这给你（丢弃sqrt和因子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) 

这是吨。分析解决方案是已知的，您可以在网上找到它;你可能需要做一些代数来一起得到 t 的幂的系数（即0 = a + b t + c t ^ 2 + d t ^ 3）。您也可以使用例如Newton-Raphson以数字方式求解此等式。

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.

但是请注意，如果3个解决方案中没有一个可能在您的范围内 0< t< 1 。在这种情况下，只计算在 t = 0 和 t = 1 并取两者的最小距离。

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.

编辑：

实际上，当你解决一阶导数= 0，你得到的解是最大距离和最小距离。所以你应该计算你得到的解的距离（第一个等式）（最多3个值 t ），以及 t的距离= 0 和 t = 1 并选择所有这些值的实际最小值。

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.

这篇关于二次贝塞尔曲线上的最近点的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！