Diagrammes de Voronoi

...

[pic 3]

cellule de Voronoi de x

[pic 4]

Intersection Projection Diagramme de Voronoi

Fig. 4 – Diagramme de Voronoi par projection

-

Algorithme de calcul par balayage

Dans ce paragraphe, on pr´esente un algorithme qui calcule le diagramme de Voronoi d’un ensemble S = {P1,...,Pk} de k points du plan en temps O(k lnk) par une m´ethode de balayage.

Le plan ´etant le plan horizontal de l’espace, on a vu (fig. 1 et probl`emes de croissance) que le diagramme de Voronoi d’angle π/4, d’axe vertical et de sommet Pi (donc d’´equation t = kXPik). L’algorithme de balayage va calculer uneS de S est la projection verticale sur le plan t = 0 de l’enveloppe convexe inf´erieure de i=1..k Ci, ou` Ci est le coˆne

projection sur le plan t = 0 de cette enveloppe convexe inf´erieure, mais au lieu de calculer la projection verticale, ce sera la projection parall`element `a la direction (0,1,−1) (fig. 5). Cette derni`ere projection va pouvoir ˆetre calcul´ee par balayage, et on pourra d´eduire du diagramme Vor′(S) ainsi obtenu le diagramme de Voronoi Vor(S). On d´efinit donc l’application

[pic 5] .

Cette application est continue. De plus, si D est une droite parall`ele `a l’axe (Oy), alors

[pic 6]

Fig. 5 – Projection parall`element `a une g´en´eratrice des coˆnes

- si D∩S = ∅, alors pour tout i ∈ {1..k}, et tous points M1 = (x,y1) et M2 = (x,y2) de D, avec y1 2, l’in´egalit´e triangulaire donne kM1Pik kM1M2k + kM2Pik.

Ainsi, les applications[pic 7] sont toutes strictement croissantes, donc par passage au minimum, α est strictement croissante sur D, donc injective.

- si Pi ∈ D ∩ S, α prend la mˆeme valeur sur tous les points de D situ´es avant Pi, mais reste injective apr`es Pi. On en d´eduit que α est injective et continue sur les ar`etes du diagramme de Voronoi de S. Ainsi, α transforme le diagramme Vor(S) en un diagramme Vor′(S) ayant la mˆeme structure combinatoire :

- la cellule VorS(Pi) de Vor(S) est envoy´ee sur une cellule Vor[pic 8]) de Vor′(S),

- l’arˆete V (Pi,Pj) s´eparant deux cellules adjacentes VorS(Pi) et VorS(Pj), et port´ee par la m´ediatrice de Pi et Pj est envoy´ee sur une arˆete V ′(Pi,Pj) qui s´epare les deux cellules Vor[pic 9] ) et Vor[pic 10]), et est port´ee par l’hyperbole projection (parall`element `a la direction (0,1,−1)) de l’intersection des deux coˆnes Ci et Cj.

- le sommet Mijℓ `a l’intersection des trois cellules VorS(Pi), VorS(Pj) et VorS(Pℓ) est envoy´e sur le sommet Mijℓ′ intersection de Vor[pic 11]), Vor[pic 12] ) et Vor[pic 13]

Pour retrouver le diagramme Vor(S) `a partir du diagramme Vor′(S), il suffit donc de suivre la structure combinatoire du second et de calculer les coordonn´ees des points Mijℓ.

On s’int´eresse donc maintenant au calcul effectif de Vor′(S). Le balayage est effectu´e par une droite ∆ parall`ele `a l’axe (Ox), qui se d´eplace dans le sens des ordonn´ees croissantes. `a chaque instant, on garde en m´emoire deux structures fondamentales :

- un dictionnaire D qui repr´esente les arˆetes de Vor′(S) qui intersectent ∆, tri´ees par abscisses croissantes, et les cellules que ces arˆetes s´eparent.

- une queue de priorit´e qui repr´esente les ´ev`enements qui n´ecessitent une mise `a jour, tri´es par ordonn´ees croissantes.Ces ´ev`enements sont de deux types :

- lorsque ∆ atteind un point Pi de S. Dans ce cas, une nouvelle r´egion VorS(Pi) est cr´e´ee et deux arcs sont ins´er´es dans D.

- lorsque ∆ atteind un point d’intersection de deux arcs. Dans ce cas, les deux arcs V ′(Pi,Pj) et V ′(Pj,Pℓ) sont remplac´es par un unique arc V ′(Pi,Pℓ) et la r´egion VorS(Pj) est supprim´ee de D.

Dans ces deux cas, chaque fois que deux arcs deviennent cons´ecutifs, on teste s’ils se rencontrent, et si tel est le cas, on ins`ere l’ordonn´ee de leur intersection dans la queue de priorit´e.

On parcourt ainsi toute la queue de priorit´e, et on a construit le diagramme Vor′(S).