三角メッシュトポロジ

Question

私は三角形のメッシュクラスを持っています。このクラスには、ノードのリスト（私の場合は2dですが、それは問題ではありません）とフェイスのリストが含まれています。各面は三角形であり、ノード配列へのインデックスのみを含んでいます。 Delaunayアルゴリズムからメッシュが出てきますので、きれいです。

メッシュ内のすべてのノードについて、どのノードが1つのエッジで接続されているかを調べる必要があります。このトポロジデータベースを迅速に構築して検索するにはどうすればよいでしょうか？多くの義務が

、私はハッシュテーブル、辞書およびソートされたリストにブラインド自分自身を見つめていたと思う デビッド・ルッテン

Answer 1

ありますメッシュトポロジクエリーを容易にする2つのやや標準的なデータ構造体。 1つはWinged Edges（一般にhalf-edgeとも呼ばれます）ともう1つはDirected Edgesです。 Googleの周りとあなたは詳細のkajillions、それぞれにさまざまなレベルのイントロを得るだろう。

あなたのシナリオについて、それらのいずれかを推奨するには十分なものがありません。たとえば、有向エッジはストレージに最適化され、非常に大きなメッシュに最適です。ウイングエッジは「古典的」と考えられており、より高度なフレーバーの出発点となります。

実際に必要とする唯一のクエリだと確信していれば、両方とも過度の攻撃であり、1つのハッシュでうまくいくでしょう。しかし、あなたが -

• のような質問に対する効率的な回答が必要な場合は、この頂点を使用してください。
• この頂点を使用するエッジはどれですか？
• このエッジの境界にはどちらが向いていますか？
• この辺にどの辺が接していますか？
• この顔に隣接する顔はどれですか？ ？

これらのうちの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