在一个点上分割一个三次贝塞尔曲线

Question

这个问题和这个问题都展示了如何在参数值0≤t≤1处沿着曲线将立方Bezier曲线分割成两个新段来组成原曲线形状。我需要在我已知坐标但不知道该点参数化的情况下，将我的Bezier曲线分割。

例如，考虑Adobe Illustrator，用户可以单击曲线以将点添加到路径中，而不影响路径的形状。

假设我找到了与用户点击位置最接近的曲线上的点，那么怎么计算控制点呢？是否有一个公式可以根据给定曲线上的点来分割Bézier曲线？

或者（不太理想的方式），给定曲线上的一个点，是否有一种方法可以确定对应于该点的参数化值t（除了使用二分搜索中的De Casteljau算法）？

---

我的Bézier曲线只存在于2D空间，但是一个好的答案会包括适用于任意维度的向量数学。

- Phrogz

---

据我所知，贝塞尔曲线可以表示为矩阵，您可以将参数值代入其中并获得坐标，理论上您可以计算出逆矩阵并使用它。 - Will Ness

寻找曲线上最接近的点需要确定 t 值。 - MBo

准确地找到最近的点并不简单，因为它需要在2D中解决一个6阶多项式。但是你也可以在屏幕空间中完成它。当你绘制曲线时，将相应的t值绘制到一个单独的缓冲区中。然后，你只需要进行屏幕空间的最近点搜索，就可以立即知道参数了。顺便说一句，在参数上进行二分查找也行不通，因为三次曲线中的坐标不是单调的。 - Nico Schertler

@NicoSchertler 我怀疑二分查找会失败，但我不得不尝试一下。是的，在许多地方都不完美。在我的情况下，另一个人（Web 浏览器 SVG）正在绘制曲线，所以我必须自己绘制它来找到最接近的点。问题是，SVG 坐标并不总是像素，因此我必须仔细选择我的 marching size 来平衡性能和精度。感谢您的意见。好消息是：一旦我使用这种方法找到了位置，我还将使用 t 值进行拆分。 - Phrogz

我建议你阅读Pomax关于贝塞尔曲线的全面书籍，可能《交点和根查找》一章会帮助你理解四次曲线：https://pomax.github.io/bezierinfo/#intersections。然而，我认为使用de Casteljau算法和二分查找可能更适合任何次数的贝塞尔曲线。 - karatedog

Answer 1

可以确定曲线上某点的参数值，而不使用De Casteljau's算法，这可能更简单，但您将需要使用启发式来找到一个好的起始值，并类似地逼近结果。

一种可能的且相对简单的方法是使用牛顿法，如下所示：

t_n+1 = t_n - ( b_x(t_n) - c_x ) / b_x'(t_n)

其中，b_x(t)指的是多项式形式的某个贝塞尔曲线的x分量，具有控制点x₀，x₁，x₂和x₃，b_x'(t)是一阶导数，c_x是曲线上的一个点，满足以下条件：

c_x = b_x(t) | 0 < t < 1

b_x(t)的系数为：

A = -x₀ + 3x₁ - 3x₂ + x₃
B = 3x₀ - 6x₁ + 3x₂
C = -3x₀ + 3x₁
D = x₀

并且：

b_x(t) = At³ + Bt² + Ct + D,
b_x'(t) = 3At² + 2Bt + C

现在找到一个好的起始值插入到牛顿法中是棘手的。对于大多数不包含环或尖点的曲线，您可以简单地使用以下公式：

t_n = ( c_x - x_0 ) / ( x_3 - x_0 ) | x_0 < x_1 < x_2 < x_3

现在您已经有了：

b_x(t_n) ≈ c_x

因此，应用一次或多次牛顿法迭代将更好地近似c_x的t。

请注意，Newton Raphson算法具有二次收敛性。在大多数情况下，一个好的起始值将在两次迭代后产生可忽略的改进，即小于半个像素。

最后值得注意的是，立方贝塞尔曲线通过寻找一阶导数的根来精确解决查找极值问题。因此，有问题的曲线可以在其极值处进行细分，以消除环或尖点，然后通过分析所得到的部分来获得更好的结果。以这种方式细分立方体将满足上述约束条件。

- Nolo