Delaunay

Triangulation d'un nuage de points en 2D 1/2.

Caractéristiques

Langages	C
Librairies	OpenGL, Glut
Gestionnaire de version	Mercurial
Version	1.0
Téléchargement	TP_Delaunay.tar.gz
Origine	Projet (Master 2 IMAGE : Géométrie Algorithmique)
Licence	LGPL

Description

Ce programme permet d'obtenir une triangulation dite Delaunay en 2D 1/2 à partir d'un nuage de point généré aléatoirement. L'algorithme implémenté utilise une file de priorité qui contient les triangles. Pour déterminer la priorité d'un triangle, on calcule la distance de la projetée verticale au triangle pour chacun des vertices qu'il contient dans sa projection 2D sur le plan. Le triangle ayant la plus grande distance (en valeur absolue) se trouve toujours en tête.

À chaque itération on va diviser le triangle en tête de de file en trois à partir de son point ayant la plus grande distance verticale. On continue d'itérer par exemple sur un nombre d'itérations définies, ou jusqu'à ce que le triangle de tête de liste ne contienne plus de vertex.

Au niveau des performances, sur un ordinateur portable équipé d'un processeur Intel Core i7 3612 QM cadencé à 2.1 GHz et disposant de 8 Go de RAM DDR3, 1 000 000 de points sont triangulés en moins de 7 secondes.