6

有谁知道将一组多边形分解成它们不同的重叠和非重叠区域的相对快速的算法，即给定一组n个多边形，找到它们之间的所有不同区域？

例如，输入将是代表圆形的 4 个多边形，如下所示

并且输出将是代表以不同颜色显示的不同区域的所有多边形。

我可以使用多边形操作编写自己的实现，但该算法可能会很慢且耗时。我想知道是否有针对此类问题的优化算法。

4

2 回答 2

1

您的问题称为地图叠加问题。它可以在 O(n*log(n)+k*log(k)) 时间内求解，其中 n 是段数，k 是段相交数。

首先，您需要将多边形表示为双向连接的边列表，不同的面对应于不同多边形的内部。

然后使用Bentley-Ottmann 算法查找所有线段相交并重建边缘列表。请参阅：计算两个细分的叠加或细分表示和地图叠加。

最后，遍历边缘列表中的每个循环并收集该循环半边的面。每组面将代表一个不同的重叠区域。

另请参阅：Shapefile Overlay Using a Double-Connected Edge List。

于 2014-02-16T15:17:42.950 回答
1

我不认为这有那么难。我已经在友好网站上回答了类似的问题，并由一个较小的社区进行了检查： https ://cs.stackexchange.com/questions/20039/detect-closed-shapes-formed-by-points/20247#20247

  • 让我们寻找一个更常见的问题——让我们用曲线而不是多边形。让我们允许它们超出图片边界，但我们只计算完全属于图片的简单多边形。
  • 通过检查属于不同曲线的所有线段对来查找所有交点。当然，在真正检查交叉点之前过滤它们。
  • 对所有曲线编号 1..n。在其中设置一些段的顺序。
  • 为每个点创建一个相交序列 SOI，因此：如果它从边界端开始，SOI[1] 为空。如果不是，SOI[1]=（与它相交的第一条曲线的编号，相交曲线上向左移动的符号）。继续，将每个交叉点写入 SOI - 如果有曲线，则为曲线数，如果是与边界的交叉点，则为 0。
  • 显然，您只寻找内部没有曲线的简单边界区域。
  • 两个相邻的非空交点之间的曲线，我们称之为线段。
  • 每条曲线都有 SOI：
    • 对于曲线 1 的线段，从线段的第一个点开始，进行 2 次尝试绘制线段多边形。它是 2，因为您可以沿着第一条相交曲线前往 2 条边。
    • 对于右尝试，只做左转，对于左尝试，只做右转。
    • 如果您到达的点没有正确方向的路段，则尝试失败。如果返回曲线 1，则成功。你有一个封闭的区域。
    • 记住所有成功的尝试
    • 对曲线 1 的所有段重复此操作
    • 对所有其他曲线重复此操作，检查所有找到的区域与已找到的区域。两个相同的相邻段足以认为面积相等。

如何找到交叉点的方向。

当段 p(p1,p2) 穿过段 q(q1,q2) 时，我们可以计算向量 pXq 的向量乘法。我们只对它的 Z 坐标的符号感兴趣——那是在我们的平面之外。如果是+，q从左到右穿过p。如果是 -，q 从右到左穿过 p。

向量乘法的 Z 坐标在这里算作矩阵的行列式：

0         0          1
p2x-p1x   p2y-p1y    0
q2x-q1x   q2y-q1y    0

（当然，也可以写得更简单，但这是一个很好的记忆技巧）

当然，如果您要更改左侧的所有权利，那么整个算法实际上不会发生任何变化。

于 2014-02-15T19:28:34.943 回答