在分段立方贝塞尔路径中插入点的算法

Question

我正在寻找一种算法来在贝塞尔曲线上插入一个新的控制点，而不变形。

有人知道贝塞尔算法(插入、优化、de Casteljau ...)的库或引用资料吗？

Answer 1

这称为“结插入问题”。对于贝塞尔曲线，de Casteljau 算法会给你正确的答案。这是 3 阶贝塞尔曲线的简单算法。

假设您要在 P0、P1、P2、P3 定义的贝塞尔曲线内的参数空间的分数 t 处插入一个结。以下是您的操作:

P0_1 = (1-t)*P0 + t*P1
P1_2 = (1-t)*P1 + t*P2
P2_3 = (1-t)*P2 + t*P3

P01_12 = (1-t)*P0_1 + t*P1_2
P12_23 = (1-t)*P1_2 + t*P2_3

P0112_1223 = (1-t)*P01_12 + t*P12_23

然后您的第一个贝塞尔曲线将定义为:P_0、P0_1、P01_12、P0112_1223；您的第二个贝塞尔曲线定义为:P0112_1223、P12_23、P2_3、P3。

几何解释很简单:在分数 t 处拆分贝塞尔多边形的每个线段，然后将这些拆分点连接到一个新的多边形中并进行迭代。当你只剩下 1 个点时，这个点位于曲线上，前一个/下一个分割点形成前一个/下一个贝塞尔多边形。同样的算法也适用于更高阶的贝塞尔曲线。

现在，如果您不希望将控制点插入到 t 的特定值处，而是在空间中的特定位置处，它可能会变得更加棘手。就个人而言，我在这里要做的只是对接近所需分割点的 t 值进行二进制搜索...但是如果性能很关键，您可能会找到更快的分析解决方案。