从多边形索引列表中获取相邻的多边形

Question

我有一个像这样的网格形式，其中每个多边形都用索引列表表示。我需要为每个多边形生成相邻多边形的列表，并想知道是否有有效的算法来完成此操作？

最简单的方法是对于每个多边形，检查每个其他多边形是否具有两个匹配的索引-但这似乎涉及几个嵌套循环。我不介意使用它，性能在这里并不是一个巨大的问题，但是我正在寻找替代方案。

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

感谢任何帮助！ :)

- Aralox

---

感谢您的回答，我也有这样的怀疑 ;) - Aralox

Answer 1

哎呀，XML网格 :).

我仔细看了一下，我第一个答案太懒了。你可以写得更好（如上所述），而且它并不复杂，我不会为此花费40美元购买期刊文章。这里是一个伪代码解决方案，应该适合你。

注意: 我说的“表”是指“查找表”。

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

我们需要两个查找表：

• 一个名为edge_triangles的边->(三角形列表)表。
• 一个名为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是指第一个。

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

另一个可能的问题是，如果你有两条重合的边却没有共同的顶点。在这种情况下，你可以将任一边减少到一个参数方程，比较它们是否重合，并形成一个查找表，告诉你给定边，哪些边是重合的，所以映射：

边 - > (边缘列表）称为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)。

- Liam M

---

谢谢你的帮助，Liam！它一定会帮助很多人，包括我自己。现在有点难以理解，但我会再读几遍，直到完全理解其中的过程。 - Aralox

你的边集应该是{min_vertex，mid_vertex}，{mid_vertex，max_vertex}，{max_vertex，min_vertex}。在构建边列表时保持三角形中给定的顺序非常重要。 - Rockcat

Answer 2

只要你只对三角网格（或任何n-D中的简单形式）感兴趣，实际上有更快的解决方案！你提出的建议的时间复杂度为O（k ^ 2），其中k是三角形数量。这意味着对于大量的三角形，计算邻居所需的时间将呈二次增长，这在大多数情况下都是计算上禁止的。

我建议您阅读Ueng和Sikorski的文章（“关于构建3D FEA数据的邻接图的线性时间算法的注释”，Visual Computer 12：pp.445-450，1996年）。作者解释了一种用于在四面体网格中查找邻居的线性时间算法O（k），从中您可以轻松推导出类似的算法以用于三角化的网格。也许您还能将其扩展到普通多边形！

如果这对您有用，请告诉我！

- HopsC

---

谢谢你的回答，看起来非常强大！当我到达需要提高性能的阶段时，我一定会尝试它。 - Aralox

不客气！我一直在解决类似的问题，但是关于这个特定问题的信息确实很少（至少使用我所用的关键词）...无论如何，很高兴能帮忙！ - HopsC

@HopsC 我也遇到了同样的问题，可以看看我下面的帖子，里面有一个O(N)的解决方案，可以处理顶点邻接和真正的几何邻接（需要额外的步骤）。 - Liam M

@Aralox，我添加了一个不那么糟糕的答案，请告诉我你的想法 - 我认为它应该满足你对速度的需求 :)。 - Liam M

@Liam 干得好 :) 这与Ueng和Sikorski的工作类似。不过，我有一个问题。当你提到“...我们可以取给定三角形中的边，将其用作边缘列表中的键，并查看哪些多边形共享该边”时，你是指对于每个三角形边，您会搜索查找表以找到相邻的三角形吗？因为这将意味着如果您为多个多边形执行此例程，则仍具有O（N ^ 2）复杂度（因为您要遍历N行N次以查找邻居）。 ...Need for speed: 不错！ :) - HopsC

@HopsC 不完全正确，列表应该是表格，这应该是这些。您将获取三角形中的每个连续边（其中包含两个顶点ID），并在表格中查找键。对于哈希表，这应该是摊销O（1），对于有序列表，这应该是O（log N）。没有第二次遍历，在每个边缘上一次，每个三角形3次查找（或零次，如果您在第一次搜索后保留引用）将为您提供每个相邻三角形，在简单情况下。 - Liam M

Answer 3

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

对于预先计算的数据，每个顶点持有一个使用它的面列表就足够了。通过相交两个顶点的面列表来查找邻居。

- Ante