贝塞尔曲线路径裁剪的最佳算法是什么

Question

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

Answer 1

这是一个建议的算法。

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

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

3. 如果多边形重叠，则使用一次casteljau迭代将两条贝塞尔曲线分成两部分。如果贝塞尔曲线的大小对于所需的精度而言太小，请停止递归。否则递归地恢复步骤 2。

在分割贝塞尔曲线的过程中，跟踪您所在的位置（值t），以便您可以轻松确定剪切贝塞尔曲线的4个控制点。

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

通过此过程，您应该以被剪切贝塞尔曲线切成碎片的贝塞尔曲线结束。您仍然需要确定哪一块位于剪辑的哪一侧。