一个简单的多边形相交算法

Question

我正在寻找一种非常简单的算法来计算多边形的交/裁剪。

即，给定多边形P，Q，我希望找到包含在P和Q中的多边形T，并且我希望T是所有可能多边形中最大的。

我不介意运行时间（我只有几个非常小的多边形），我也可以承受多边形交的近似解（即具有更少点数但仍包含在多边形交中的多边形）。

但对我来说真正重要的是算法要简单（测试便宜），最好是短小精悍的代码。

编辑：请注意，我希望获得代表交集的多边形。我不仅需要两个多边形是否相交的布尔答案。

- Elazar Leibovich

---

多边形是凸多边形还是非凸多边形？如果不是凸的话，它们的交集就不一定是一个多边形。 - DNNX

@DNNX 如果它们是凸多边形，那就容易了。但它们不是凸的，我希望能找到表示交集的所有多边形。 - Elazar Leibovich

你看过这个问题吗？你的问题不完全相同，因为你在询问实现的简单性。但是提到的一些库可能会满足你的需求... https://dev59.com/gnI_5IYBdhLWcg3wF_F3 - Eric

Answer 1

我理解原帖的作者正在寻找一个简单的解决方案，但不幸的是，真的没有简单的解决方案。

尽管如此，我最近创建了一个开源免费剪切库（用Delphi、C++和C#编写），可以剪切所有类型的多边形（包括自交多边形）。这个库使用起来非常简单：https://github.com/AngusJohnson/Clipper2

- Angus Johnson

---

我不久前也得出了这个不幸的结论。每个解决方案都是令人痛苦的复杂。感谢这个库！ - Elazar Leibovich

或许我还应该提一下，我的Clipper库与其他剪裁库相比也非常优秀：http://angusj.com/delphi/clipper.php#features - Angus Johnson

@angus johnson 如果要进行简单的测试，以确定一个多边形是否与另一个相交或者是否完全包含在其中，你会使用什么？ - GorillaApe

@AngusJohnson，你的库支持计算两个开放路径的交点吗？谢谢。 - sendreams

更新自2018年: Polyclipping已被更名为Clipper，并可作为NuGet软件包使用。 - Manfred Radlwimmer

你好@AngusJohnson，有没有一个剪切多边形和折线的算法？我正在尝试找到一种剪切多边形和折线的方法。 - Lake_Lagunita

Answer 2

你可以使用多边形裁剪算法来找到两个多边形之间的交集。然而，当考虑到所有边缘情况时，这些算法往往会变得复杂。

你可以使用你喜欢的搜索引擎查找 Weiler-Atherton，它是多边形裁剪的一种实现。Weiler-Atherton 的维基百科文章 Alan Murta 拥有一个完整的多边形裁剪器 GPC。

另一种方法是首先将每个多边形分成一组三角形，这样更容易处理。Gary H. Meisters 的“Two-Ears Theorem”就能解决问题。麦吉尔大学的页面对三角形细分进行了很好的解释。

- Doug Ferguson

---

我在谷歌上搜索了多边形裁剪，并找到了相关结果。但请注意，这些算法旨在高效、精确和复杂。我想要一个慢一点、可能是近似的简单算法。 - Elazar Leibovich

我也希望有一种简单易用的方法。人们可以想象，如果通过API公开了更原始的几何操作，WPF和GDI+会执行通常有用的剪切。当一个程序从简单开始时，随着考虑到那些困难的边缘情况，它会变得更加复杂。 - Doug Ferguson

Answer 3

如果您使用C++，并且不想自己创建算法，您可以使用Boost.Geometry。它使用了上述Weiler-Atherton算法的改进版本。

- Barend

Answer 4

您没有给出多边形的表示方法。所以我为您选择（更像是建议）一种：将每个多边形表示为一个大凸多边形和需要从该大凸多边形“减去”的小凸多边形列表。

现在，给定该表示中的两个多边形，可以计算它们的交集如下： 计算大凸多边形的交点，形成交集的大多边形。 然后从两者的所有小多边形的交点“减去”，得到减去多边形的列表。您将获得遵循相同表示法的新多边形。由于凸多边形交点容易计算，因此这个交点查找也应该很容易。这似乎应该有效，但我还没有深思熟虑其正确性/时间/空间复杂度。

- Aryabhatta

---

哇！这恰好是我所想的，但：（1）多边形表示为CW段系列，将其转换为凸-凸非常棘手。（2）在减去第一个凸多边形后，得到了一个非凸形状，我需要处理它，而且我不确定从多边形中减去凸是比找到两个多边形之间的交点更容易... - Elazar Leibovich

@Elazar：将线段表示转换为凸 - 凸形式，您可以执行以下操作：1）形成凸包。2）对于凸包的每条边，如果它不在内部，则可以找到一个非凸多边形需要减去。然后，您可以“三角化”此非凸多边形以获得凸形状的集合。关于您提到的第二点：如果使用该表示法，实际上无需执行任何实际减法。我想，对于凸包+“三角剖分”，应该已经有包可以做到这一点。 - Aryabhatta

该算法在以下评论中的“叉子刀片以直角相交”的例子上会失败。具体来说，它会错过应该添加到每个叉子横杠旁边的切口。 - ees

实际上，该算法需要减去两个形状中所有较小的多边形，而不是它们的交集。不过您可能想要将它们与新的外壳相交。 - fishinear

Answer 5

