哎哟，XML 网格:)。
我实际上对此很好看，我的第一个答案很懒惰。你可以写得更好（如上文所述），而且也没有那么复杂，我不会为此花 40 美元买一篇期刊文章。这是一个应该适合您的伪代码解决方案。
注意：当我说表时，我的意思是“查找表”。
假设每个三角形都有编号并由顶点 v1、v2、v3 组成，这些顶点是唯一编号的并且可以使用 < 运算符进行比较（因此我们可以获得唯一的键组合）。
我们需要两个查找表：
一个表格告诉我们哪些三角形使用给定的边，另一个表格告诉我们一个给定的三角形由哪些边组成。我们按如下方式构建这些列表：
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->faces 表。如果边 e1 和 e2 相邻，则考虑 e2 和 e3，但 e1 和 e3 不是。如果我们在 edge->face 列表中连接 e1、e2 和 e3 条目，你最终会得到一些非常不正确的数据。这可能比您想做的要多一些，但这是我今天早上必须解决的问题:)。
在每条边最多只能对应2个三角形的情况下，我们可以去掉传统意义上的可以追加的'list'，而使用大小为2的固定大小的数组。这样可以减少你的内存开销并提高内存效率。所以我们的边缘表更类似于：
无论如何，基本算法可以扩展到具有任意数量边的任意数量的多边形（所有多边形之间不一定相同），并且相对于三角形（或一般情况下的多边形）的数量是 O(N) 时间。空间复杂度为 O(E + N) 其中 E 是边，N 是多边形的数量。查找时间应该接近 O(1)，假设您有良好的散列算法。