math - 多边形相交的简单算法

Question

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

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

但对我来说，算法很简单（更便宜的测试）并且最好是短的（更少的代码）对我来说真的很重要。

编辑：请注意，我希望获得一个代表交叉点的多边形。对于两个多边形是否相交的问题，我只需要一个布尔答案。

score 66 · Accepted Answer

我了解原始发布者正在寻找一个简单的解决方案，但不幸的是，确实没有简单的解决方案。

不过，我最近创建了一个开源免费软件剪辑库（用 Delphi、C++ 和 C# 编写），它可以剪辑各种多边形（包括自相交的多边形）。这个库使用起来非常简单：http: //sourceforge.net/projects/polyclipping/。

score 18 · Accepted Answer

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

Weiler-Atherton是您可以使用您最喜欢的搜索引擎查找的一种多边形裁剪实现。维基百科关于 Weiler-Atherton 的文章

Alan Murta 有一个完整的多边形裁剪器GPC实现。

编辑：

另一种方法是先将每个多边形分成一组三角形，这样比较容易处理。Gary H. Meisters的双耳定理可以解决问题。McGill的这个页面很好地解释了三角形细分。

score 15 · Accepted Answer

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

score 6 · Accepted Answer

你没有给我们你的多边形表示。所以我正在为你选择（更像是建议）一个:)

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

现在给定该表示中的两个多边形，您可以将交集计算为：

计算大凸多边形的交集以形成交集的大多边形。然后“减去”两者中所有较小的交叉点，以获得一个已分割多边形的列表。

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

由于凸多边形相交很容易，因此这种相交查找也应该很容易。

这似乎应该有效，但我没有对正确性/时间/空间复杂性进行更深入的思考。

score 4 · Accepted Answer

这是一种简单而愚蠢的方法：在输入时，将多边形离散化为位图。相交，将位图和在一起。要生成输出多边形，请绘制位图的锯齿状边界，并使用多边形近似算法对锯齿状进行平滑处理。（我不记得那个链接是否给出了最合适的算法，它只是谷歌的第一个命中。您可以查看其中一个将位图图像转换为矢量表示的工具。也许您可以在不重新实现算法的情况下调用它们?)

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

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

score 0 · Accepted Answer

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

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

然后你就有了多边形相交解析算法的原始结果。通常，您会希望根据每个区域的缠绕数选择一些区域。搜索多边形绕组数以获得对此的解释。

如果你想从这个 O(N²) 算法中创建一个 O(N·logN) 算法，你必须做完全一样的事情，除了你在行扫描算法内部做。寻找Bentley Ottman 算法。内部算法将是相同的，唯一的区别是您将在循环内部减少要比较的边数。

score 0 · Accepted Answer

我解决同样问题的方式

将多边形分成线段
IntervalTrees使用或查找相交线LineSweepAlgo
查找闭合路径GrahamScanAlgo用于查找具有相邻顶点的闭合路径
交叉参考 3. 用DinicAlgo溶解它们

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

score 0 · Accepted Answer

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

这将为您提供一组凸多边形，以便它们的并集恰好是您的起始多边形的交集。

score 0 · Accepted Answer

如果多边形未对齐，则它们必须对齐。我会通过找到多边形的中心（X 中的平均值，Y 中的平均值）然后通过矩阵变换增量旋转多边形，将点投影到轴之一并使用最小 stdev 的角度来对齐形状（你也可以使用主成分）。为了找到交点，一个简单的算法将定义一个点网格。对于每个点，维护一个多边形或另一个多边形或两者（联合）内的点数（有简单快速的算法，例如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);
}

score -2 · Accepted Answer

根据您的多边形，这可能是一个巨大的近似值，但这是一个：

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

不过，这应该非常有效，因为对多边形的任何变换都以相同的方式应用于质心，并且中心节点距离只能计算一次。

math - 多边形相交的简单算法

10 回答 10

Related

Reference