Triangular malha topologia

Question

Eu tenho uma classe de malha triangular que contém uma lista de nós (2d no meu caso, mas que não deve importar) e uma lista de faces. Cada face é um triângulo e que contém apenas os índices na matriz nó. A malha sai de um algoritmo de Delaunay por isso é muito limpo.

Para cada nó na malha eu preciso encontrar o que nós estão ligados a ele com uma única aresta. O que seria uma maneira rápida de construir e pesquisar esta base de dados topologia?

Muito obrigado, David Rutten

Answer 1

Existem duas estruturas de dados um pouco do padrão que facilitam a topologia de consultas de malha. Um deles é Winged Bordas (comumente referido também como half-edge ), eo outro é Directed Bordas . Google ao redor e você deseja obter kajillions de detalhes, e intros vários de nível em cada um.

não sei o suficiente sobre o cenário para recomendar um deles. Por exemplo, arestas dirigidas é optimizada para armazenamento, e mais adequado para muito grandes malhas. bordas alados é considerado um 'clássico', e é um bom ponto de partida para sabores mais avançadas.

Na verdade, se tiver certeza de que é a única consulta você precisa, em seguida, ambos são um exagero e você faria muito bem com um único hash. Se, no entanto, encontra-se na necessidade de respostas eficientes para consultas como -

• Que rostos usar este vértice?
• Que bordas usar este vértice?
• Que enfrenta fronteira essa vantagem?
• Que bordas fronteira esta cara?
• Que rostos são adjacentes a este rosto?

Você deve considerar mergulho em um deles.

Answer 2

Eu acho que olhou-me cego na Hashtables, dicionários e listas ordenadas ... O seguinte é provavelmente o mais fácil e 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