Rappel du contexte théorique

Triangulation : qu'est-ce que c'est ?

        La triangulation consiste à mailler un semis de points, avec des triangles ayant pour sommets les points du semis. Nous nous limiterons à un espace à deux dimension, qui est le cas d'école. En effet, le même problème peut se poser en un nombre de dimensions supérieur, notamment celui en 3 dimensions, qui est très utilisé pour la modélisation des objets (réalité virtuelle).
   Ce maillage doit répondre à certaine propriétés de la triangulation, à savoir que l'intersection de deux triangles est soit :

•  l'ensemble vide (les deux triangles sont distincts)

• un point du maillage

• une arête

    Le problème consiste à choisir une méthode pour construire cette triangulation. Nous allons nous intéresser à celle de Delaunay qui repose sur le diagramme de Voronoï (ces deux représentation sont en fait duales).

La méthode Delaunay

    Cette méthode s'appuie principalement sur le critère suivant :

Soit T un triangle du maillage, alors aucun point du semis (sauf ceux de T), n'est contenu dans le cercle cercle circonscrit de T.

    Nous allons utiliser un algorithme incrémental pour construire le diagramme de Delaunay (il en existe d'autres qui utilisent des méthodes globales, comme le célèbre "Diviser pour Construire" ou "divide and conquer").

Principe: 

    On insère les points un par un. A chaque point inséré, on recherche dans quel triangle il se trouve. On supprime alors ce triangle pour en créer trois nouveaux ayant pour sommet ce point et pour côté opposé les arêtes du triangle englobant. On vérifie ensuite le critère, c'est à dire que le point inséré ne se trouve pas dans le cercle circonscrit d'un des triangles voisins. Si c'est le cas, on fait pivoter l'arête commune entre les deux triangles, et on vérifie le critère avec les voisins des nouveaux triangles créés.... 

Pour ce faire il faut initialiser le maillage, c'est à dire qu'il faut au moins un triangle de départ qui contient tous les points à insérer. A la fin, une fois tous les points insérés, on retire ce triangle du maillage et on corrige éventuellement en rajoutant des triangles sur le bord du maillage de façon à former une enveloppe convexe. 

Structures de données utilisées

On utilise une liste doublement chaînée pour stocker les points. Ces points sont à coordonnées réelles et seront représentés par un enregistrement contenant 2 champs, un pour l'abscisse et un pour l'ordonnée.

On utilise une deuxième liste doublement chaînée LT pour le stockage des triangles du maillage. Chaque élément de la liste est un enregistrement contenant un champ du type triangle, et deux pointeurs pour l'accès au précédent et au suivant de la liste. On fera en sorte que la liste soit triée par rapport à l'orthocentre du triangle de chaque élément (tri par abscisse, puis par ordonnée si collision).

Le type triangle est un enregistrement contenant : trois pointeurs sur des éléments de la liste de points qui sont les trois sommets du triangle trois pointeurs sur des éléments de LT référençant les voisins du triangle un champ H contenant un point correspondant aux coordonnées de l'orthocentre du triangle

Voici un schéma regroupant les différentes déclarations et leurs liens :

Liste de points

Liste de triangles

Autres structures de données utilisées :

• Droite : on déclare un enregistrement pour stocker les coefficients d'une droite, soit sa pente et son ordonnée à l'origine.

Description de l'algorithme

• Algorithme principal

• Prototypes des fonctions utilisées pour la réalisation de l'algorithme

1. Outils géométriques : geometrie.c et geometrie.h

2. Opérations sur le type Point : points.c et points.h

3. Manipulation d'une liste de Points : listePoint.c et listePoint.h

4. Opérations sur le type Triangle et gestion d'une liste de triangles : listeTriangle.c et listeTriangle.h

5. Fonctions et procédures propres à l'algorithme : delaunay.c et delaunay.h

• Programme principal

Algorithme principal :

1. Chargement des points en mémoire, dans la structure prévue, à partir du fichier d'entrée. Ce fichier d'entrée sera conforme au format suivant : le nombre de points contenu dans le fichier, suivi (ligne par ligne) des coordonnées des points comprises entre 0 et 100, écrites sur deux caractères avec 2 espaces entre chaque coordonnée, exemple : entree.dat.

2. Initialisation de la boite englobante  : l'algorithme de Delaunay reposant sur l'insertion de points dans un triangle, on doit avoir un triangle de départ. Pour résoudre cette contrainte, on crée une boite englobante autour du semis de points : c'est à dire un rectangle ( mieux adapté au problème qu'un triangle) que l'on divise en deux triangles.  

