给定一点，求其在三次贝塞尔曲线上的最近点

Question

我有一个由A，B，C，D定义的三次贝塞尔曲线。其中A是起点，B和C是控制点，D是终点。我知道如何在任何值t（其中0 <= t <= 1）处找到位置，以及通常的概念，因为它只使用少量调用线性插值函数的结果即可得出曲线。（可以在维基百科 这里 在Higher-order curves标题下方轻松可视化）

现在我想找到曲线上距离空间中某一点P最近的点。谷歌给了我多个讨论，但没有一个能让我的大脑“嗡嗡作响” 。实际上，说实话，它们都超出了我的理解范围。我的数学知识可能比我想象的要有限得多，并且在提到导数时就会失去意义。

以下是谷歌带我去的一些地方：

gamedev.net

stackoverflow.com (二次方程)

stackoverflow.com (接近但我不懂)

除了一个我无法再找到的ActionScript实现外，我知道我在这里的某个答案/评论中找到过它...

有人有耐心和知识帮助我理解这些信息吗？ 我正在考虑采用“足够接近”的方法，并在非常小的步骤中迭代曲线上的最接近点。 这将很慢，精度会降低。 在我特定的情况下，速度比精度更少是一个问题，但是我觉得有一种方法可以同时拥有两者...

提前致谢。

- Tim Beaudet

---

这个链接是否相关？看起来像是PostScript中的一个实现。 - harold

你选择了一个相当复杂的问题，而且没有使用推导来解释。我甚至怀疑这个问题是否可以以数学上正确的方式解决：我认为它涉及到求解五次方根，而且没有闭合公式可以计算（http://en.wikipedia.org/wiki/Quintic_equation#Finding_roots_of_a_quintic_equation）。因此，进行近似可能是你能做的最好的事情。 - cmaster - reinstate monica

我之前研究过这个问题，但是没有任何收获。显然，近似值是我们能做到的最好的。 - BonzaiThePenguin

@BlackBird 在飞机上还是在3D中？ - 4pie0

我技术上更喜欢3D，但我想它也可以在平面上工作吧？实际的实现是一个赛车赛道，所以自然会有山丘和倾斜。目前我倾向于采用蛮力方法，尽管我对此还是很好奇的。 - Tim Beaudet

Answer 1

正如cmaster所说，这导致需要解决一个五次方程以找到一个六次方程的最小值。

无论是二维还是三维都不重要。需要最小化的函数是一个六次方程。

f(t)=0.5*dot(p(t)-X,p(t)-X) such that 0<=t<=1

在这里，X代表给定的点，p(t)代表多项式曲线，dot表示欧几里得标量积。通过找到导数的所有根，可以实现最小化。

f'(t)=dot(p'(t), p(t)-X)

通过比较根的函数值和区间端点处的函数值，在区间内寻找最小值的方法。

还存在一些不使用导数的最小化方法，主要用于比多项式更复杂的函数。例如参见Brent, R. P. (1973) 的第5章。该书详细涵盖了导数和泰勒多项式的部分内容。该方法或其主要思想也可以在《Numerical recipes》中找到，称为"黄金分割搜索"。

- Lutz Lehmann