我有一个三角网格类,它包含一组节点列表(在我的示例中为2D,但这不应该成问题),以及一个面片列表。每个面片都是一个三角形,只包含节点数组中的索引。该网格来自Delaunay算法,因此非常干净。
对于网格中的每个节点,我需要找到与其相连的仅有一条边的节点。有什么快速构建和搜索该拓扑数据库的方法吗?
非常感谢! David Rutten
对于网格中的每个节点,我需要找到与其相连的仅有一条边的节点。有什么快速构建和搜索该拓扑数据库的方法吗?
非常感谢! David Rutten
有两种比较标准的数据结构可以方便地进行网格拓扑查询。其中一种是Winged Edges(通常也称为half-edge),另一种是Directed Edges。在谷歌上搜索,你会得到无数的细节和不同级别的介绍。
不了解您的情况,无法推荐其中之一。例如,有向边是存储优化的,最适合非常大的网格。翼边被认为是“经典”的,并且是更高级变体的良好起点。
实际上,如果您确定这是唯一需要查询的内容,那么两者都过于复杂,使用单个哈希表就足够了。但是,如果您发现自己需要高效地回答类似以下的查询 -
你应该考虑深入其中之一。
我想我已经对哈希表、字典和排序列表盯得眼花缭乱了...以下可能是最简单和最快的方法:
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