3. Insertion des points un à un, avec vérification du critère du cercle circonscrit.

4. Suppression de la boite englobante.

5. Écriture dans un fichier des triangles résultant de la triangulation, au format suivant : liste des triangles affichés ligne par ligne.

Prototypes des fonctions utilisées pour la réalisation de l'algorithme :

1. Outils géométriques : geometrie.c et geometrie.h

• Point milieu(Point *a,Point *b);
  Fonction qui retourne le milieu du segment [a,b]
• Droite equation(Point *a,Point *b);
  Fonction calculant l'équation d'une droite : c'est à dire calcule la pente et l'ordonnée à l'origine. Cette fonction ne traite pas le cas où la droite est verticale, il faut donc tester ce cas avant d'appeler la fonction.
• Droite perp_passant_par_p(Point *a,Point *b,Point *p);
  Fonction qui retourne l'équation de la droite perpendiculaire à la droite (a,b) passant par le point p
• Droite mediatrice(Point *a,Point *b);
  Fonction qui retourne l'équation de la médiatrice du segment [a,b].
• Point intersection_droite(Droite *d1,Droite *d2);
  Fonction qui retourne les coordonnées du point d'intersection des deux droites passées en paramètres.
• int appartient_segment(Point *p,Point *a,Point *b);
  Retourne si le point p appartient au segment [a,b].
  
  

2. Opérations sur le type Point : points.c et points.h

• Point creerPoint(double x,double y);
  Retourne un point ayant les coordonnées passées en paramètres.
• void affichePoint(Point *p);
  Affiche un point sur la sortie standard.
• void faffichePoint(FILE *f,Point *p);
  Affiche un point dans le fichier f passé en paramètre.
• double distance(Point p1,Point p2);
  Retourne la distance entre deux points.
  
  

3. Manipulation d'une liste de Points : listePoint.c et listePoint.h

• void creation(Listept *l);
  créé et initialise une liste de points.
• int fichier_de_points(char *nomfich,Listept *lpt);
  lit dans un fichier des coordonnées de points et les insère dans la liste lpt.
• void afficheListePoint(Listept *lpt);
  Affiche la liste de points sur la sortie standard.
• int est_vide(Listept *l);
  Retourne si la liste de points est vide.
• void destroy(Listept *l);
  supprime entièrement une liste de point de la mémoire.
• void insert(Listept *l,Point *punct,int choix);
  Insère un élément dans la liste de points, choix est la position où l'insérer.
• void supprimer(Listept *l,int choix);
  Supprime le point qui est à l'emplacement choix dans la liste
  
  

4. Opérations sur le type Triangle et gestion d'une liste de triangles : listeTriangle.c et listeTriangle.h

• Triangle creerTriangle(Point *s1,Point *s2,Point *s3,Listept *lpt);
  Crée et initialise un triangle avec les paramètres passes dans la fonction, et détermine son orthocentre.
• Triangle copiet(Triangle *t1, Listept *lpt, Tliste *lt);
  Copie un triangle.
• EltTriangle *voisin_par_arete(Triangle *tr,Point *p1,Point *p2);
  Retourne le triangle voisin de tr contenant p1 et p2 (qui peuvent designer une arête de tr).
• void AfficheT(Triangle t);
  Affichage d'un triangle sur la sortie standard.
• void fAfficheT(FILE *f,Triangle t);
  Affichage d'un triangle dans un fichier.
• void creationTl(Tliste *l);
  Initialisation d'une liste de triangles.
• int est_videTl(Tliste *l);
  Retourne si la liste est vide.
• void afficheListeT(Tliste *lt);
  Affiche la liste de triangles sur la sortie standard.
• void afficheListeT2(Tliste *lt);
  Affiche la liste de triangles ET leurs voisins sur la sortie standard.
• void fafficheListeT(FILE *f,Tliste *lt);
  Affiche la liste de triangles dans un fichier.
• void insertTl(Tliste *l,EltTriangle *tr);
  Insertion d'un triangle dans une liste de triangles triée par coordonnées de leurs orthocentres.
