三角网格拓扑

Question

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

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

大卫·鲁滕（David Rutten）

Answer 1

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

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

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

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

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

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