algorithm - 贝塞尔路径裁剪的最佳算法是什么

Question

我知道 Greiner-Hormann 和 Vatti 的两种常用算法。他们使用多边形。我想在贝塞尔曲线路径上实现 bool 运算。我想扩展这些算法以使用贝塞尔曲线路径。但这是数值问题。贝塞尔路径裁剪的最佳方法是什么？ (以及 Greiner-Hormann 算法对任意多边形(具有自相交)的最佳修改是什么)

Answer 1

这是一个建议的算法。

1. 使用四个控制点确定包围贝塞尔曲线的多边形。

2. 测试多边形重叠以查看两条贝塞尔曲线是否可能有交点。如果不重叠，我们就完成了，不需要剪裁。

3. 如果多边形重叠，使用一次 casteljau 迭代将两条贝塞尔曲线一分为二。如果贝塞尔曲线的大小相对于所需的精度来说太小，则停止递归。否则从第 2 步递归恢复。

在划分贝塞尔曲线的过程中，跟踪你所在的位置(t值)，这样你就可以很容易地确定裁剪贝塞尔曲线的4个控制点。

请注意，在某些点上，贝塞尔曲线可能会近似于一条直线。在这种情况下，重叠测试和拆分会更快。

在这个过程中，您应该以通过剪切贝塞尔曲线切割成碎片的贝塞尔曲线结束。您仍然需要确定哪一 block 位于剪裁的哪一侧。