Triangulation de Delaunay

La construction des triangles de Delaunay à partir d'un diagramme de Voronoï est assez simple. En effet, l'algorithme de Delaunay recherche premièrement les germes voisins (donc séparés par un arrête de Voronoï), pour chaque germe du Diagramme, et les relie entre eux. Comme le montre la figure suivante :

**Figure 4.3:** Du diagramme de Voronoï aux Triangles de Delaunay
$\begin{figure} \begin{center} \epsfig{file=image78.eps,scale=1.0} %\\ \end{center} \end{figure}$

Notons que seul le couple de points (point à gauche, point à droite), ne possède pas d'arrête de Voronoï, ils ne sont donc pas reliés (figure de droite). Cet algorithme garantit la génération de triangles, ce pourquoi il est appelé Triangulation de Delaunay. Une triangulation de Delaunay est unique, et hérite des propriétés du Diagramme de Voronoï (les triangles ne se recouvrent pas etc...).

Voici une illustration du Diagramme de Voronoï, et de sa Triangulation de Delaunay réciproque.

**Figure 4.4:** Diagramme de Voronoï, Partition de Delaunay
$\begin{figure} \begin{center} \epsfig{file=image79.eps,scale=1.0} %\\ \end{center} \end{figure}$

La Triangulation de Delaunay livre par conséquent une partition de l'image sous la forme de figures triangulaires. Nous pouvons dès lors entreprendre une compression.

Remarque : La conception de ce genre de segmentation étant assez complexe à réaliser, nous avons utilisé un algorithme conçu par M. AUDIBERT, et implémenté (en C) par Franck DEPOORTERE. Les fonctions de triangulation ont été modifiées afin d'être compatibles avec notre projet. L'algorithme de calcul de la triangulation de Delaunay est reproduit ci-dessous :

$\begin{algorithm} % latex2html id marker 550 [H] \begin{algorithmic}[1] \par \F... ...algorithmic} \caption{Calcul de la Triangulation de Delaunay} \end{algorithm}$

Il existe d'autre algorithme de calcul de la triangulation de delaunay, nous verrons par la suite que celui-ci possède plusieurs faiblesses.

julien michot 2006-08-13