Diagramme de Voronoï

Un article de Wikipédia, l'encyclopédie libre.
Aller à : navigation, rechercher
Un diagramme de Voronoï.

En mathématiques, un diagramme de Voronoï, aussi appelé décomposition de Voronoï, partition de Voronoï, polygones de Voronoï, tesselation de Dirichlet ou polygones de Thiessen, représente une décomposition particulière d’un espace métrique déterminée par les distances à un ensemble discret d’objets de l’espace, en général un ensemble discret de points. Il doit son nom au mathématicien russe Georgi Fedoseevich Voronoï (1868 - 1908).

Histoire[modifier | modifier le code]

On peut faire remonter l’usage informel des diagrammes de Voronoï jusqu'à Descartes en 1644 dans Principia philosophiae comme illustration de phénomène astronomique [1]. Dirichlet a utilisé des diagrammes de Voronoï en dimension 2 ou 3 dans son étude des formes quadratiques en 1850 (Dirichlet 1850).

En 1854, le médecin britannique John Snow a utilisé le diagramme de Voronoï des pompes pour montrer que la majorité des personnes mortes dans l’épidémie de choléra de Soho se trouvaient dans la cellule de la pompe à eau de Broad Street, donc qu'ils vivaient plus près de cette pompe que de n’importe quelle autre pompe[2]. Il a ainsi démontré que le foyer de l'infection était cette pompe.

Les diagrammes de Voronoï portent le nom du mathématicien russe Georgy Fedoseevich Voronoï (ou Voronoy) qui a défini et étudié le cas général en dimension n en 1908. Les diagrammes de Voronoi qui sont utilisés en géophysique et en météorologie pour analyser des données de distributions spatiales (comme les mesures de chutes de pluie) sont appelés polygones de Thiessen du nom du météorologiste américain Alfred H. Thiessen (en).

Définition[modifier | modifier le code]

Commençons par nous placer dans le plan affine \mathbb{R}^2. Soit S un ensemble fini de n points du plan ; les éléments de S sont appelés centres, sites ou encore germes.

On appelle région de Voronoï — ou cellule de Voronoï — associée à un élément p de S, l’ensemble des points qui sont plus proches de p que de tout autre point de S :

\mathrm{Vor_S}(p)=\{ x \in \mathbb{R}^2 \  /\  \forall q \in \mathrm{S}\  \| x - p \| \le \| x - q \| \}

où ||x - p|| désigne la distance entre x et p.

Si l'on appelle H(p, q) le demi-plan délimité par la médiatrice du segment [pq], on a

\mathrm{H}(p,q)=\{ x \in \mathbb{R}^2 \  /\  \| x - p \| \le \| x - q \| \}
\mathrm{Vor_S}(p)=\bigcap_{q \in \mathrm{S} \backslash \{ p\} } \mathrm{H}(p,q)

En dimension 2, il est facile de tracer ces partitions. On se base sur le fait que la frontière entre les cellules de Voronoï de deux germes distincts se situe forcément sur la médiatrice qui sépare ces deux germes. En effet, les points de cette médiatrice sont équidistants des deux germes donc on ne peut pas affirmer qu’ils se situent dans l'une ou l'autre cellule de Voronoi. Pour un ensemble de germes, le diagramme de Voronoï se construit donc en déterminant les médiatrices de chaque couple de germes. Un point d'une médiatrice appartient alors à une frontière de Voronoï s'il est équidistant d'au moins deux germes et qu'il n'existe pas de distance plus faible entre ce point et un autre germe de l'ensemble.

On peut généraliser la notion à un espace euclidien E muni de la distance euclidienne d. Soit S un ensemble fini de n points de E. La définition devient :

\mathrm{Vor_S}(p)=\{ x \in \mathrm{E}\  /\  \forall q \in \mathrm{S}\  \mathrm{d}(x,p) \le \mathrm{d}(x,q) \}

Pour deux points a et b de S, l’ensemble \Pi(a,b) des points équidistants de a et b est un hyperplan affine (un sous-espace affine de co-dimension 1). Cet hyperplan est la frontière entre l’ensemble des points plus proches de a que de b, et l’ensemble des points plus proches de b que de a.

\Pi(p,q)=\{ x \in \mathrm{E}\ /\ \mathrm{d}(x,p) = \mathrm{d}(x,q) \}

On note H(a, b) le demi espace délimité par cet hyperplan contenant a, il contient alors tous les points plus proches de a que de b. La région de Voronoï associée à a est alors l’intersection des H(a, b) où b parcourt S\{a}.

