14

我有许多不相交的简单多边形，但有些多边形可能嵌入到其他多边形中。

例如：

+--------------------------------------------+
|                                            |
|   +----------------+          +--------+   |
|   |                |         /         |   |
|   |   +--------+   |        /          |   |
|   |   |        |   |       /  +----(2)-+   |
|   |   |        |   |      /   |            |
|   |   +----(3)-+   |     /    |   +---+    |
|   |                |    +-----+   |   |    |
|   +------------(2)-+              +(2)+    |
|                                            |
+----------------------------------------(1)-+

如何找出所有多边形的“深度”？换句话说，如何找出一个多边形被多少个多边形包围？“深度”是括号中的数字。

我可以计算一个多边形的一个点在所有其他多边形内的次数，但这具有二次复杂性。如何更快地计算这些深度？

4

5 回答 5

2

将多边形放入某种空间查找结构中，例如基于多边形最小边界矩形的R 树。然后你应该能够计算出你在 O( n log n ) 中所追求的包含关系。（除非您处于病态情况下，多边形的许多最小边界矩形重叠，根据您的描述，这似乎不太可能。）

编辑添加：当然，你不依赖R树来告诉你一个多边形是否在另一个多边形内（它基于最小边界矩形，所以它只能给你一个近似值）。您可以使用 R-tree 廉价地识别候选包含物，然后以昂贵的方式验证这些包含物（检查一个多边形中的一个点是否在另一个多边形内）。

于 2013-01-18T00:46:35.900 回答
1

在您的示例中，您描述了一个非凸多边形，因此其他人建议的 rtree 方法本身不会有效。但是您可以将其与额外的检查相结合，以查看多边形的顶点是否在另一个顶点内，只要您找到与 rtree 方法的匹配项。这将减少您必须执行“多边形中的点”检查的次数。

另一种方法是采用您的第一个想法 - 即检查每个多边形的顶点与每个其他多边形 - 并对其进行修改以缓存您已经计算的结果并重用它们以降低时间复杂度。下面描述的方法本质上是从多边形本身构建树结构，而不是使用 rtree。它本质上是一种不同的树结构，它尊重非凸多边形。

  1. 最初，每个多边形都是一个根节点，并且在它自己的树中。
  2. 您必须遍历您的一组根节点并使用“多边形中的点”测试检查它是否在另一个根节点内。
  3. 当您找到匹配项时，从根节点集中删除较小的多边形并将其作为子节点添加到较大的多边形中。您开始构建一个有意义的树结构，并且您还减少了您正在迭代的容器（根节点）的大小，因此未来的迭代会更快。
  4. 继续此操作，直到根节点的数量停止变化。
  5. 请记住，在主嵌套循环中，您仅比较一个根节点是否在另一个根节点内。当您找到匹配项（大节点中的小节点）时，您可以跳过较小节点的子树。但是您必须遍历较大节点的子树并进行检查以找到层次结构中较小节点的正确位置。但是与具有二次复杂度的简单嵌套循环相比，您仍然避免了很多检查。
于 2019-12-27T15:00:38.693 回答
0

在我看来，您可以使用测试一个是否在另一个内部作为比较运算符来对多边形进行排序。

步骤1

假设我们定义多边形之间的关系“<”如下：A < B 且当 A 在 B 内。碰巧如果 A < B 且 B < C，则 A < C（即如果多边形 A 在 B 内且 B 在在 C 内部，那么 A 必须在 C 内部）。现在，我们在任意多边形之间有一个严格的弱排序。

[编辑：您需要使用某种点内非凸多边形测试，但大概您已经这样做了。]

第2步

使用您最喜欢的基于比较的排序算法根据此比较对多边形进行排序。例如，归并排序的最坏情况时间复杂度为 O(nlogn) 比较，其中 n 是多边形的数量。

[编辑：这是重要的一步，因为它摆脱了二次复杂性。]

第 3 步

确保“最大”（即最外层）元素首先出现在已排序的多边形数组中。（如有必要，请反转列表以实现此目的 - 它与多边形数量成线性关系）。

第4步

