三角メッシュトポロジ

StackOverflow https://stackoverflow.com/questions/864933

  •  21-08-2019
  •  | 
  •  

質問

ノードのリスト (私の場合は 2d ですが、それは問題ではありません) と面のリストを含む三角形メッシュ クラスがあります。各面は三角形であり、ノード配列へのインデックスのみが含まれます。メッシュはドロネー アルゴリズムから生成されるため、非常にきれいです。

メッシュ内のすべてのノードについて、どのノードが単一のエッジで接続されているかを見つける必要があります。このトポロジ データベースを構築して検索する迅速な方法は何でしょうか?

どうも デビッド・ルッテン

役に立ちましたか？

解決

メッシュ トポロジのクエリを容易にする、ある程度標準的なデータ構造体が 2 つあります。1つは ウィングエッジ (一般的にはとも呼ばれます) ハーフエッジ)、そしてもう一つは 有向エッジ. 。Google で検索すると、膨大な量の詳細と、それぞれについてさまざまなレベルの紹介が得られます。

シナリオの 1 つを推奨できるほど、シナリオについての知識がありません。たとえば、有向エッジはストレージが最適化されており、非常に大きなメッシュに最適です。ウィングエッジは「クラシック」とみなされており、より高度なフレーバーの出発点として適しています。

実際、それが必要な唯一のクエリであると確信している場合は、両方とも過剰であり、単一のハッシュで十分です。ただし、次のようなクエリに対する効率的な回答が必要な場合は、

  • この頂点を使用する面はどれですか?
  • この頂点を使用するエッジはどれですか?
  • このエッジに接する面はどれですか?
  • この面の境界となるエッジはどれですか?
  • これに隣接している面 顔。

そのうちの 1 つに飛び込むことを検討してください。

他のヒント

私は次はおそらく最も簡単かつ最速で...ハッシュテーブル、辞書およびソートされたリストにブラインド自分自身を見つめていたと思います 

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
ライセンス： CC-BY-SA と 帰属
所属していません StackOverflow
scroll top