三角形网格拓扑结构

Question

我有一个三角网格类，它包含一组节点列表（在我的示例中为2D，但这不应该成问题），以及一个面片列表。每个面片都是一个三角形，只包含节点数组中的索引。该网格来自Delaunay算法，因此非常干净。

对于网格中的每个节点，我需要找到与其相连的仅有一条边的节点。有什么快速构建和搜索该拓扑数据库的方法吗？

非常感谢！ David Rutten

- David Rutten

Answer 1

有两种比较标准的数据结构可以方便地进行网格拓扑查询。其中一种是Winged Edges（通常也称为half-edge），另一种是Directed Edges。在谷歌上搜索，你会得到无数的细节和不同级别的介绍。

不了解您的情况，无法推荐其中之一。例如，有向边是存储优化的，最适合非常大的网格。翼边被认为是“经典”的，并且是更高级变体的良好起点。

实际上，如果您确定这是唯一需要查询的内容，那么两者都过于复杂，使用单个哈希表就足够了。但是，如果您发现自己需要高效地回答类似以下的查询 -

• 这个顶点被哪些面使用？
• 这个顶点连接哪些边？
• 这条边被哪些面所相邻？
• 这个面连接哪些边？
• 哪些面与这个面相邻？

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

- Ofek Shilon

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

- David Rutten

---

为了避免人们认为你只是在刷声望，最好的方法可能是1）在发布自己的答案之前等待一段时间，或者2）将这个答案移动到原始问题上方。 - Scottie T

@Scottie T：这种自问自答的方式是允许的，甚至在FAQ中也鼓励这样做。我倾向于将答案设为CW，否则会感觉像是在操纵TFGITW问题。请参见：http://stackoverflow.com/questions/18557/how-does-stackoverflow-work-the-official-faq/119658#119658 - dmckee --- ex-moderator kitten

Scottie，我不知道，谢谢你指出来。虽然我不会再去尝试修改它了。 - David Rutten