贝塞尔路径剪切的最佳算法是什么？

Question

我知道两种通用的算法，Greiner-Hormann和Vatti。它们适用于多边形。我想在贝塞尔路径上实现布尔运算。我想扩展这些算法以适用于贝塞尔路径。但这是一个数值问题。如何最好地剪裁贝塞尔路径？（以及如何最好地修改Greiner-Hormann算法以适用于任意多边形（具有自交））

- LmTinyToon

---

我知道安迪·芬内尔的文章。但是这种方式不好。 - Alex Aparin

贝塞尔曲线的阶数是多少？2还是3？您对哪种裁剪感兴趣？垂直和水平？在曲线上的特定点？ - chmike

我对立方贝塞尔曲线很感兴趣。可以通过任意贝塞尔路径进行裁剪。 - Alex Aparin

你想将一个贝塞尔曲线与另一个相交吗？这听起来对我来说是一个非常棘手的数学问题。 - Mark Ransom

我想通过另一组贝塞尔曲线序列来剪裁贝塞尔曲线序列。 - Alex Aparin

Answer 1

这里是一个建议的算法：

1. 使用四个控制点来确定一个多边形，该多边形包围了贝塞尔曲线。

2. 测试多边形重叠，以查看两条贝塞尔曲线是否可能有交点。如果没有重叠，则无需剪裁，完成操作。

3. 如果存在重叠，使用一个Casteljau迭代将两条贝塞尔曲线分成两部分。如果贝塞尔曲线的大小与所需精度相比太小，则停止递归。否则继续执行步骤2。

在分割贝塞尔曲线的过程中，要记录你所处的位置（值t），这样可以轻松确定被裁剪的贝塞尔曲线的4个控制点。

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

通过此过程，您应该得到一条被剪切的贝塞尔曲线的多个片段。您仍需要确定每个片段位于剪切的哪一侧。

- chmike

---

我不理解你的回答。我想在贝塞尔路径上实现布尔运算。你给了我查找贝塞尔曲线交点的算法。 - Alex Aparin

我从以上文章中采用了这个术语。 - Alex Aparin

参考：http://davis.wpi.edu/~matt/courses/clipping/ 因此，您需要找到交点。另一种解决方案是使用Casteljau分解将贝塞尔曲线近似为多边形。当四个控制点几乎对齐时，您停止递归。然后使用多边形裁剪。 - chmike

我给你提供了两个贝塞尔曲线之间找到交点的算法。要找到自我交点，需要将贝塞尔曲线分成两半，并使用两个部分应用算法。在三次贝塞尔曲线中只能有一个自我交点。这是解决方案的前半部分。另一半是选择构成裁剪后贝塞尔序列的贝塞尔段。这类似于多边形裁剪。 - chmike

我试图去实现，但你的算法真的很差。它不能处理触摸点。它也没有关于正确输出拓扑的一些关键字。 - Alex Aparin