一个简单的多边形交集algorithm

我正在寻找一个非常简单的algorithm来计算多边形相交/裁剪。 也就是说，给定多边形P ， Q ，我希望find包含在P和Q多边形T ，并且希望在所有可能的多边形中T是最大的。

我不介意运行时间（我有几个非常小的多边形），我也可以得到近似的多边形的交点（即一个多边形less点，但仍然包含在多边形的交集）。

但是对于我来说algorithm是简单的（更便宜的testing），最好是短的（更less的代码）。

编辑：请注意，我想获得一个多边形代表交集。 对于两个多边形是否相交的问题，我不需要布尔型的答案。

Answer 1

我了解原始海报正在寻找一个简单的解决scheme，但不幸的是，真的没有简单的解决scheme。

尽pipe如此，我最近创build了一个开源免费软件剪辑库（用Delphi，C ++和C＃编写），用于剪辑各种多边形（包括自相交）。 这个库很简单： http : //sourceforge.net/projects/polyclipping/ 。

Answer 2

您可以使用“ 多边形裁剪”algorithm来查找两个多边形之间的交点。 然而，当考虑所有的边缘情况时，这些往往是复杂的algorithm。

Weiler-Atherton可以使用你喜欢的search引擎寻找多边形裁剪的一个实现。 维基百科关于Weiler-Atherton的文章

Alan Murta完全实现了一个多边形裁剪器GPC 。

编辑：

另一种方法是首先将每个多边形分成一组更容易处理的三angular形。 Gary H. Meisters的Two-Ears定理可以做到这一点。 McGill的这个页面在解释三angular形细分方面做得很好。

Answer 3

如果您使用C ++，并且不想自己创buildalgorithm，则可以使用Boost.Geometry 。 它使用了上面提到的Weiler-Athertonalgorithm的改进版本。

Answer 4

你没有给我们你的多边形表示。 所以我select（更像是build议）一个为你:)

将每个多边形表示为一个大的凸多边形，以及从该大的凸多边形中需要“减去”的较小的凸多边形的列表。

现在给出两个多边形的表示forms，你可以计算交点为：

计算大凸多边形的交点形成交点的大多边形。 然后“减去”所有较小者的交集，得到一个被划分的多边形列表。

你得到一个新的多边形遵循相同的表示。

由于凸多边形的交点很容易，所以这个交点也应该很容易。

这似乎是应该起作用的，但我并没有就正确性/时间/空间的复杂性给予更深入的思考。

Answer 5

这是一个基于三angular测量的方法，它非常简单，可以在O（N ² ）中运行。

顺便说一句，O（N ² ）是最适合这个问题的。 设想两个多边形形状像干草叉刀片相交成直angular。 每个都有一些与尖齿数量成正比的分段; 交点中的多边形数量与尖齿数量的平方成正比。

1. 首先，对每个多边形进行三angular剖分。

2. 将来自P的所有三angular形与来自Q的所有三angular形进行比较以检测交点。 任何一对相交的三angular形可以被分解成更小的三angular形，每个三angular形都在P中，在Q中或在交集中。 （无论你在步骤1中使用什么，都可以重复使用来帮助解决这个问题。）只保留交叉点中的三angular形。

3. 计算每个三angular形的邻居，通过两两比较，并build立一个邻接图。 该图将包含P和Q交点中每个多边形的一个连接子图。

4. 对于每个这样的子图，select一个三angular形，走到边缘，然后绕过边缘，产生边界相应输出多边形的线段。

Answer 6

这是一个简单而愚蠢的方法：input时，将多边形离散化为位图。 交叉和位图在一起。 为了生成输出多边形，请绘制位图的锯齿边界，并使用多边形逼近algorithm平滑锯齿。 （我不记得这个链接是否给出了最合适的algorithm，这只是第一个Google命令，你可能会检查出其中的一个工具，将位图图像转换为向量表示，也许你可以在不重新实现algorithm的情况下调用它们？）

我认为，最复杂的部分是寻找边界 。

早在九十年代初，我在工作中遇到类似这样的问题。 我把它弄糊涂了：我想出了一个（完全不同的）algorithm，它可以处理实数坐标，但是面对浮点（和噪声input）的实际情况，它似乎陷入了一个完全无法解决的过度情况， 。 也许在互联网的帮助下，我会做得更好！

Answer 7

我没有很简单的解决scheme，但这里是真正algorithm的主要步骤：

1. 为多边形顶点和边做一个自定义双链表。 使用std::list将不会执行，因为您必须自己交换下一个和上一个指针/偏移量，以便在节点上进行特殊操作。 这是简单的代码的唯一方法，这将会给予良好的性能。
2. 通过比较每对边来find交点。 请注意，比较每一对边将给出O（N 2）时间，但将algorithm改进为O（N·logN）将很容易。 对于某对边（例如a→b和c→d），通过使用在边a→b上由t 8 = d 0 /（d 0 -d 1）给出的参数（从0到1）其中d 0是（ca）×（ba），d 1是（da）×（ba）。 ×是二维交叉乘积，如p×q =pₓ·qᵧ-pᵧ·qₓ。 findtₐ后，find交点就是用它作为段a→b上的线性插值参数：P = a +tₐ（ba）
3. 拆分每个边添加段相交的顶点（和链接列表中的节点）。
4. 那么你必须跨越交点处的节点。 这是您需要执行自定义双链表的操作。 您必须交换一些下一个指针（并相应地更新以前的指针）。

然后你就得到了多边形相交parsingalgorithm的原始结果。 通常情况下，您需要根据每个地区的圈数select一些地区。 search多边形匝数来解释这一点。

如果你想从这个O（N²）算出一个O（N·logN）algorithm，你必须做同样的事情，除了你在一个行扫描algorithm中做。 寻找Bentley Ottmanalgorithm 。 内部algorithm将是相同的，唯一的区别是你将有一个减less的边缘比较，在循环内。

Answer 8

我的工作方式是一样的问题

1. 将多边形分割成线段
2. 使用IntervalTrees或LineSweepAlgo查找相交线
3. 使用GrahamScanAlgofind一个封闭的path来find一个封闭的path与相邻的顶点
4. 交叉引用3.与DinicAlgo解散它们

注意：由于多边形有一个共同的顶点，我的情况是不同的。 但希望这可以帮助

Answer 9

这可能是一个巨大的近似值取决于你的多边形，但是这里有一个：

• 计算每个多边形的质量中心。
• 计算多边形每个点到质心的最小或最大或平均距离。
• 如果C1C2（其中C1 / 2是第一个/第二个多边形的中心）> = D1 + D2（其中D1 / 2是您为第一个/第二个多边形计算的距离），则这两个多边形“相交”。

虽然这应该是非常有效的，因为对多边形的任何变换以与质心相同的方式应用，并且中心节点距离可以仅被计算一次。