topologia a maglia triangolare

Question

Ho una classe di maglia triangolare che contiene una lista di nodi (2D nel mio caso, ma che non dovrebbe importare) e un elenco di facce. Ogni faccia è un triangolo e contiene solo gli indici nella matrice nodo. La maglia viene fuori di un algoritmo di Delaunay quindi è molto pulito.

Per ogni nodo della rete devo trovare quali nodi connessi a quest'ultimo con un singolo bordo. Quale sarebbe un modo rapido per costruire e cercare questo database topologia?

Molto obbligato, David Rutten

Answer 1

Ci sono due le strutture di dati in qualche modo standard che facilitano la maglia topologia-query. Uno è Winged Bordi (comunemente indicato anche come half-bordo ), e l'altro è Diretto bordi . Google in giro e si otterrebbe kajillions di dettagli, e intro vari livelli in ciascuno di essi.

Non so abbastanza circa lo scenario di raccomandare uno di loro. Ad esempio, è archi orientati stoccaggio ottimizzato, e più adatto per grandi mesh. bordi Alati è considerato un 'classico', ed è un buon punto di partenza per i sapori più avanzati.

In realtà se si è certi che è l'unica domanda che ci serve, quindi entrambi sono un peso inutile e faresti bene con un unico hash. Se, tuttavia, si trova nel bisogno di risposte efficaci alle domande come -

• che si affaccia usare questo vertice?
• Quali bordi usare questo vertice?
• che si affaccia confine questo bordo?
• Quali bordi di confine questa faccia?
• Quali volti sono adiacente a questo faccia?

Si dovrebbe prendere in considerazione le immersioni in uno di loro.

Answer 2

Credo di aver guardai me cieco hashtables, dizionari e liste ordinate ... Quello che segue è probabilmente il più facile e veloce:

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