现在“最大”（即最外层）多边形应该是第一个元素。

[编辑：事实上，多边形已经根据它们的深度进行了排序。但是，具有相同深度的两个多边形可能会以不同的顺序出现，具体取决于排序是否稳定。这对我们来说无关紧要；我们感兴趣的是深度的变化。]

我们现在将为每个多边形分配一个深度，如下所示。首先，将每个1的深度初始化为0（[编辑：根据示例初始化为1]）。接下来，遍历您的排序列表，但这次仅将每个元素 p 与下一个元素 p+1 进行比较。如果 (p+1 < p) 为真，则增加 p+1 的深度。否则，将 p+1 的深度设置为与 p 的深度相同。

于 2013-03-29T21:44:47.467 回答
0

第 1 步：将多边形定向在同一方向，例如逆时针方向。

第 2 步：对于需要计算“深度”以计算总绕组数的任何点 (x, y)。这可以通过多种方式完成；实践中最快的方法是计算源自 (x, y) 的水平（或垂直）射线之间的交点的 SIGNED 数量。

特别是，每个多边形的深度将是它的任何顶点的深度。

于 2013-08-27T21:00:41.923 回答
0

（这种方法遵循与@GarethRees 类似的想法：首先，廉价地发现哪些多边形对不需要检查是否包含。一旦仍然需要检查的对数是可以接受的，就做精确的（昂贵的）几何查看。）

很容易计算每个多边形 p 的边界矩形，即左、右、上和下，所以让我们先这样做。例如左侧：p.L = min { x : (x,y) is a vertex of p }时间与点数成线性关系。

为避免将每个多边形相互比较，您可以将该区域划分为 2x2 网格。假设区域的宽度和高度分别由Dx和给出Dy，那么您可以创建九个集合top,bottom,left,right,topright,topleft,bottomright,bottomleft,rest并执行以下操作：

for p in polygons:
    in_top    = p.B > Dy/2
    in_bottom = p.T < Dy/2
    in_left   = p.R < Dx/2
    in_right  = p.L > Dx/2 
    if in_top:
        if in_left:
            add p to topleft
        elsif in_right:
            add p to topright
        else:
            add p to top
    elsif in_bottom:
        if in_left:
            add p to bottomleft
        elsif in_right:
            add p to bottomright
        else:
            add p to bottom

    if in_right and not (in_top or in_bottom):
        add p to right
    elsif in_left and not (in_top or in_bottom):
        add p to left

    if not (in_top or in_bottom or in_left or in_right):
        add p to rest

这又是线性时间。每个多边形都被分箱到其最“紧密”的包含扇区中。你从中得到了什么？好吧，例如，您知道对于其中的任何多边形p，left都不可能与 set 存在任何包含关系right，因此您无需比较它们。bottomleft与right、bottomleft和之间topleft也是如此，依此类推。这是您的示例中的样子：

                      Dx/2
+----------------------|---------------------+
|                      |                     |
|   +----------------+ |        +--------+   |
|   |                | |       /         |   |
|   |   +--------+   | |      /          |   |
|___|___|________|___|_|____ /__+===d(2)=+___|_ Dy/2
|   |   |        |   | |    /   |            |
|   |   +---b(3)-+   | |   /    |   +---+    |
|   |                | |  +-----+   |   |    |
|   +-----------c(2)-+ |            e(2)+    |
|                      |                     |
+----------------------|----------------a(1)-+

所以rest = {a}, top = {}, bottom = {}, left = {b,c}, right = {d}

topleft = {}, topright = {}, bottomleft = {}, bottomright = {e}

所以基本上现在你最多需要比较（用昂贵的精确支票）bto c，dtoe和a所有其他人——事实上，如果你以聪明的方式订购支票，你就不需要与a所有其他人比较，因为包含是传递性的，所以如果你注意到c包含b和a包含c，那么你不需要检查是否a包含b。

另一点是您可以递归地应用上述推理。比如说套装topright太大了，不适合你的口味；然后，您可以通过进一步划分该子区域来应用相同的技术（只需要正确记账）。

于 2013-01-29T14:17:02.220 回答