Diagramme de Voronoï

On désigne par P un ensemble composé de n points de l'espace $\Re ²$ appelés aussi sites ou germes.

$$P = \left\{ p_i\in \Re ², i=1,\ldots,n \right\}$$ (4.1)

On appelle polygone de Voronoï associé au site Pi la région Vor(Pi) (chaque région étant l'ensemble de points (x,y) les plus proches à un point de P) telle que chaque point de P a pour plus proche site Pi.

$$Vor_P(Pi) = \left\{ x\in \Re ², d(x,Pi) \leq d(x,Pj),\forall Pj\in P-Pi\right\}$$ (4.2)

où d représente la distance Euclidienne.

L'union de l'ensemble des polygônes de Voronoï est appelé Diagramme de Voronoï. Un sommet de Voronoï est la rencontre de plusieurs arrêtes.

Voici quelques germes déposés au hasard de l'image, ainsi que leur polygône de Voronoï associé.

Figure 4.1: Diagramme de Voronoï

Le diagramme de Voronoï possède quelques propriétés remarquables :

• les polygônes sont convexes
• le diagramme couvre toute l'image
• une arrête de Voronoï sépare tout point de son plus proche voisin.
• chaque sommet des polygônes possède exactement 3 arrêtes
• pour chaque sommet S du diagramme de Voronoï, le cercle passant par les trois points voisins à ce sommet, ne contient aucun autre point de P.

Figure 4.2: Propriétés du'un diagramme de Voronoï

Dans la figure de gauche, le cercle passant par les trois points voisins d'un sommet de Voronoï, ne contient aucun autre germe de Voronoï. A l'inverse, la figure de droite n'est pas un diagramme de Voronoï car un site est présent à l'intérieur du cercle.

A partir du diagramme de Voronoï, nous pouvons construire le dual, appelé alors la triangulation de Delaunay.