mesh - 三角网状拓扑

Question

我有一个三角形网格类，其中包含一个节点列表（在我的例子中是 2d，但这不重要）和一个面列表。每个面都是一个三角形，它只包含节点数组的索引。网格来自 Delaunay 算法，因此非常干净。

对于网格中的每个节点，我需要找到哪些节点通过一条边连接到它。构建和搜索此拓扑数据库的快速方法是什么？

非常感谢，大卫·鲁滕

Answer 1

有两个有点标准的数据结构有助于网格拓扑查询。一种是Winged Edges（通常也称为half-edge），另一种是Directed Edges。到处谷歌，你会得到无数的细节，以及每一个细节的不同层次的介绍。

对您的方案了解不足，无法推荐其中之一。例如，有向边是存储优化的，最适合非常大的网格。带翼的边缘被认为是“经典”，是更高级口味的良好起点。

实际上，如果您确定这是您需要的唯一查询，那么两者都是矫枉过正的，您只需使用一个哈希就可以了。但是，如果您发现自己需要对以下查询的有效答案 -

• 哪些面使用这个顶点？
• 哪些边使用这个顶点？
• 哪些面与此边缘接壤？
• 哪些边与这张脸接壤？
• 哪些面与这张脸相邻？

您应该考虑深入其中之一。

Answer 2

我想我对哈希表、字典和排序列表视而不见……以下可能是最简单和最快的：

Public Sub SolveConnectivity(ByVal nodes As Node2List, ByVal faces As List(Of Face))
  m_map = New List(Of List(Of Int32))(nodes.Count)

  'Create blank lists
  For i As Int32 = 0 To nodes.Count - 1
    m_map.Add(New List(Of Int32)(6))
  Next

  'Populate connectivity diagram
  For i As Int32 = 0 To faces.Count - 1
    Dim F As Face = faces(i)
    m_map(F.A).Add(F.B)
    m_map(F.A).Add(F.C)

    m_map(F.B).Add(F.A)
    m_map(F.B).Add(F.C)

    m_map(F.C).Add(F.A)
    m_map(F.C).Add(F.B)
  Next
End Sub