4

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

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

大変お世話になりました、デビッド・ルッテン

4

2 に答える 2

3

メッシュ トポロジ クエリを容易にする 2 つのやや標準的なデータ構造体があります。1 つはWinged Edges (一般にhalf-edgeとも呼ばれます) で、もう 1 つはDirected Edgesです。グーグルで検索すると、無数の詳細と、それぞれにさまざまなレベルのイントロが表示されます。

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

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

  • この頂点を使用する面は?
  • この頂点を使用するエッジは?
  • このエッジに隣接する面は?
  • この面に隣接するエッジはどれですか?
  • この面に隣接する面は?

それらのいずれかに飛び込むことを検討する必要があります。

于 2009-09-17T18:45:46.903 に答える
0

HashTables、Dictionaries、Sorted Lists で自分自身を盲目的に見つめたと思います...次はおそらく最も簡単で最速です:

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
于 2009-05-14T18:40:53.947 に答える