Comment détecter et enregistrer la connectivité cyclique dans les sommets de bord (détection de trous)?

Question

merci de prendre le temps de lire ma question.

Je travaille sur la détection de trous dans un treillis triangulaire et les remplis de nouveaux triangles. J'ai fait quelques-unes des parties qui sont, pour obtenir une liste de sommets de bord, etc. Voici les sommets/arêtes qui font des trous, s'il vous plaît jeter un oeil à l'image.

(9, 62)   => vertex # 9 and 62 makes an edge (left hole) 
(66, 9)   => vertex # 66 and 9 makes an edge (left hole) 
(70, 66)  => vertex # 70 and 66 makes an edge (left hole) 
(62, 70)  => vertex # 62 and 70 makes an edge (left hole) 

(147, 63)  => vertex # 147 and 63 makes an edge (right hole) 
(55, 148) 
(63, 149) 
(149, 55) 
(148, 147) 

La première chose que je dois faire est de vérifier quels sommets font un cycle (ce qui signifie un trou est détecté), puis enregistrez dans un ensemble distinct de sommets cycliques.

Le problème est d'écrire un tel algorithme qui vérifie si le graphique donné (sommets/arêtes) contient combien de cycles? puis enregistrer dans des ensembles distincts.

Veuillez m'écrire un algorithme simple et optimisé pour résoudre ce problème.

Merci.

Answer 1

1. maille

   Laissez supposons que votre STL maille a n triangles dont vous avez besoin pour le convertir en format indexé. Donc, extraire tous les points de triangle et convertir en deux tables distinctes. l'un tenant tous les points et le second contenant 3 indices de points pour chaque triangle. Supposons que vous avez obtenu m points et n triangles.

   Vous devez trier la table de points (index) et utiliser la recherche binaire pour l'accélérer de O(n.m) à O(m.log(n)).

2. _edge Structure

   créer une structure qui détient tous les bords de la maille. Quelque chose comme:

   struct _edge 
   { 
   int p0,p1; // used vertexes index 
   int cnt; // count of edge usage 
   }; 
   

   où p0<p1.

3. créer _edge edge[] tableau O(n)

   Il doit être une liste tenue de tous les bords (3n), de sorte boucle à travers tous les triangles et ajouter 3 arêtes par chacun. Le nombre défini sur cnt=1 Ceci est O(n).

   Maintenant, triez la liste par p0,p1 qui est O(n.log(n)). Après cela, il suffit de joindre tous les bords avec le même p0,p1 en additionnant leur cnt et en supprimant l'un d'entre eux. Si codé à droite, il s'agit de O(n).

4. détecter trou

   En régulière STL chaque bord doit avoir cnt=2.Si cnt=1 alors triangle est manquant et vous avez trouvé votre trou. si cnt>2 vous avez une erreur géométrique dans votre maillage.

   Supprimez donc tous les bords avec cnt>=2 de votre table edge[] qui est O(n).

5. détecter les boucles

   let supposons que nous avons k bords gauche dans notre tableau edge[]. Maintenant, pour chaque 2 bords qui partagent un point, créez un triangle. Quelque chose comme:

   for (i=0;i<k;i++) 
   for (j=i+1;j<k;j++) 
       { 
       if ((edge[i].p0==edge[j].p0)||(edge[i].p1==edge[j].p0)) add_triangle(edge[i].p0,edge[i].p1,edge[j].p1); 
       if ((edge[i].p0==edge[j].p1)||(edge[i].p1==edge[j].p1)) add_triangle(edge[i].p0,edge[i].p1,edge[j].p0); 
       } 
   

   Si vous utilisez la recherche binaire pour la boucle intérieure alors ce sera O(k.log(k)). Aussi vous devriez éviter d'ajouter des triangles en double et corriger le bobinage d'eux donc d'abord ajouter les triangles à la table séparée (ou rappelez-vous de commencer l'index) et ensuite supprimer les doublons (ou vous pouvez le faire directement dans add_triangle).

   De même, pour gérer des trous plus grands, n'oubliez pas d'ajouter de nouveaux bords à votre table edge[]. Vous pouvez mettre à jour les arêtes après le traitement des arêtes actuelles et répéter # 4 ou incorporer les modifications à l'analyse.