algorithm - 线剪裁到任意二维多边形

Question

如果我得到一条足够长的线段可以穿过给定的多边形，它可以是凹多边形或凸多边形。我如何找到包含在多边形中的所有相交的光段？

如果目标区域不是多边形，而是隐式曲线函数或样条曲线，怎么办？

谢谢！

Answer 1

您的问题确实没有简单的解决方案，尤其是曲线（贝塞尔曲线和样条曲线）。除了多边形剪裁的复杂性之外，重构剪裁曲线也面临着相当大的挑战（假设您希望剪裁结果保持为贝塞尔曲线和样条曲线，而不仅仅是“扁平”线近似）。

我最近发布了我的多边形裁剪库“Clipper”的 beta 更新*，它可以进行线多边形和线线裁剪（其中线也可以是曲线）。然而，虽然主库是用 Delphi、C++ 和 C# 编写的，但新的 beta 代码到目前为止只在 Delphi 中，这可能对您没有帮助。不过，如果您查看代码，您就会明白为什么我说没有“简单”的解决方案。

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

Answer 2

• 第一步：以任意顺序找到所有交点。对于多边形，您需要找到每个线段的红线和线的交点。只需求解两个线性方程组。如果解决方案受限于多边形段限制，则您有一个交集。
• 第二步：按红线上的位置对找到的点进行排序。你知道第一个和最后一个点是外部的。“外部性”随着每个点翻转 - 外-内-外等等。在两个相邻的外部点之间，您有内部线段（绿色）。编辑：不是真的......从点#0开始，段#0 - #1是内部的，下一个是外部的，下一个是内部的，依此类推。

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