• void supprimeTri(Tliste *l, Triangle *tr);
  Suppression d'un triangle dans une liste de triangles triée par coordonnées de leurs orthocentres. On ne vérifie pas que le triangle est dans la liste, on suppose qu'il y est.
• void destroyTl(Tliste *l);
      Procédure de destruction de liste de triangles.
  

5. Fonctions et procédures propres à l'algorithme : delaunay.c et delaunay.h
   
   

   • void Init_All(struct listept *lpt,Tliste *Tl,int xmin,int xmax,int ymin,int ymax);
     Cette première procédure sert à effectuer l'initialisation du système, c'est à dire à créer la boite englobante. Elle crée quatre nouveau points à partir des coordonnées qu'on lui rentre en paramètre, ces points étant ceux de la boite. Puis elle crée les deux triangles correspondants. Elle insère alors les triangles et les points dans leur liste respective. Afin que les quatre points de la boîte ne soient pas cocycliques, on en décale un.
   • int p_boncote(Point *a,Point *b,Point *c,Point *p);
         Cette fonction renvoie un entier. Cet entier est une sorte de booléen. En effet, cette fonction teste ( d'après les paramètres d'entrée ) si le point c est du même côté de la droite (a,b) que p. Si la fonction renvoie 0, c'est que p et c ne sont pas du même côté. 
         Le principe algorithmique est le suivant : on effectue un test pour savoir si le segment est perpendiculaire à la droite des abscisses, car dans ce cas on compare  les abscisses des 2 points : c et p, pour conclure. 
         Sinon, on utilise la fonction "equation" expliquée plus haut, pour calculer la pente et la coordonnée à l'origine de la droite formée par a et b. L'équation est alors équivalente à :     pente*x + (ordonnée à l'origine) - y = 0 . On remplace alors x et y par les coordonnées des points c et p. Les résultats ne sont plus égaux à 0 , mais positifs ou négatifs selon de quel côté de la droite se trouve chaque point. On multiplie les 2 résultats obtenus entre eux. La fonction renvoie en réalité 0, si la multiplication est inférieure à 0, car dans ce cas les deus résultats ne sont pas du même signe et p et c ne sont pas du même côté de la droite.
   • int p_dans_triangle(Triangle *t,Point *p);
         A l'aide de cette fonction, on sait si un point p est contenu dans un triangle t.
     Le principe de fonctionnement est basé sur la fonction précédente. On test si p est du même côté que le troisième sommet par rapport à  la droite formée par deux sommets du triangle . Si le test est vérifié pour tous les sommets, alors p appartient à t. 
   • EltTriangle triangle_contenant_p(Triangle t_init,Point *p,Listept *lpt,Tliste *lt);
         Cette fonction retourne un EltTriangle, c'est à dire un élément de la liste de triangle. Cet élément a dans son champ triangle le triangle contenant le point p. Elle part du premier triangle de la liste et teste s'il contient p. Si ce n'est pas le cas, on va tester sur un autre triangle, mais ce triangle n'est pas prit  au hasard, ni dans l'ordre de la liste. En effet on cherche à se déplacer "dans la direction" de p, à partir du triangle sur lequel on se trouve.
         Chaque triangle pointant sur des triangles voisins, on cherche le triangle voisin sur lequel on va se déplacer et recommencer le teste. Pour choisir ce triangle, on trace la droite entre l'orthocentre de notre triangle et le point p. Cette droite va couper une arête du triangle ( le cas où l'orthocentre est extérieur au triangle est pris en compte dans la fonction). On se déplace alors sur le triangle voisin ayant cette arête commune avec notre triangle. Lorsque le test révèle que le triangle est celui qui contient p, on renvoie l'EltTriangle correspondant.
         Cette fonction est en relation directe avec l'algorithme de Delaunay. On va faire appel à elle à chaque fois que l'on insèrera un nouveau point dans le maillage.
   • EltTriangle one_two_three(Triangle *t, Point *p, Tliste *lt,Listept *lpt);
        
     

     Ici on suit la suite logique de la fonction précédente. Après avoir trouver le triangle contenant le point inséré, il faut le diviser en trois nouveaux triangles. L'algorithme de cette fonction est simple : on crée trois nouveaux triangles à partir du nouveau point et des sommets du triangle qui le contient ; établissement des liens avec leurs voisins ; actualisation des voisins de leurs voisins, car leur nouveaux voisins ne pointent pas encore sur eux et pointent toujours sur le triangle t contenant p ; insertion des trois nouveaux triangles dans la liste ; suppression du triangle t contenant p. On renvoie alors l'EltTriangle correspondant à l'un des trois nouveaux triangles, car il a pour voisins les deux autres, et il est important pour la suite de l'algorithme de ne pas perdre l'adresse de ces trois triangles.

   • int critere_cercle(Triangle *t,Point *p);
         On va se servir de cette fonction pour vérifier si un point p est dans le cercle circonscrit d'un triangle t. Pour faire ce test, on calcul la distance entre l'orthocentre du triangle et un sommet : cela nous donne le rayon, puis on le compare avec la distance entre le même orthocentre et le point p. Si le rayon est supérieur, alors p appartient au cercle circonscrit du triangle. 
         Cette fonction va nous permettre de vérifier le critère principal de l'algorithme, et faire, en fonction du résultat, pivoter ou pas des arêtes.
   • void actualise_voisin(EltTriangle *tv,EltTriangle *t,Point *a,Point *b,Tliste *lt);
         Cette procédure est principalement utilisée dans la fonction one_two_tree, pour actualiser les voisins des 3 nouveaux triangles. On entre un triangle et son voisin en paramètres, ainsi que les deux sommets qui leurs sont communs. A partir de la on retrouve quel est le pointeur du voisin qui devra pointer sur notre triangle, et on fait en sorte qu'il pointe sur notre triangle. Ceci est très important, car en insérant des nouveaux triangles dans la liste, il faut qu'ils pointent sur des voisins, mais que leurs voisins aussi pointent sur eux.
   • void verif_activ(EltTriangle *tr,Point *p,Tliste *lt,Listept *lpt);
     

     C'est dans cette procédure que l'on va lancer les vérifications du critère principal, et agir en conséquence. On a un triangle de départ tr ainsi que le point p. On teste si tr n'est pas nul car dans ce cas on ne fait rien et on ressort tout de suite de la procédure. Si non, on appel critere_cercle qui va nous dire si p est dans le cercle circonscrit de tr ou pas. S'il n'y est pas, la procédure s'arrête là. Si oui, on initialise deux nouveaux triangles ( l'initialisation est faite ici, car si les tests précédents ne sont pas vérifiés, ce serait inutile de le faire avant ). On effectue un test à l'aide de la fonction p_boncote pour savoir quel est le sommet de tr qui est opposé à son voisin contenant pt. Un triangle ayant trois sommets, il y a trois cas différents selon le sommet trouvé, donc la procédure contient trois parties quasi similaires. Selon le sommet on va rentrer dans une des trois parties, mais nous allons expliquer le fonctionnement d'une qui se généralise aux trois.     Le principe est le suivant : est crée alors deux nouveaux triangles ( afin de faire pivoter l'arête commune à tr et son voisin contenant pt) on fait en sorte qu'ils pointent sur leurs voisins dans le graphe, et des actualisations de leurs voisins ( actualise_voisin ), on les insère, on supprime tr et son voisin contenant p, puis on relance verif_activ (toujours avec le point p) sur leur voisin sans revenir sur nos pas.

        

   • void ajoute_point_dans_Graphe(Point *p,Listept *lpt,Tliste *lt);
         Cette procédure applique l'algorithme de Delaunay. Elle fait appel aux fonctions et procédures précédentes, c'est à dire qu'elle prend un point p de la liste lpt rentré en paramètre, cherche dans quel triangle il se trouve à l'aide de triangle_contenant_p, divise se triangle en trois à l'aide de one_two_tree, puis appel verif_activ sur les voisins des trois nouveaux triangles.
   • test_min_max(double *xmin,double *xmax,double *ymin,double *ymax,Point *pt);
         Cette fonction permet de remettre à jour les variables xmin, xmax, ymin, ymax à partir du point pt. Si l'abscisse de pt est inférieure à xmin, alors xmin prend sa valeur, si l'ordonnée de pt est supérieure à ymax, alors ymax prend sa valeur. Il est facile  d'imaginer ce qu'il en est de xmax et ymin. Ceci va nous servir dans la procédure de suppression de la boite englobante, pour pouvoir obtenir une boite qui englobera "au mieux" les points du maillage (c'est-à-dire, un rectangle très proche de l'enveloppe convexe des points insérés dans le graphe) : le centre de cette boite sera considéré comme le "centre" du maillage.
   • void suprime_boite(Tliste *lt, Listept *lpt, double *xmin, double *xmax, double *ymin, double *ymax);
         Il s'agit maintenant de supprimer les quatre points de la boite englobante, et les triangles ayant pour sommet un ou deux de ces points. Puis, il faut vérifier que le contour du maillage forme une enveloppe convexe, dans le cas contraire, il faudra rajouter des triangles sur le pourtour. En voici le fonctionnement étape par étape :

     • on parcours la liste lt jusqu'à trouver un triangle contenant un et un seul point de la boite.    

     • On insère les deux points du triangle (blancs sur le dessin) dans une liste de points qui va contenir tous les points du contour. On insère également ce triangle dans une liste qui servira à stocker les triangles à supprimer. On va garder en mémoire ce triangle dans deux variables, une qui nous servira de test d'arrêt pour parcourir tous les triangles communs à la boite, et l'autre qu'on réactualisera à chaque passage au voisin, de manière à savoir d'où on vient. On passe au triangle voisin (peu importe lequel, du moment qu'il n'est pas dans le maillage). On rentre dans une boucle qui va nous servir à répertorier tous les points et les triangles du contour. A chaque itération, on insère un nouveau point, un nouveau triangle et on réactualise les coordonnées extrémales à l'aide test_min_max.
     • A partir de nos coordonnées extrémales, on détermine le "centre" du maillage, qui est l'intersection des diagonales du rectangle formé par les coordonnées extrémales.
     • La liste de points maintenant obtenue comporte les points dans l'ordre de parcours du contour. On prend donc les points trois par trois, et on vérifie si le deuxième point du triplet est du même côté que le centre par rapport à la droite formée par les deux autres points du triplet. Si ils le sont, alors on crée un nouveau triangle ayant pour sommet ces trois points, et on réactualise ses voisins.
       
     • A partir de la liste de triangles du contour, on peut supprimer tous les triangles superflus de liste de triangles du maillage.
     • On libère toute la mémoire que l'on avait alloué pour réaliser cette procédure (liste de points et liste de triangles du contour).
     • 
       

