多边形索引列表中的相邻多边形

Question

我有一个类似于 this 的网格。 末尾有代表每个多边形的索引列表。我需要为每个多边形生成相邻多边形的列表，并且想知道是否有人知道执行此操作的有效算法？

我想到的最简单的方法是对于每个多边形，检查其他每个多边形是否有两个匹配的索引 - 但这看起来涉及一些嵌套循环。我不介意使用这个，性能在这里不是一个大问题，但是是的，我只是在寻找替代方案。

每个多边形的最大索引/顶点没有任何限制，但为了简单起见，我们假设其为 3（因此三角形多边形）。

感谢您的帮助！ :)

Answer 1

哎哟，XML 网格:)。

我实际上仔细研究了这个，我的第一个答案很懒。你可以写得更好（如上面发布的），而且没那么复杂，我不会花 40 美元买一篇关于这个的期刊文章。这是一个应该适合您的伪代码解决方案。

注意：当我说表时，我的意思是“查找表”。

假设每个三角形都已编号并由顶点 v1、v2、v3 组成，这些顶点具有唯一编号并且可以使用 << 进行比较。运算符（这样我们可以获得唯一的组合键）。

我们需要两个查找表：

• 一个称为edge_triangles 的edge->（三角形列表）表。
• 称为triangle_edges 的三角形->（边列表）表。

一个表告诉我们哪些三角形使用给定的边，另一个表告诉我们给定的三角形由哪些边组成。我们按如下方式构建这些列表：

for t = next triangle
    // Determine the ordering of vertices.
    min_vertex = min(t.v1, t.v2, t.v3);
    mid_vertex = median(p.v1, t.v2, t.v3);
    max_vertex = max(t.v1, t.v2, t.v3);

    // Register which edges this triangle uses.
    edge_triangles[min_vertex][mid_vertex].append(t);
    edge_triangles[mid_vertex][max_vertex].append(t);
    edge_triangles[min_vertex][max_vertex].append(t);

    // Set the edges that make up this triangle.
    triangle_edges[t].append({min_vertex, mid_vertex});
    triangle_edges[t].append({mid_vertex, max_vertex});
    triangle_edges[t].append({min_vertex, max_vertex});
for next t

使用这些列表，我们可以获取给定三角形中的边，将它们用作边表中的键，并查看哪些多边形共享该边。因此，相邻的三角形。因此，对于三角形 t，我们可以执行以下操作：

adjacent = edge_faces[face_edges[t][0]];

这是“相邻等于共享三角形 t 的第 0 条边的三角形列表”的伪代码，其中第 0 条边只是第一个。

我们使用 min、median 和 max 来确保相同的边不会有不同的条目：例如 {v1, v2} 和 {v2, v1}，其中 v1 和 v2 是两个顶点。我们实际上可以忽略这一点并添加一个“紧凑”步骤，其中我们连接与边缘列表中的不同条目相对应但实际上对应于相同边缘的列表。

另一个可能的问题是，如果您有两条重合但不共享公共顶点的边。在这种情况下，您可以将任一边简化为参数方程，比较它们的重合度，并形成一个查找表，告诉您对于给定边，哪些边是重合的，因此映射：

• edge->(edges list) table称为edge_coincident_edges。

我们还使用另一个查找表，因为我们无法连接边->面表。考虑边 e1 和 e2 是否相邻，则 e2 和 e3 相邻，但 e1 和 e3 不相邻。如果我们将边->面列表中的 e1、e2 和 e3 条目连接起来，您最终会得到一些非常不正确的数据。这可能比你想做的多一点，但这是我今天早上必须解决的问题:)。

在每条边最多只能对应2个三角形的情况下，我们可以取消传统意义上的“列表”，我们可以追加，并使用大小为2的固定大小的数组。这将减少你的内存开销并提高记忆效率。所以我们的边表更类似于：

• 一个名为edge_triangles的边->（第一个三角形，第二个三角形）表。

无论如何，基本算法可以扩展到具有任意数量边的任意数量的多边形（所有多边形之间不一定相同），并且相对于三角形（或一般情况下的多边形）的数量来说是 O(N) 时间。空间复杂度为 O(E + N)，其中 E 是边，N 是多边形的数量。假设您有良好的哈希算法，查找时间应该接近 O(1)。

Answer 2

如果您只对三角网格（或 n-D 中的任何单纯形）感兴趣，那么实际上有更快的解决方案！您提出的建议的时间复杂度为 O(k^2)，其中 k 是三角形的数量。这意味着对于大量三角形，计算邻居所需的时间成倍增加，这在大多数情况下在计算上是令人望而却步的。

我建议您阅读 Ueng 和 Sikorski 的文章（“关于构建 3D FEA 数据邻接图的线性时间算法的说明”，视觉计算机 12：pp 445-450，1996）。作者解释了用于查找四面体网格中的邻居的线性时间算法 O(k)，从中您可以轻松推导出三角网格的类似算法。也许您也可以将其扩展到一般多边形！

让我知道这是否适合您！

Answer 3

如果没有预先计算的数据，就不可能比循环遍历所有面更快。

对于预先计算的数据，每个顶点保存使用它的面列表就足够了。查找邻居是通过 2 个顶点的相交面列表来完成的。