从三角形带转换为多边形
Converting from triangle strip to polygon
我有一些区域包含 1 个或多个多边形。每个多边形以 GL_TRIANGLE_STRIP 格式表示，其中每个顶点是一对 (lat, long)。有没有办法得到该地区的轮廓？
一些规格：
- 轮廓必须按逆时针顺序排列。
- 任意 2 个多边形可以有一条公共边。
- 多边形可以是凹的
- 一个多边形内部最多可以有 1 个 'gap'，这将由另一个轮廓按顺时针顺序表示。
我正在寻找复杂度约为 O(N*logN) 的算法，其中 N = 顶点数。
编辑：我尝试了一些解决方案，比如 2 乘 2 直到到达数据集的末尾然后向后移动，但是这个算法在有间隙的多边形上效果不佳，例如
this polygon 其中输入是：A B C D E F G H I J，其中 I = A 和 J = B，这样做，输出将是 A C E G I J H F D B 并且应该是 A C E G 和 B H F G（顺序颠倒了，因为这样画起来更容易）。
另一个解决方案是考虑点一个无向图和它们之间的边（根据 GL_TRIANGLE_STRIP 格式），我在其中应用 DFS 以取出连接的组件。之后我计算了每个组件的面积，我将最大面积的多边形视为逆时针轮廓，其余为顺时针轮廓。这是行不通的，因为邻接表需要一些排序，这会使算法效率低下。
我尝试的另一种解决方案是调整一些凸包，但凸包仍然是凸包，不适用于凹多边形。
我也读过有关凹包的信息，但这似乎并不总能给出精确的结果。
感谢您的回答！
让我们从将三角形带转换为多边形开始。我们以下面的条带为例：
（由维基共享资源提供）
您的条带定义为：
A B C D E F
将其转换为多边形非常简单。只需浏览列表并使用每个第二个顶点。当你在最后时，向后 return 并使用其他顶点。在这种情况下：
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
如果需要，您还可以根据创建等高线的多边形对生成的等高线进行分组，以查找由多个等高线界定的连接区域。多边形上的 disjoint set 将有助于完成该任务。如果需要，您还可以尝试将轮廓分为孔和外轮廓。但是请注意，这个概念在球体上是非常模糊的（想象一个球体和一个沿着赤道的带状区域 - 两个轮廓中的哪个是洞，哪个在外面？）对于相对较小的区域，您可以使用此分类的区域。
我有一些区域包含 1 个或多个多边形。每个多边形以 GL_TRIANGLE_STRIP 格式表示，其中每个顶点是一对 (lat, long)。有没有办法得到该地区的轮廓？
一些规格：
- 轮廓必须按逆时针顺序排列。
- 任意 2 个多边形可以有一条公共边。
- 多边形可以是凹的
- 一个多边形内部最多可以有 1 个 'gap'，这将由另一个轮廓按顺时针顺序表示。
我正在寻找复杂度约为 O(N*logN) 的算法，其中 N = 顶点数。
编辑：我尝试了一些解决方案，比如 2 乘 2 直到到达数据集的末尾然后向后移动，但是这个算法在有间隙的多边形上效果不佳，例如
this polygon 其中输入是：A B C D E F G H I J，其中 I = A 和 J = B，这样做，输出将是 A C E G I J H F D B 并且应该是 A C E G 和 B H F G（顺序颠倒了，因为这样画起来更容易）。
另一个解决方案是考虑点一个无向图和它们之间的边（根据 GL_TRIANGLE_STRIP 格式），我在其中应用 DFS 以取出连接的组件。之后我计算了每个组件的面积，我将最大面积的多边形视为逆时针轮廓，其余为顺时针轮廓。这是行不通的，因为邻接表需要一些排序，这会使算法效率低下。
我尝试的另一种解决方案是调整一些凸包，但凸包仍然是凸包，不适用于凹多边形。
我也读过有关凹包的信息，但这似乎并不总能给出精确的结果。
感谢您的回答！
让我们从将三角形带转换为多边形开始。我们以下面的条带为例：
您的条带定义为：
A B C D E F
将其转换为多边形非常简单。只需浏览列表并使用每个第二个顶点。当你在最后时，向后 return 并使用其他顶点。在这种情况下：
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
如果需要，您还可以根据创建等高线的多边形对生成的等高线进行分组，以查找由多个等高线界定的连接区域。多边形上的 disjoint set 将有助于完成该任务。如果需要，您还可以尝试将轮廓分为孔和外轮廓。但是请注意，这个概念在球体上是非常模糊的（想象一个球体和一个沿着赤道的带状区域 - 两个轮廓中的哪个是洞，哪个在外面？）对于相对较小的区域，您可以使用此分类的区域。