将线段裁剪到任意2D多边形内

Question

如果我有一条足够长的线段可以穿过一个凸多边形或凹多边形，那么如何找到所有包含在该多边形内的相交光线段？

如果目标区域不是多边形，而是一个隐式曲线函数或样条曲线，应该如何处理？

谢谢！

- Buzz

Answer 1

你的问题并没有简单的解决方案，特别是涉及到曲线（beziers和splines）时更加复杂。除了多边形剪辑的复杂性之外，还存在重建剪切曲线的巨大挑战（假设您希望剪辑结果保持为beziers和splines而不仅仅是“平坦”的线条近似）。我最近发布了我的多边形剪辑库“Clipper”的beta更新*，它可以进行线-多边形和线-线剪辑（其中线也可以是曲线）。然而，尽管主要库是用Delphi、C++和C#编写的，但新的beta代码目前只有Delphi版本，可能对您没有帮助。不过，如果您查看代码，您会明白为什么我说没有“简单”的解决方案。

• 编辑于2011年7月15日：这个“更新”从未超出这个beta版本，并且现在只是一个“概念验证”。它现在基于我Clipper库的旧版本，需要进行重大改写才能得以维护和扩展。（在某个阶段，我可能会重新审视它，但目前我打算进一步改进核心库。）尽管如此，这个“概念验证”的Delphi代码可以在这里下载。

- Angus Johnson

---

谢谢。你用了哪种方法进行曲线裁剪？ - Buzz

我采用的方法最初是将曲线展平（并标记每个展平的段），因为剪切算法仅适用于直线。一旦找到交点，标记的段用于识别曲线子段（de Casteljau算法）。然后，只需重新应用de Casteljau算法到原始曲线上，但仅适用于包含交点的曲线部分。这样说清楚了吗？ - Angus Johnson

我很感兴趣看到这个功能（特别是线多边形裁剪）被添加到Clipper库中（包括C#翻译）。 - Redwood

你好，这个算法是否包含在您最新版本的Clipper中？ - azer89

它是用C#演示的。但是，它目前正在进行重大修改，因此希望在下一个Clipper更新中会有变化。 - Angus Johnson

抱歉，我找不到它，我想实现线和多边形的交点测试，并提取每个连接组件，这可能吗？在上面的图像中，我应该得到4个组件。 - azer89

Answer 2

• 第一步：找到所有交点，顺序不限。对于多边形，需求出红线和每个线段的交点。只要解决两个线性方程组的问题。如果解被约束在多边形线段范围内，则存在交点。
• 第二步：按照位置在红线上的顺序对已找到的点进行排序。你知道第一个和最后一个点是外部点。每个点都会改变“外部-内部-外部”的状态。在相邻的两个外部点之间，你有内部线段（绿色）。编辑：不准确...从点＃0，线段＃0开始，＃1是内部，下一个是外部，下一个又是内部，如此类推。

如果区域不是多边形，而是由某个隐式函数给出的，则需要找到该函数等于红线的位置（具体方法取决于函数）。

- alxx

---

如何排序？找到坐标最低的点，并按照到该点的距离对所有其他点进行排序。 - alxx

这是一个已知的问题，可能有很多解决方案。尝试搜索“线多边形相交”。 - alxx

第一个绿色交点是内部的吗？第二个绿色交点是外部的吗？ - Buzz

我用错了词。这些点不是内部/外部的，第一条绿色点之间的线段是内部的，下一个是外部的，以此类推。 - alxx

你需要小心使用这种方法，因为如果直线与多边形的顶点相交，你会看到两个点，而不是一个。由于浮点数精度问题，它们也可能没有完全相同的值。 - Drew Noakes