二次贝塞尔曲线上最近的点

Question

二次贝塞尔曲线上最近的点

3

我在计算鼠标位置到二次曲线上最近的点时遇到了问题。我尝试过几个API，但都没有找到可行的函数。我找到了一个适用于5阶三次贝塞尔曲线的实现方法，但我没有数学技巧将其转换为二次曲线。如果我有t值，我可以使用一些方法来解决问题，但我不知道如何开始找t值。如果有人能够指导我查找t的算法或提供有关在任意点上查找二次曲线上最近点的示例代码，我将非常感激。

谢谢

- matt

很可能，你找到的用于五次曲线的实现也可以在二次曲线上不做任何修改就能工作。 - toto2

3个回答

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- jkraybill · Answer 1

有一个 ActionScript 实现可以很容易地适应 Java，在这里可以在线获取。

它源自于书籍《图形宝典》中的算法，您可以在 Google Books 这里阅读。

- toto2 · Answer 2

我可以帮你开始数学部分。我不确定二次贝塞尔曲线是如何定义的，但它必须等价于：

(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个常数。

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

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

由于您想要找到最小化上述量的t，因此您将其相对于t进行了一阶导数，并将其设置为0。这给出了以下结果（省略sqrt和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 的三次方程。已知解析解，可以在网上找到；你可能需要做一些代数运算来将 t 的各个幂的系数放在一起（即 0 = a + b t + c t^2 + d t^3）。你也可以使用例如牛顿-拉弗森法等数值方法来解决这个方程。

但请注意，如果没有任何一个解在你的范围内 0 < t < 1，那么只需计算在 t = 0 和 t = 1 时的距离值（第一个方程），并选择其中较小的一个。

编辑:
实际上，当你解第一导数为零时，得到的解既可以是最大距离，也可以是最小距离。因此，你应该计算你得到的解（最多 3 个 t 值）的距离（第一个方程），以及在 t=0 和 t=1 时的距离，并选择所有这些值中的实际最小值。

- Jon Martin · Answer 3

愚蠢、天真的方法是遍历曲线上的每个点，并计算该点与鼠标位置之间的距离，最小的距离将成为胜者。但根据您的应用程序，您可能需要采用更好的方法。