您可以使用半边数据结构。
基本上，您的网格也有一个边列表，并且每个方向上的每对顶点都有一个边结构。这意味着如果您有顶点 A 和 B，那么在某处存储了两个边缘结构，一个用于 A->B，一个用于 B->A。每条边有 3 个指针，一个称为前一个，一个称为下一个，一个称为孪生。跟随下一个和上一个指针将引导您绕过网格中三角形或多边形的边缘。调用 twin 会将您带到相邻多边形或三角形中的相邻边。（看图中的箭头）这是我所知道的最有用和最详细的边缘数据结构。我用它通过创建新边和更新指针来平滑网格。顺便说一句，每条边也应该指向一个顶点，这样它就知道它在空间中的位置。
您的问题实际上分为三个部分，而不是两个部分：
您必须提出其他问题才能找到适当的答案。
应该使用哪些数据结构来表示网格？
您需要处理哪些元素类型？
如果您只需要处理多边形（闭环）和单纯形（每个节点都连接到元素中的每个其他节点，例如四面体），那么有序节点列表就足够了，因为可以从节点列表中隐含边。另一方面，如果您需要处理六面体、棱柱或一般多面体等元素类型，则需要有关元素拓扑的更多信息。一个简单的边缘映射数组通常就足够了。它只是元素节点列表中索引的数组[][2]，它告诉您如何连接给定元素类型的点。
Chris 描述的半边结构仅适用于 2D。在 3D 中，每个边缘可以附加任意数量的元素，而不仅仅是两个。半边表示有一个 3D 扩展，我认为它被称为风车结构。
如果你必须支持任意元素类型，我更喜欢更完整的数据结构来表示元素拓扑。一个常见的选项是使用边和共边。每对连接的节点都有一个边结构，并且在元素中每次使用该边都有一个共同边。它类似于风车方法，但更明确一些。
我应该使用什么算法从元素中提取边缘？
速度或内存有多重要？结果应该包括每个元素一次的每条边，还是无论有多少元素使用它都只包含一次？结果中边缘的顺序是否重要？每条边的节点顺序是否重要？
对于只访问每个边一次的任意元素类型，很难想出一个算法。为了确保每条边只出现一次，您可以过滤结果，或者您可以有点hackish，并在每条边上保留一个“已访问”位，以确保您不会将其粘贴在结果中两次。
我应该如何表示结果？
我使用结果的方式有什么关系？
如果您要在计算密集型计算中使用结果，那么大的坐标数组可能是最佳选择。您不想在计算过程中一遍又一遍地重新获取节点坐标。但是，如果您要过滤结果以删除重复的边缘，则比较坐标（节点对为 6 个双精度）不是要走的路。如果您正在过滤，请先生成指向边缘结构的指针列表，然后过滤掉重复项，然后生成坐标列表。您也可以对节点对使用这种方法，但是您必须针对每条边的两个可能的节点顺序进行过滤，从而使过滤所需的时间加倍。
如果内存比性能更重要，那么边缘指针列表也是要走的路。但是，您不是将边缘列表转换为坐标列表，而是在计算过程中查找坐标。以这种方式获取节点坐标的速度较慢，但您可以避免制作大量坐标列表 - 您每条边存储一个指针，而不是每条边存储 6 个双精度数。
许多网格应用程序将所有坐标存储在一个大的全局数组中，每个节点都有一个数组索引。如果是这种情况，不要将边缘列表转换为坐标数组，而是将其转换为全局坐标数组的索引列表。性能不应该与本地坐标数组相差太多，但没有内存和人口开销。
我没有适合你的算法，但我可以告诉你去哪里找。
“点集三角测量”是您正在寻找的。
以下是一些可以为您执行此操作的开源库（了解算法的代码）：