Le projet

Ce projet à été développé avec la librairie Qt sous QtCreator et dispose donc de fichiers.pro permettant d'ouvrir un projet sous l'IDE ou de compiler en ligne de commande avec qmake.

Le projet est divisé en deux programmes:

Un programme principal utilisateur
Un programme de test des fonctionnalités

et plusieurs fichiers dont les principaux sont:

m_mesh.h, header de la classe Mesh, classe principale du programme
m_geometry.cpp, regroupe l'implémentation des fonctions de chargements de fichiers et des fonctions propres à la géometrie
m_topology.cpp, regroupe les fonctionnalités topologiques de base (notamment le flip, la marche incrémentale et Crust
m_topology_inc.cpp, regroupe les fonctionnalités propres à la triangulation incrémentale
m_topology_con.cpp, regroupe les fonctionnalités propres à la triangulation contrainte
predicate.h, regroupe les predicats utilisés (orientation de triangle, cercle circonscrit, intersection de segments...)
it_*.h présentent 3 itérateurs et circulateurs, un FaceIterator, un VertexCirculator et un ConvexHullCirculator

La répartition de l'implémentation des fonctions est détaillé dans m_mesh.h

Compilation

Pour compiler en ligne de commande, dans un terminal, à la racine du projet

$ mkdir build # crée deux exécutables bin/PavIn et bin/testPavIn
$ cd build # crée l'exécutable du programmme utilisateur
$ qmake ../TopoMesh/TopoMesh.pro # crée un makefile pour le programme principal
ou
$ qmake ../TopoMesh/TopoTest.pro # crée un makefile pour le programme de test
$ ./TopoMesh
$ ./TopoTest

Format des fichiers utilisés

Les nuages de points 2D sont définis dans des fichiers.tri et dans des fichiers.ctri pour les triangulations contraintes.
Les fichiers sont de la forme:

nbVertex nbEdgeContraints
x_0 y_0 #Coordonnées flottantes des points
x_1 y_1
...
x_NbVertex y_NbVertex
vA_0 vB_0 #Coordonnées entières des
vA_1 vB_1 #indices des sommets
...
vA_nbEdgeContraints vB_nbEdgeContraints

En noir les informations pour les fichiers.tri, en vert les informations rajoutées pour les fichiers de triangulations contraintes. Le répertoire data/ fourni contient quelques jeux de données.

Les fichiers cloud_N.tri représentent des nuages de N points.
Les fichiers line_*.tri représentent des nuages favorables pour l'application de l'algorithme de Crust.
Les fichiers cline_*.tri reprennent les nuages précédents en ajoutant quelques arêtes contraintes.

Fonctionnalités développées

Triangulation naïve
"Delaunayisation" de triangulation naïve
Triangulation incrémentale Delaunay
Marche incrémentale
Crust
Triangulation contrainte
Ruppert

Le programme

Le lancement du programme ouvre une fenêtre vide et proposant certaines options. Il est tout d'abords possible de charger des triangulations:

Non contraintes: File->Load tri...
Contraintes: File->Load ctri...

Le chargement ouvre une fenêtre de navigation dans le répertoire approprié pour le chargement demandé.

Triangulation non contrainte

Charger un fichier.tri affiche les points du nuage en rouge dans la fenêtre.
Il est alors possible de trianguler ce nuage:

De façon naïve: Triangulation->Naive triangulation
De façon incrémentale: Triangulation->Delaunay triangulation

Ensuite certaines opérations peuvent être faites sur la triangulation:

"Delaunayisation" de la triangulation: Operation->Lawson
Détection du contour: Operation->Crust

Enfin, certaines options d'affichage sont proposées:

Affichage de tous les cercles circonscrits: Display->Swap circles
Affichage du contour Crust: Display->Swap Crust (affiche les centres de Voronoï en bleu)

Triangulation contrainte

Charger un fichier.ctri affiche les points du nuage en rouge dans la fenêtre et les arêtes contraines en bleu ciel.
Il est alors possible d'effectuer les mêmes opérations que précédemment, mais surtout de trianguler avec contraintes.
De nombreux essais ont été menés pour arriver à raffiner une triangulation à l'aide de l'algorithme de Ruppert mais les résultats ne sont pas concluants.

Insertion interactive de points

Autant pour les triangulations contraintes que non, un mode d'ajout intéractif de point peut être lancé ou éteint via le bouton Add vertex mode. Allumé, ce mode permet de cliquer dans la triangulation et d'ajouter un point incrémentalement dans la triangulation.