线裁剪为任意二维多边形

Question

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

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

谢谢！

Answer 1

真的没有一个简单的解决方案来解决您的问题，特别是曲线（贝塞尔曲线和样条曲线）。除了多边形裁剪的复杂性之外，重构修剪曲线还有相当大的挑战（假设您希望裁剪结果保持为贝塞尔曲线和样条曲线，而不仅仅是“平展”线条近似）。

我最近发布了一个测试更新*到我的多边形剪裁库'Clipper'，它可以做线多边形和线条剪裁（线条也可以是曲线）。然而，虽然主要的库是用Delphi编写的，但是C＃& C＃，新的beta代码到目前为止只在Delphi中可能不会帮助你。不过，如果你看看代码，你会明白为什么我说没有'简单'的解决方案。

• 编辑2011年7月15日： 此“更新”从来没有超过这个beta版本，现在简单的“证明了概念”。它现在基于我的Clipper库的旧版本，并且需要进行重大修改才能维护和扩展。 （在某个阶段，我可以重温它，但我目前正在进一步完善核心库的意图。）不过，这个“证明了概念” Delphi代码可以下载here

Answer 2

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

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