Théorie des graphes utilisables?

paul18

Bonsoir,

Je cherche une solution à mon problème actuel, et avant de lancer une quelconque hypothèse dans un domaine où je suis totalement néophyte, je me propose d'abord d'exposer mon défi à relever :

1. je cherche à écrire un programme (Python) qui détecte automatiquement ce que les anglo-saxons nomment "non-manifold vertices": une (ou plusieurs) connexion(s) n'impliquant qu'un nœud à chaque fois (voir image en attaché)
2. chacun aura reconnu un maillage, j'ai arbitrairement mis 3 "non-manifold vertices"; dans la réalité, je peux en avoir aucun, 1 comme x
3. le maillage a un particularité forte; c'est un maillage de peau qui s'appuie sur des éléments volumiques sous-jacents (hexaèdres, tétraèdres, pentaèdres) = il se compose de quadrangles et/ou triangles et chacune des "surfaces" est fermée
4. qui dit maillage dit table de connectivité, et je la connais: je peux retrouver assez facilement les arêtes 
5. (je peux même couper les quadrangles en triangles, ce qui revient au final à un fichier STL)
6. bien sûr j'ai cherché sur le net de la documentation (il m'en reste encore pas mal à lire ), mais elle se veut très générale (et donc plus compliquée à appréhender)
7. (je ne peux bien sûr pas compter les éléments connectés à un même nœud; typiquement y triangles peuvent être raccordés au même nœud) 

Pour détecter automatiquement ces fameux "non-manifold vertices":

• voyez-vous une solution qui vous parait évidente ? 
• la théorie des graphes peut-elle m'aider? (je n'y suis pas encore entré dedans)
• je vois (wikipedia) qu'il est possible de mettre ça sous forme de matrice (matrice des degrés - matrice adjacente - matrice laplacienne) mais est-ce utilisable dans mon cas ? ça serait des plus séduisants.

Tout conseil pour m'orienter est le bienvenu

Paul

bisam

Je ne connais absolument rien à la représentation en 3 dimensions en général, mais en cherchant un petit peu avec le vocabulaire que tu as donné "non manifold vertices", on trouve facilement qu'il existe 4 types de tels sommets :

1. les sommets isolés : qui n'appartiennent à aucune arête.
2. les sommets sur un fil : qui appartiennent à une arête qui elle-même n'appartient à aucune face.
3. les sommets qui appartiennent à plusieurs faces n'ayant aucune arête commune
   
4. les sommets qui appartiennent à une arête commune à au moins 3 faces.

Pour les détecter, tout dépend de la représentation informatique de ces différents types d'objets, cependant, a priori, je pense que les objets de types "sommets" possèdent une méthode "appartient à telle arête", les arêtes une méthode "possède tels sommets" et "appartient à telle face" et les faces "possède telles arêtes".

Il devient facile de détecter les éléments que tu cherchais.

PS : J'ai modifié un petit peu mes propos en utilisant le vocabulaire plus adéquat "arête" à la place de "côté".

Barjovrille

Bonjour, je ne sais pas si j'ai bien compris ton problème notamment la définition de "non manifold vertices".

J'ai une question est-ce que dans le cas des maillage 2D c'est possible de rencontrer des "non manifold vertices" si oui est-ce que tu peux faire une image exemple comme tu l'as fait ?

Le reste des questions (notamment sur la théorie des graphe) dépend de ta réponse à ma première question.

paul18

@bisam:

• je ne m'intéresse qu'au cas n°3
• le cas n°2 est facile à traiter (ce que j'ai déjà fait): une arête ne peut être commune qu'à 2 et seulement 2 éléments (je rappelle que ma surface est fermée, donc le cas "une" arête n'est pas possible; en pratique c'est un bord libre qui est aussi facile à traiter):  dans le cas 2, l'arête apparait 4 fois = il suffit de sortir les occurrences

Dans le cas n°3, je ne peux pas compter, car :

• sur un même nœud je peux avoir en théorie une infinité de triangles,
• j'ai bien x éléments et y arêtes qui y sont connectés (pas de discontinuité)

Je cherche la petite subtilité (à l'instar du cas n°2) qui me permette d'identifier ce ou ces nœud(s): les performances de l'algorithme en dépendront  (surtout quand je traite plusieurs millions d'éléments quads/trias); à défaut une système robuste. L'idée des matrices est plaisante https://fr.wikipedia.org/wiki/Th%C3%A9orie_des_graphes (sans savoir si c'est utilisable), car on peut faire beaucoup de calculs (voir librairies genre Numpy par exemple)

@Brajoville: voir PJ (sauf erreur)

Paul

Barjovrille

Je n'avais pas vu le message de Bisam, ok ça commence à s'éclaircir.

D'après tes images tu t'intéresse plutôt au cas 3. de Bisam non ?  Le cas 1. c'est un point isolé dans l'espace si j'ai compris (mais tu n'en aura pas) . Le cas 2. ne se pose pas car il n'y a pas de "fil simple" dans ton maillage (du genre un carré avec une antenne) . Et le cas 4. je n'ai pas trop compris mais j'imagine que ça pose problème si il y a un "vide" dans le maillage mais ce n'est pas autorisé. Tu confirmes ?

Barjovrille

Dans le cas 3. (ce sont les exemples que tu as fourni), tu peux brute force avec la table de connectivité. Tu prends un premier élément du maillage (un polyèdre) et tu regardes tous les éléments qui n'ont qu'un seul sommet en commun avec cet élément. Si tu trouves de tels sommets  ce sont des non manifold vertices cas 3 (l'étape regarder tous les éléments... se fait bien avec numpy tu utilises le calcul vectoriel ça va assez vite je pense). Et tu fais ça pour tous les éléments du maillage. Il y a peut-être une façon plus intelligente de faire essayer de repérer les arbres dans le graphe (partie connexe minimale), (ça pourrait impliquer l'utilisation du laplacien du graphe mais c'est une idée très vague c'est peut-être un cul de sac aussi, si je trouve une stratégie concrète je te dirais).

paul18

oui c'est le cas n°3: j'ai lu trop rapidement (je corrige)

Barjovrille

Ok merci pour la confirmation nos messages se sont croisés.

paul18

Merci à tous les 2 pour ces éléments de réponse.

@Barjovrille: oui je vois assez bien comment procéder; pour autant je dois fournir en entrée une liste de nœuds par éléments et chercher les occurrences dans la table complète: si j'ai 1 million d'éléments, je dois quand même faire 1 million d'itérations (et les boucles coûtent chers, sauf à //). Mais ça reste une voie.

Pour ce qui est de la théorie des graphes, n'y a-t'il pas une matrice qui fournit l'information?

Barjovrille

Oui le problème c'est la boucle for.

Pour l'instant je ne vois pas de matrice de la théorie des graphes qui fournit l'information de manière plus évidente que la table de connectivité. Mais peut-être qu'il y a des façons astucieuses de représenter le graphe ou de voir les choses qui réduiront la complexité de la recherche (après je ne suis pas un expert en théorie des graphes ni du maillage).