我在有限元方法中使用了一个二维三角形网格来离散域。我想计算所有边的中点，因为我想使用元素。我正在使用 MatLab。我拥有的数据是：
包含节点坐标和的矩阵。大小为，其中是节点数。
包含每个三角形节点的矩阵。大小为，其中是网格中三角形的数量和 3 列，因为每个三角形都有三个节点。例如，这个矩阵的一行可能有所以三角形是由这些节点形成的，为了知道它们的坐标，我只取节点坐标矩阵中的第 10、4和行（前面的一）。
我事先知道节点数（包括中点）将是其中是网格边界中的节点数，所以我可以预先分配矩阵。新节点矩阵将包含先前节点坐标和新节点坐标，元素矩阵现在将有 6 列，因为每条边将添加一个节点。
我的代码正在做的是遍历所有三角形并计算它们的边中点，如果它还没有在坐标节点矩阵中包括它（在这里我会浪费很多时间来检查它是否还在里面）。主要问题是，由于内部边缘对于两个三角形来说是共同的，所以已经计算了很多次边缘的中点，所以我在浪费时间计算中点，然后检查它是否已经在矩阵中。
你能给我任何关于如何更有效地计算边缘中点并将它们包含在矩阵中的建议吗？注意：我没有网格边缘的矩阵。
谢谢！
如果您有一个数组来存储每个单元格的 3 个邻居的索引，那么您只会计算相邻单元格边缘的中点的索引高于当前单元格，或者根本没有邻居。这样，您就可以轻松决定两个单元中的哪一个负责计算边缘中点。
如果主要瓶颈是计算唯一边的列表（好吧，在 MATLAB 中，我猜它是一个矩阵），只要你能找到一个哈希表实现，你应该能够找到一个（n 平均情况）线性时间顶点（或元素，或边，由欧拉公式，因为您的二维网格是平面图）数量的算法。
这样做的方法是遍历包含三角形节点的矩阵。每行包含三个节点索引，因此包含三个潜在边的二元素向量。将这些向量插入到您的哈希表中，使用向量的排序版本作为键。（一个例子：如果我的边是 , ,，我的哈希表应该看起来像，我使用 Python 字典符号来表示哈希表，因为 Python 字典是在标准库中实现为哈希表。）然后读取哈希表的键将为您提供独特的边缘，您可以使用此信息插入中点。{[1, 2]: [[2, 1]], [1, 3]: [[1, 3]], [2, 3]:[[3, 2]]}
几乎可以肯定，有更有效的数据结构可用于处理有限元信息。我认为是 PETSc 中的 DMplex 的Sieves浮现在脑海中；其他类似 DAG 的表示形式存在于精神上相似的文献中，如果不是实践的话。但是，我认为没有实现筛子的 MATLAB 库，而大多数语言都可以使用哈希表实现作为面向用户的库，这使其成为一种更容易以任何语言组合在一起的解决方案。（它也较少依赖于数据结构和算法知识的方式。）