\mathrm{H}(p,q)=\{ x \in \mathrm{E}\  /\  \mathrm{d}(x,p) \le \mathrm{d}(x,q) \}
\mathrm{Vor_S}(p)=\bigcap_{q \in \mathrm{S} \backslash \{ p\} } \mathrm{H}(p,q)

Généralisation du diagramme de Voronoï[modifier | modifier le code]

Pour résoudre certains problèmes, Shamos[3] introduit la notion de diagramme de Voronoï d'un ensemble de points A (sous-ensemble de S), V(A), défini par :

\mathrm{V}(\mathrm{A}) = \{ x \in \mathrm{E} /\ \exists p \in \mathrm{A}, \forall q \in \mathrm{S} \setminus \mathrm{A}, \mathrm{d}(x, p) < \mathrm{d}(x, q) \}

Ainsi, V(A) est l'ensemble des points qui sont plus proche d'un point quelconque de A que de n'importe quel point n'étant pas dans A.

Si l'on appelle H(i, j) le demi-plan délimité par la bissectrice du segment [ij] et contenant i, alors on a :

\mathrm{V}(\mathrm{A}) = \{ \bigcap\mathrm{H}(i, j) /\ i \in \mathrm{A}, j \in \mathrm{S} \setminus \mathrm{A} \}

Les régions de Voronoï généralisées sont donc convexes, mais elles peuvent être vides. Shamos définit par la suite les diagrammes de Voronoï d'ordre k (1 ≤ k < card(S)) comme étant l'ensemble des cellules de Voronoï généralisées formées par tous les sous-ensembles de k points :

\mathrm{V}_k(\mathrm{S}) = \{ \bigcup \mathrm{V}(\mathrm{A}) /\ \mathrm{A} \subset \mathrm{S}, \mathrm{card}(\mathrm{A}) = k \}.

Les régions V(A) sont une partition de Vk(S).

Il définit également le « diagramme de Voronoï des points les plus éloignés » (farthest-point Voronoi diagram). Ce diagramme est construit en inversant le sens de l'inégalité

\overline{\mathrm{Vor}}_\mathrm{S}(p)=\{ x \in \mathrm{E}\  /\  \forall q \in \mathrm{S}\  \mathrm{d}(x,p) \ge \mathrm{d}(x,q) \}

Le point p ne se trouve évidemment pas dans la cellule VorS(p), mais à l'opposé par rapport au « centre » de l'ensemble : le point p est le point de S le plus éloigné de VorS(p).

Le diagramme des points les plus éloignés est entièrement déterminé par l'enveloppe convexe de S. Il ne contient pas de cellule fermée.

Ainsi, l'ensemble des points les plus éloignés d'un point p est l'ensemble des points qui sont plus proches des autres points de S :

\overline{\mathrm{Vor}}_\mathrm{S}(p)=\{ \bigcup \mathrm{Vor_S}(q) /\ q \in \complement_{\mathrm{S}}(\{p\}) \}

donc le diagramme des points les plus éloignés est identique à Vn - 1(S), n = card(S).

Propriétés[modifier | modifier le code]

Les régions de Voronoï sont des polytopes convexes en tant qu’intersection de demi espaces[4]. L’ensemble de tels polygones partitionne E, et est la partition de Voronoï correspondant à l’ensemble S.

Théorème — Soit v un point du plan. C'est un sommet d'un polygone de Voronoï si et seulement si c'est le centre d'un cercle passant par trois germes, et ne contenant aucun autre germe dans sa surface.


Relation avec la triangulation de Delaunay[modifier | modifier le code]

Superposition d’un diagramme de Voronoï et de sa triangulation de Delaunay duale
Superposition d’un diagramme de Voronoï (en rouge) et de sa triangulation de Delaunay (en noir)

Le diagramme de Voronoï d’un ensemble discret S de points est le graphe dual de la triangulation de Delaunay associée à S.

Passage du diagramme de Voronoï à la triangulation de Delaunay[modifier | modifier le code]

Chaque germe du diagramme de Voronoï constitue un sommet dans la triangulation de Delaunay. Ces sommets sont reliés entre eux par une arête si et seulement si les cellules sont adjacentes.

\mathrm{DEL}(\mathrm{S})=\{(p,q) \in \mathrm{S}^2 \ / \ \mathrm{Vor_S}(p) \cap \mathrm{Vor_S}(q)\ne \varnothing \}

Passage de la triangulation de Delaunay au diagramme de Voronoï[modifier | modifier le code]

Les sommets du diagramme de Voronoï sont les centres des cercles circonscrits des triangles de la triangulation de Delaunay. Les arêtes du diagramme de Voronoï sont sur les médiatrices des arêtes de la triangulation de Delaunay.

Représentation du diagramme[modifier | modifier le code]