Programme principal :

    Il suffit d'appeler la procédure fichier_de_points avec le nom de fichier saisie à l'appel du programme pour charger les points en mémoire. Ensuite on appelle init_All pour créer la boite englobante. On parcourt la liste de points et on les insère un par un dans le maillage à l'aide de la procédure ajoute_point_dans_Graphe. A la sortie on obtient la liste des triangles du maillage. On supprime alors la boite englobante. Il ne reste plus qu'à écrire dans un fichier ( sortie.dat ) les triangles, identifiés par leurs sommets.

Remarques et conclusion

Optimisation et résultats du programme :

    On pourrait améliorer la structure de données, en modifiant les champs sommets et triangles voisins, en remplaçant dans les deux cas les trois champs par un tableau de trois pointeurs.

    Le programme ne fonctionnement pas dans tous les cas. Pour l'insertion de points, tout se passe comme prévu, mais lors de la vérification du critère, à partir du deuxième appel ( récursif ) des triangles ne sont pas supprimés. En effet, après vérification, on pouvait obtenir quatre triangles pour quatre points. On en conclut, que le pivotement d'arête a lieu, mais que l'actualisation de la liste n'est pas correcte : 

LA VERITE EST AILLEURS....

Du point de vue de la suppression de la boite englobante, nous avons vérifié que l'on obtenait bien les points du contours. Tout se passe correctement, mis à part la suppression, de la mémoire, de la liste de triangles temporaire que l'on crée. En effet, la liste ne ressort pas indemne de la boucle qui consiste à vérifier la convexité du système. Mais, nous n'arrivons pas à comprendre pourquoi, puisque on ne fait pas appel à la liste dans cette boucle. Encore une fois : Mystère.

Bénéfice du projet :

    En dehors du plaisir incommensurable de débugger un programme en C, nous avons pu prendre conscience que la notion de pointeurs n'était pas si évidente à manipuler. Nous avons également, mais trop tard, adopté des méthodes un peu plus rigoureuses pour programmer.

Quelques liens intéressants :