topologie de maillage triangulaire

Question

J'ai une classe de maillage triangulaire qui contient une liste de noeuds (2d dans mon cas, mais cela ne devrait pas d'importance) et une liste de visages. Chaque face est un triangle, et il ne contient que les indices dans la matrice de noeud. Le maillage sort d'un algorithme de Delaunay il est donc très propre.

Pour chaque nœud du maillage que je dois trouver les noeuds qui lui sont connectés avec un seul bord. Quel serait un moyen rapide de construire et rechercher cette base de données de topologie?

Bien obligé, David Rutten

Answer 1

Il y a deux struct de données un peu standard qui facilitent les requêtes de topologie mesh. On est Winged Edges (communément appelée également demi-bord ), et l'autre est Mise en scène Edges. Google autour et vous obtiendrez kajillions de détails et intros différents niveaux dans chacun.

Je ne sais pas assez sur votre scénario de recommander l'un d'eux. Par exemple, des bords dirigés stockage est optimisée, et le mieux adapté à mailles très larges. bords ailées est considéré comme un « classique », et est un bon point de départ pour les saveurs les plus avancées.

En fait, si vous êtes certain que est la seule question que vous auriez besoin, puis les deux sont une surpuissance et vous feriez bien avec un seul hachage. Cependant, si vous vous trouvez dans le besoin de réponses efficaces aux questions comme -

• Ce qui fait face à utiliser ce sommet?
• Quels bords utiliser ce sommet?
• Ce qui fait face à la frontière de ce bord?
• Quels bords frontière ce visage?
• Ce qui fait face sont adjacents à cette visage?

Vous devriez envisager de plonger dans l'un d'entre eux.

Answer 2

Je pense que je me suis regardé fixement aveugle sur Hashtables, dictionnaires et listes triées ... Ce qui suit est probablement le plus facile et plus rapide:

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