Régularisation

La géométrie algorithmique repose généralement sur l'utilisation de nombres exacts non représentables sur un ordinateur réel. Une solution consiste à utiliser des coordonnées entières et à faire du calcul exact sur celles-ci. Cette approche implique d'arrondir les résultats d'un algorithme si l'on veut pouvoir les réinjecter dans un autre algorithme.

Diagramme de Voronoï

Dans le cas du diagramme de Voronoï bidimensionnel, on cherche à arrondir les sommets de Voronoï aux points d'une grille en conservant les propriétés intéressantes du diagramme, telles que la planarité du plongement et la convexité des cellules.

Si on arrondit les sommets de Voronoï aux points de la grille les plus proches, il se peut que ces propriétés soient perdues. C'est ce qui arrive dans l'exemple à gauche, où le Voronoï exact (en bleu) est arrondi (en rouge) en créant une cellule non convexe (en jaune).

La figure à droite donne un exemple dans lequel il n'est pas possible d'arrondir le diagramme de Voronoï (bleu) sur la grille (orange) dans de bonnes conditions.

Condition suffisante

Lors de l'opération d'arrondi, un point est déplacé au pire de la demi diagonale d'un pixel de la grille. Étant donné un angle ABC on peut se placer dans le cas le plus défavorable pour l'arrondi A'B'C' et aboutir ainsi à une condition suffisante pour que l'arrondi au plus près donne un bon diagramme.

Pour en savoir plus


Last modified: Mon Nov 29 13:49:08 MET 1999 O. Devillers P.-M. Gandoin Thèmes Accueil PRISME same page in english