Graphiquement, on représente en général les parois des cellules, c'est-à-dire les points qui sont à égale distance d'au moins deux centres, et les centres associés aux cellules. On représente parfois la cellule par un aplat de couleur, avec ou sans paroi, avec une couleur différente entre chaque cellule (voir Théorème des quatre couleurs).

D'un point de vue analytique, une cellule étant une intersection de demi-plan, elle peut être représentée comme le système d'équation de ces demi-plans (voir Géométrie analytique > Demi-plan) :

\left \{ \begin{matrix}
a_1 x + b_1 y \geqslant c_1 \\
a_2 x + b_2 y \geqslant c_2 \\
\cdots
\end{matrix} \right .

Pour représenter informatiquement un diagramme de Voronoï, John Burkardt[5] a proposé d'utiliser un fichier avec quatre types d'enregistrement :

  • s x y : point de l'ensemble S, de coordonnées (x, y) ;
  • v x y : sommet (vertex) d'un polygone de Voronoï, de coordonnées (x, y) ;
  • l a b c : droite (portant une arête d'un polygone), d'équation ax + by = c ;
  • e l v1 v1 : arête d'un polygone, décrit par l'indice l de sa droite porteur et les indices v1 et v2 des sommets qui sont ses extrémités ; si un indice est égal à -1, cela signifie que le sommet est « à l'infini » (demie droite, ou droite si les deux sommets sont à -1).

Exemple[modifier | modifier le code]

L'exemple suivant reprend les mêmes points que l'exemple de la triangulation de Delaunay : Exemple de diagramme de Voronoï.png

Algorithmes[modifier | modifier le code]

Algorithme de Green et Sibson[modifier | modifier le code]

Construction du diagramme de Voronoï selon l'algorithme de Green et Sibson.

En 1978, Peter Green et Robin Sibson[6] ont proposé un algorithme en O(n2). C'est un algorithme incrémental.

Soit S = {p1, p2, …, pn}. Supposons que le diagramme est construit pour les k premiers germes ; on ajoute le germe k + 1. Comme le diagramme de Voronoï est une partition du plan, le point pk + 1 est nécessairement dans (au moins) une région du diagramme de Voronoï des k premiers points ; soit q le germe de cette région.

On considère la médiatrice de [pk + 1q]. Comme la région est convexe, cette médiatrice a exactement deux points d'intersection avec les parois de la cellule. Soient x1 et x2 ces points d'intersection, le triangle qx1x2 étant orienté dans le sens direct. Le segment [x1x2] réduit la région Vor{p1, …, pk}(q), ce qui nous donne directement Vor{p1, …, pk + 1}(q).

La point x2 est sur la paroi d'une cellule, il appartient donc également à une cellule générée par un germe r. On considère alors la médiatrice de [pk + 1r], et ainsi de suite jusqu'à revenir au point x1. On trace ainsi une suite de parois qui font le tour du point pk + 1, et qui définissent de nouvelles cellules.

Algorithme de Shamos et Hoey[modifier | modifier le code]

Fusion de deux sous-diagramme par l'algorithme de Shamos.
  1. L'ensemble S est partitionné en G et D, dont on connaît les diagrammes de Voronoï V(G) et V(D).
  2. On fusionne les enveloppes complexes, et on trace les médiatrices des segments de raccordement.
  3. On construit la ligne de soudure P.
  4. Les diagrammes sont raccordés.

Shamos et Hoey ont démontré en 1975[3] qu'il est possible de calculer le diagramme de Voronoï d'un ensemble de n points du plan dans le temps O(n log n). Il utilise pour cela un raisonnement par récurrence : supposons que l'on puisse séparer l'ensemble S en deux sous-ensembles de même cardinal n/2, séparés par une droite verticale : l'ensemble G des points à gauche et l'ensemble D des points à droite. Les diagrammes respectifs de ces sous-ensembles, V(G) et V(D), sont connus, et on peut les fusionner.

On a ainsi un algorithme de type diviser pour régner, dont la complexité est O(n log n).

Il faut ensuite déterminer la complexité de la fusion des sous-diagrammes.

Il existe une ligne polygonale P telle que :

  • les points à gauche de cette ligne sont plus proches des points de G que de n'importe quel point de D ;
  • les points à droite de cette ligne sont plus proches des points de D que de n'importe quel point de G.

Cette ligne est celle qui séparera les cellules de V(G) et les cellules de V(D) qui se recouvrent. Cette ligne est monotone en y (l'intersection d'une droite horizontale y = cte avec P est un point unique), on peut donc construire cette ligne par un balayage simple des diagrammes V(G) et V(D).

On commence par raccorder les enveloppes convexes et G et de D ; cela nécessite la création de deux segments de droite [GinfDinf] et [GsupDsup], où \{\mathrm{G_{inf}}, \mathrm{G_{sup}} \} \in \mathrm{G} et \{\mathrm{D_{inf}}, \mathrm{D_{sup}} \} \in \mathrm{D} (ce sont des points des enveloppes convexes). Le premier élément de la ligne brisée est une demi-droite inférieure de la médiatrice de [GinfDinf] ; cette demi-droite s'arrête sur le premier segment de V(G) ou V(D) rencontré (dans la figure ci-contre, il s'agit de l'intersection d'un segment de chaque diagramme).

Si l'on continue tout droit, on pénètre dans la cellule d'un point de G, appelons-le G1, et dans la cellule d'un point D1 de D, on est donc proche de G1 et de D1. La ligne brisée P continue donc selon la médiatrice de [G1D1], et elle s'étend jusqu'à rencontrer un segment de V(G) ou de V(D). Et ainsi de suite, la ligne P suit des médiatrices de segments formés d'un point de G et d'un point de D. Elle se termine par une demi-droite portée par la médiatrice de [GsupDsup].

Cette ligne P tronque les diagrammes V(G) et V(D), et est leur ligne de raccordement.

Aux étapes élémentaires, on n'a que deux points, et les diagrammes sont évidemment délimités par la médiatrice.

La construction des enveloppes convexes est en O(n log n) ou O(n log m), m étant le nombre de points de l'enveloppe (mn). Le raccordement des enveloppes convexes et la construction de P sont en O(n). On a donc une complexité globale en O(n log n).

La construction du diagramme des points les plus éloignés se fait de a même manière, en partant de la partie supérieure de la médiatrice de [GinfDinf]. Lorsque l'on « entre » dans une cellule, on s'éloigne du point ayant servi à créer à cette cellule.

Algorithme de Fortune[modifier | modifier le code]

L'algorithme de Steven Fortune (1987, Laboratoires Bell AT&T)[7] a été démontré comme asymptotiquement optimal.

L'idée générale consiste à balayer le plan de gauche à droite avec une ligne verticale ; on construit le diagramme de Voronoï progressivement. Le problème est que le diagramme déjà construit, à gauche de la ligne, dépend de points situés à droite de cette ligne, et donc non encore pris en compte. Fortune résout ce problème en considérant un front parabolique légèrement « en retard » par rapport à la droite de balayage, tel que le diagramme situé à gauche de ce front est le diagramme final.

Applications[modifier | modifier le code]

Les diagrammes de Voronoï sont utilisés, ou réinventés sous de nombreux noms, dans différents domaines. Ils interviennent souvent lorsque l'on cherche à partitionner l'espace en sphères d'influence :

Bibliographie[modifier | modifier le code]

  • Johann Peter Gustav Dirichlet, « Über die Reduction der positiven quadratischen Formen mit drei unbestimmten ganzen Zahlen. », Journal für die reine und angewandte Mathematik,‎ 1850

Références[modifier | modifier le code]

  1. Principia philosophiae 1644, édition latine AT VIII-1; traduction française par Paul Picot, revue par Descartes, Les Principes de la philosophie, 1647 avec une Lettre-Préface AT IX-2
  2. (en) Steven Johnson, The Ghost Map : The Story of London's Most Terrifying Epidemic – and How it Changed Science, Cities and the Modern World, Riverhead Books,‎ 2006 (ISBN 1-59448-925-4), p. 195–196
  3. a, b et c (en) Michael Ian Shamos, Computational Geometry : thèse de doctorat, université Yale,‎ 1975
    (en) Michael Ian Shamos et Dan Hoey, « Closest-point problems », dans Proceeding of 16th Annual IEEE Symposium on Foundations of Computer Science, Los Angeles, IEEE Computer Society Press,‎ 1975 (lire en ligne), p. 151-162
  4. voir Ensemble convexe > Intersections de convexes
  5. Voronoi and Delaunay Calculations, Université d'État de Floride
  6. (en) Peter Green et Robin Sibson, « Computing Dirichlet tessellations in the plane », Computer Journal, vol. 21, no 2,‎ 1978, p. 168-173 (DOI 10.1093/comjnl/21.2.168, lire en ligne) ; le code source Fortran est disponible sur la page Peter Green Software/Tile (Université de Bristol)
  7. (en) Steven Fortune, « A Sweepline Algorithm for Voronoi Diagrams », Algorithmica, Springer-Verlag, vol. 1,‎ 1987, p. 153-174

Articles connexes[modifier | modifier le code]

Liens externes[modifier | modifier le code]