这里有一个简单且愚蠢的方法：在输入时，将多边形离散化为位图。要求交集，将位图进行“与”操作。要生成输出多边形，请跟踪位图的锯齿边界并使用多边形逼近算法平滑锯齿（我不确定该链接是否提供了最合适的算法，它只是谷歌搜索的第一个结果。您可以尝试一下已有的工具，将位图图像转换为矢量表示。也许你可以调用它们而无需重新实现算法？）。

我认为最复杂的部分将是跟踪边界。

顺便说一下，在90年代初，我在工作中遇到过类似的问题。我搞砸了：我想出了一个（完全不同的）算法，可以处理实数坐标，但在面对浮点数（和嘈杂的输入）的现实时，似乎遇到了无法修复的大量退化情况。也许有了互联网的帮助，我会做得更好！

- Darius Bacon

---

追踪边界可能会更容易，如果你意识到每个顶点要么是多边形的顶点，要么是每个多边形的线段的交点。 - Mark Ransom

Answer 6

如果多边形没有对齐，则必须对齐。我会通过找到多边形的中心（X轴平均值，Y轴平均值），然后通过矩阵变换逐步旋转多边形，将点投影到其中一个轴上，并使用最小标准差的角度来对齐形状（也可以使用主成分）。要找到交点，一个简单的算法是定义一个点网格。对于每个点，维护在一个多边形内、另一个多边形内或两个多边形内（联合）的点数计数（有简单且快速的算法可用，例如http://wiki.unity3d.com/index.php?title=PolyContainsPoint）。计算多边形1和多边形2的点数，除以多边形1或多边形2中的点数，就可以粗略地（取决于网格采样）估计多边形重叠的比例。交集面积将由与AND操作相对应的点给出。

例如：

function get_polygon_intersection($arr, $user_array)
{
    $maxx = -999;  // choose sensible limits for your application
    $maxy = -999;
    $minx = 999;
    $miny = 999;
    $intersection_count = 0;
    $not_intersected = 0;
    $sampling = 20;
    
    // find min, max values of polygon (min/max variables passed as reference)
    get_array_extent($arr, $maxx, $maxy, $minx, $miny);
    get_array_extent($user_array, $maxx, $maxy, $minx, $miny);
    
    $inc_x = $maxx-$minx/$sampling;
    $inc_y = $maxy-$miny/$sampling;
    
    // see if x,y is within poly1 and poly2 and count
    for($i=$minx; $i<=$maxx; $i+= $inc_x)
    {
        for($j=$miny; $j<=$maxy; $j+= $inc_y)
        {
            $in_arr = pt_in_poly_array($arr, $i, $j);
            $in_user_arr = pt_in_poly_array($user_array, $i, $j);
            
            if($in_arr && $in_user_arr)
            {
                $intersection_count++;
            }
            else
            {
                $not_intersected++;
            }
        }
    }
    
    // return score as percentage intersection
    return 100.0 * $intersection_count/($not_intersected+$intersection_count);
}

- ejectamenta

Answer 7

我解决同样问题的方式：

1. 将多边形分解为线段
2. 使用IntervalTrees或LineSweepAlgo找到相交的线段
3. 使用GrahamScanAlgo找到相邻顶点的闭合路径
4. 将步骤3与DinicAlgo进行交叉引用以消除它们

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

- Ansh David

Answer 8

我没有非常简单的解决方案，但以下是真正算法的主要步骤：

1. 为多边形的顶点和边创建一个自定义的双向链表。不能使用std::list，因为你必须自己交换节点的下一个和上一个指针/偏移量以进行特殊操作。这是保持代码简单的唯一方法，并且可以提供良好的性能。
2. 通过比较每对边来找到交点。注意，比较每对边将需要O(N²)的时间，但之后将很容易改进算法为O(N·logN)。对于某对边（例如a→b和c→d），交点是通过在边a→b上使用参数（从0到1）来找到的，该参数由tₐ=d₀/(d₀-d₁)给出，其中d₀是(c-a)×(b-a)，d₁是(d-a)×(b-a)。×是二维叉乘，例如p×q=pₓ·qᵧ-pᵧ·qₓ。找到tₐ后，使用它作为线性插值参数在线段a→b上找到交点：P=a+tₐ(b-a)
3. 在相交的地方添加顶点（和链表中的节点）来分割每条边。
4. 然后，你必须在交点处交叉节点。这就是你需要创建自定义双向链表的操作。你必须交换一些next指针（并相应地更新previous指针）。

然后您将得到多边形相交解决算法的原始结果。通常，您会根据每个区域的绕数选择一些区域。搜索“多边形绕数”以了解其说明。

如果您想将此O（N²）算法转换为O（N·logN）算法，则必须完全相同地执行此操作，只是在线扫描算法内部执行。搜索“Bentley Ottman算法”。内部算法将是相同的，唯一的区别是您将比较的边数减少，在循环内部。

- Dom

Answer 9

如果您不关心可预测的运行时间，可以尝试先将多边形分割为凸多边形的并集，然后成对计算子多边形之间的交集。

这将给您一组凸多边形，使它们的并集恰好是起始多边形的交集。

- afiori

Answer 10

这可能会根据多边形的不同而有很大的近似，但以下是一种可行的方法:

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

尽管如此，由于对多边形的任何变换都同样适用于重心，因此这种方法应该非常高效，只需要计算一次中心节点距离。

- Sylvestre Equy

---

如何获得表示交集区域的多边形？ - Elazar Leibovich