Topologie à mailles triangulaires

Question

J'ai une classe de maillage triangulaire qui contient une liste de nœuds (2d dans mon cas mais cela ne devrait pas compter) et une liste de faces. Chaque face est un triangle et ne contient que les indices dans le tableau de nœuds. Le mesh provient d'un algorithme de Delaunay donc c'est très propre.

Pour chaque noeud du maillage, j'ai besoin de trouver les noeuds qui lui sont connectés avec un seul bord. Quel serait un moyen rapide de construire et de rechercher cette base de données de topologie?

bien obligé, David Rutten

Answer 1

Il y a deux structures de données quelque peu standard qui facilitent les requêtes topologiques maillées. L'un est Winged Edges (communément appelé aussi half-edge), et l'autre est Directed Edges. Google autour et vous obtiendrez des kajillions de détails, et intros de divers niveaux dans chacun.

Je ne connais pas suffisamment votre scénario pour en recommander un. Par exemple, les bords orientés sont optimisés pour le stockage et conviennent mieux aux maillages de très grande taille. Les bords ailé sont considérés comme «classiques» et constituent un bon point de départ pour des saveurs plus avancées.

En fait, si vous êtes certain que c'est la seule requête dont vous auriez besoin, alors les deux sont une overkill et vous feriez bien avec un seul hachage. Si, toutefois, vous avez besoin de réponses efficaces à des requêtes telles que -

• Quels visages utilisent ce sommet?
• Quels bords utilisent ce sommet?
• Quelles sont les faces qui bordent ce bord?
• Quels bords bordent ce visage?
• Quelles faces sont adjacentes à cette face ?

Vous devriez envisager de plonger dans l'une d'entre elles.

Answer 2

Je pense que je l'ai regardé fixement moi-même 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