topología de malla triangular

Question

Tengo una clase de malla triangular que contiene una lista de nodos (2D en mi caso, pero eso no debería importar) y una lista de rostros. Cada cara es un triángulo y que sólo contiene los índices en la matriz nodo. La malla sale de un algoritmo de Delaunay, así que es muy limpio.

Para cada nodo de la malla Necesito encontrar que los nodos están conectados a la misma con un solo borde. Lo que sería una forma rápida de construir y buscar esta base de datos de topología?

Muy agradecido, David Rutten

Answer 1

Hay dos estructuras de datos algo estándar que facilitan malla topología de consultas. Uno es Winged Bordes (comúnmente denominado también como media-borde ), y el otro es Dirigida bordes . Google alrededor y se obtendría kajillions de detalles, y las introducciones a distintos niveles en cada uno de ellos.

No sabe lo suficiente sobre su escenario a recomendar uno de ellos. Por ejemplo, bordes dirigidos es, y el más adecuado para mallas muy grandes optimizado almacenamiento. cantos alados se considera un 'clásico', y es un buen punto de partida para sabores más avanzadas.

En realidad, si está seguro de que es la única consulta que había necesidad, entonces ambos son una exageración y que harías muy bien con una sola hash. Sin embargo, si usted se encuentra en necesidad de respuestas eficientes a las preguntas como -

• ¿Qué se enfrenta a utilizar este vértice?
• ¿Qué bordes utilizar este vértice?
• ¿Qué se enfrenta a este borde fronterizo?
• ¿Qué bordes frontera esta cara?
• que se enfrenta son adyacentes a este cara?

Debe tener en cuenta el buceo en uno de ellos.

Answer 2

Creo que he quedé ciego a mí mismo en tablas hash, diccionarios y listas ordenadas ... La siguiente es probablemente el más fácil y rápida:

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