三角网格拓扑

Question

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

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

多谢， 大卫·鲁顿

Answer 1

有两种有点标准的数据结构可以促进网格拓扑查询。 一种是Winged Edges（通常也称为half-edge)，另一个是 有向边。 谷歌一下，你会得到大量的细节，以及每个细节的不同级别的介绍。

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

实际上，如果您确定这是您需要的唯一查询，那么两者都太过分了，您只需使用单个哈希就可以了。 但是，如果您发现自己需要有效回答诸如“

• 哪些面使用此顶点？”
• 之类的问题。 哪些边使用这个顶点？
• 哪些面与该边缘接壤？
• 哪些边与该面接壤？
• 哪些面与此相邻
  脸？

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

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