-1

我有一些区域包含 1 个或多个多边形。每个多边形以 GL_TRIANGLE_STRIP 格式表示，其中每个顶点是一对 (lat, long)。有什么办法可以得到该区域的轮廓？

一些规格：

  • 轮廓必须按逆时针顺序排列。
  • 任何 2 个多边形都可以有一个公共边。
  • 多边形可以是凹的
  • 一个多边形内部最多可以有 1 个“间隙”，它将由另一个轮廓按顺时针顺序表示。

我正在寻找一种复杂度约为 O(N*logN) 的算法，其中 N = 顶点数。

编辑：我尝试了像 2 x 2 这样的解决方案，直到我到达数据集的末尾然后向后移动，但是这个算法在有间隙的多边形上效果不好，例如 这个多边形，输入是: A B C D E F G H I J，其中 I = A 和 J = B , 这样做, 输出将是A C E G I J H F D Band that should be A C E Gand B H F G(顺序是倒置的，因为这样更容易绘制)。

另一种解决方案是考虑点一个无向图和它们之间的边（根据 GL_TRIANGLE_STRIP 格式），我在其中应用了 DFS 以取出连接的组件。之后，我计算了每个组件的面积，我将最大面积多边形视为逆时针轮廓，其余为顺时针轮廓。这不起作用，因为邻接表需要一些排序，这会使算法效率低下。

我尝试的另一个解决方案是一些调整过的凸包，但凸包仍然是凸包，并且不适用于凹多边形。

我还阅读了有关凹壳的信息，但这似乎并不总是给出准确的结果。

谢谢您的回答！

4

1 回答 1

1

让我们首先将三角形带转换为多边形。我们以下面的条带为例：

三角带 （由维基共享资源提供）

您的条带定义为：

A B C D E F

将其转换为多边形非常简单。只需浏览列表并使用每个第二个顶点。当你到达终点时，向后返回并使用其他顶点。在这种情况下：

A C E (reached the end, now return) F D B

这可以在O(N)中完成，其中N是条带的顶点数。这是顺时针还是逆时针取决于条带的方向。

所以，我们可以把每个条带变成一个多边形。剩下的就是删除共享边。假设我们有两个多边形

A C E F D B
W X E C Y Z

请注意，任何共享的边（在这种情况下C E）都将以相反的方向出现（C E在第一个多边形中，E C在第二个多边形中）。要找到区域轮廓，我们只需要找到匹配的边并合并两个多边形。

要找到匹配的边，只需将所有多边形边写入哈希映射（存储它们属于哪个多边形以及它们在多边形中的位置）就足够了。这可以在O(E)中完成，其中E是多边形边的总数。

要最终合并多边形，创建新多边形实际上更简单。修改绝对是可能的，但更微妙一些。为此，我们只需要沿着多边形边缘走。只要我们在其逆不在哈希图中的边上，就将这条边写入输出多边形。如果是，请忽略它并继续处理另一个多边形。标记您访问过的边缘，并在您回到之前访问过的边缘时立即停止。这样做直到所有边都被访问（或两个方向都在哈希图中）。整个过程可以在O(E)中完成，其中E是多边形边的总数。

这是我们示例中的样子：

Start at polygon 1
Start at edge (A, C)
(A, C) is neither visited nor is its inverse in the hash map
Create new output area = [A, C]
the inverse of (C, E) is in the hash map, continue to polygon 2
(C, Y) is neither visited nor is its inverse in the hash map
Append it to the area = [A, C, Y]
(Y, Z) is neither visited nor is its inverse in the hash map
Append it to the area = [A, C, Y, Z]
(Z, W) is neither visited nor is its inverse in the hash map
Append it to the area = [A, C, Y, Z, W]
(W, X) is neither visited nor is its inverse in the hash map
Append it to the area = [A, C, Y, Z, W, X]
(X, E) is neither visited nor is its inverse in the hash map
Append it to the area = [A, C, Y, Z, W, X, E]
the inverse of (E, C) is in the hash map, continue to polygon 1
(E, F) is neither visited nor is its inverse in the hash map
Append it to the area = [A, C, Y, Z, W, X, E, F]
(F, D) is neither visited nor is its inverse in the hash map
Append it to the area = [A, C, Y, Z, W, X, E, F, D]
(D, B) is neither visited nor is its inverse in the hash map
Append it to the area = [A, C, Y, Z, W, X, E, F, D, B]
(B, A) is neither visited nor is its inverse in the hash map
Append it to the area = [A, C, Y, Z, W, X, E, F, D, B, A]
(A, C) is already visited
Close the area contour, continue to check other unvisited edges

如果需要，您还可以按创建轮廓的多边形对生成的轮廓进行分组，以查找由多个轮廓界定的连接区域。多边形上的不相交集将有助于该任务。如果需要，您还可以尝试将轮廓分类为孔和外轮廓。但请注意，这个概念在球体上是高度模糊的（想象一个球体和一个沿赤道带的区域 - 两个轮廓中的哪一个是洞，哪个在外面？）对于相对较小的区域，您可以使用此分类的区域。

于 2019-09-25T16:35:44.387 回答