TD 2 - Triangulation


Ce TD sert de préparation aux prochains qui seront consacrés à la construction de la triangulation de Delaunay.

Structures de données

On utilisera les déclarations suivantes (interface structure.h et réalisation structure.c).

Les sommets seront rangés dans un tableau (Vertex vertices[];) et chaque sommet sera identifié par son indice dans ce tableau. Par ailleurs, on aura besoin d'accéder au dernier triangle incident construit sur un sommet.

La structure principale est le triangle. Il convient d'adopter une relation cohérente entre l'ordre des numéros de sommets dans v et l'ordre des triangles adjacents dans t.
Par exemple, pour i=0,1,2, on peut convenir que t[i] pointe sur le triangle opposé au sommet v[i]. Un relation simple entre i, j et k permet alors de trouver le triangle t[k] qui s'appuie sur le segment v[i]v[j] ou le sommet v[k] commun aux triangles t[i] et t[j].

Le constructeur new_Triangle permet d'allouer un triangle définit par trois points, sans relation de voisinage, ni orientation. Les trois sommets pointent alors sur ce triangle.
La fonction vertex_id permet de savoir si un point est sommet d'un triangle et, dans ce cas, de connaître sa place dans le triangle.
Le programme manipulera des listes de triangles (type TList) et une notion plus abstraite de triangulation pour laquelle sont définies 4 primitives : empty(), is_empty, triangles et add_triangle.

Graphique

On utilisera l'interface drawing.h dont la réalisation (fichier drawing.c) utilise la librairie MacLib (fichiers MacLib.c et MacLib.h, qu'il n'est pas nécessaire de regarder pour faire ce TD).

Il est recommandé de ne pas modifier ces fonctions graphiques qui seront utiles pour la mise au point.
Si le booléen hilite vaut FALSE (0) les fonctions dessinent en noir. Si le booléen hilite vaut TRUE (!0) les fonctions dessinent dans une couleur.

Voici un petit exemple d'utilisation :

#include 
#include 
#include "structure.h"
#include "drawing.h"

int main(void) {
  Vertex vertices[] = {
    {  50,  50 },
    {  75,  50 },
    { 100, 150 },
    { 125, 150 },
    { 125,  25 },
    {  50,  75 },
    {  25, 100 },
  };
  int n_vertices = sizeof(vertices)/sizeof(Vertex);
  Triangulation T = empty();
  add_triangle(new_Triangle(0, 1, 2, vertices), &T);
  add_triangle(new_Triangle(3, 1, 2, vertices), &T);

  init_drawing();      /* ne pas oublier */
  paint_vertices(vertices, n_vertices, FALSE);
  draw_list(triangles(T), vertices, FALSE);
  paint_list_vertices(triangles(T), vertices, TRUE);
  draw_triangle(*triangles(T), vertices, TRUE);
  wait();	/* il faut cliquer pour quitter */
  return 0;
}
Pour la mise en oeuvre, après avoir placé tous les fichiers (structure.h, structure.c, drawing.h, drawing.c, MacLib.h, MacLib.c et exemple.c) dans son répertoire de travail, on compilera par la commande :
gcc -g -Wall exemple.c drawing.c MacLib.c structure.c -L/usr/X11R6/lib -lX11 -lm

On remarquera que l'axe des y est orienté vers le bas. Il convient de ne pas s'en soucier lors de la programmation et de simplement considérer que l'affichage est inversé. Notamment, le sens trigonométrique direct se dessine dans le sens des aiguilles d'une montre.

Travail demandé

Les prototypes des fonctions à écrire sont donnés dans les fichiers geometry.h et triangulation.h. On pourra utiliser le fichier Makefile pour faciliter la mise en oeuvre.
  1. Orientation des triangles :
  2. Cocircularité :
  3. Ajout de triangles :
    On suppose une triangulation déjà construite et un point extérieur à tous les cocercles. Dans ce cas, pour étendre la triangulation, il suffit de trianguler entre ce point et tous les sommets de la portion "visible" de l'enveloppe convexe.
  4. Suppression de triangles :
    Écrire une fonction
    TList find_deleted_triangles(int p, Triangulation *list, Vertex v[]);
    qui prend en paramètres un point p et une triangulation (passée par variable) et qui partage la liste de triangles en deux, selon que les cocercles respectifs contiennent ou pas p.
    La valeur de la fonction retourne la sous-liste des triangles dont le cocercle contient p.
    Le paramètre T retourne la triangulation restreinte aux autres triangles.
  5. Ensuite... :
    Il faut traiter convenablement la liste des triangles à détruire pour permettre la bonne suite des opérations, soit une fonction
    void clear_triangles(TList deleted, Vertex v[]);
    Il reste alors à retrianguler correctement autour de p, à la place des triangles détruits, soit une fonction
    void redo_triangles(TList deleted, int p, Triangulation *T, Vertex v[]);
    la liste deleted donne les triangles détruits et les nouveaux triangles seront ajoutés à T. Pour écrire cette fonction, on pourra de nouveau utiliser new_linked_triangle. On fera attention au cas où on doit retrianguler une région qui touche l'enveloppe convexe et, en particulier, lorsque toute la triangulation est à refaire.


URL: https://www.enseignement.polytechnique.fr/profs/informatique/Philippe.Chassignet/00-01/TD_GSI/td_2.html

Pour toutes suggestions, commentaires ou remarques, email : Philippe.Chassignet@polytechnique.fr