一种简单的多边形求交算法

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

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

但对我来说，算法简单(测试成本更低) ，最好是短(代码更少) ，这一点非常重要。

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

132230 次浏览
小开

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

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

尽管如此，这应该是非常有效的，因为任何对多边形的转换都以非常相同的方式应用于质量中心，而且中心-节点距离只能计算一次。

小开

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

多边形裁剪的一个实现是 维勒-阿瑟顿.关于维勒-阿瑟顿的维基百科文章，您可以使用您喜欢的搜索引擎来查找它

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

编辑:

另一种方法是首先将每个多边形划分为一组三角形，这样比较容易处理。加里 · H · 迈斯特斯的 双耳定理完成了这个魔术。这个 呼叫麦吉尔很好地解释了三角形的细分。

小开

你还没有给我们一个多边形的表示。所以我选择(更像是建议)一个给你:)

将每个多边形表示为一个大的凸多边形，并从该大的凸多边形中“减去”一组较小的凸多边形。

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

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

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

由于凸多边形求交很容易，所以这种求交也应该很容易。

这看起来应该是可行的，但关于正确性/时间/空间复杂性，我还没有进行更深入的思考。

小开

这里有一个简单而愚蠢的方法: 在输入时，将多边形离散化为一个位图。相交，并将位图放在一起。要生成输出多边形，需要描绘出位图的锯齿边界，并使用 多边形近似算法平滑锯齿边界。(我不记得这个链接是否给出了最合适的算法，这只是谷歌的第一次点击。您可以查看其中一个工具，它可以将位图图像转换为矢量表示。也许你可以在不重新实现算法的情况下调用它们?)

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

顺便说一下，在90年代早期，我在工作中遇到过类似的问题。我搞砸了: 我想出了一个(完全不同的)算法，可以在实数坐标系下工作，但是面对浮点数(和噪音输入)的现实，似乎遇到了一个完全无法解决的退化情况。也许在互联网的帮助下，我会做得更好！

小开

如果您使用 C + + ，并且不想自己创建算法，那么可以使用 推进，几何学。它使用了上面提到的 Weiler-Atherton 算法的改进版本。

小开
最佳答案

我理解原来的海报是寻找一个简单的解决方案，但不幸的是，真的没有简单的解决方案。

尽管如此，我最近还是创建了一个开源的免费软件剪辑库(使用德尔斐、 c + + 和 c # 编写) ，它可以剪辑各种多边形(包括自相交的多边形)。这个库使用起来非常简单: http://sourceforge.net/projects/polyclipping/。

小开

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

  1. 为多边形顶点和 使用 std::list是不行的，因为您必须交换下一个和 上的特殊操作的指针/偏移量 这是获得简单代码的唯一方法，这将给出 表现不错。
  2. 通过比较每对边来找到交点。注意 比较每一对边缘会得到 O (N2)时间，但是会有所改善 O (N · logN)的算法后来就简单了 边(例如 a → b 和 c → d) ，交点是通过使用 边 a → b 上的参数(从0到1) Ta = d0/(d0-d1) ，其中 d0是(c-a) × (b-a) ，d1是(d-a) × (b-a) 二维交叉积 p × q = px · qγ-pγ · qx, 找到交点就是把它当做线性插值 参数 a → b: P = a + ta (b-a)
  3. 拆分添加顶点(和链表中的节点)的每个边 这些部分相交的地方。
  4. 然后您必须 十字架交叉点处的节点 需要进行自定义双向链接的操作 必须交换一对 下一个指针(并更新 前面的 相应的指针)。

然后就得到了多边形交点求解算法的原始结果。通常，您需要根据每个区域的绕组数选择一些区域。搜索 多边形绕组数多边形绕组数以获得对此的解释。

如果你想从这个 O (N2)算法中创建一个 O (N · logN)算法，你必须做完全相同的事情，除了在一个行扫描算法中。找 宾利 · 奥特曼算法。内部算法将是相同的，唯一的差异，您将有一个减少数量的边进行比较，内部循环。

小开

我解决同一个问题的方法

  1. 将多边形分割成线段
  2. 使用 IntervalTrees或 LineSweepAlgo找到相交线
  3. 使用 GrahamScanAlgo找到一条闭合路径，以找到一条具有相邻顶点的闭合路径
  4. 交叉引用3。与 DinicAlgo解析它们

注意: 我的场景是不同的，因为多边形有一个共同的顶点。但希望这可以帮助

小开

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

这会给你一个凸多边形的集合，这样它们的并就是你的起始多边形的交集。

小开

如果多边形没有对齐，那么它们必须对齐。我将通过找到多边形的中心(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);
}

提交答案