-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 回答