Applet: diagrammes de Voronoi en geometrie taxi

Imaginons le probleme suivant: une compagnie de taxi a etabli un certain nombre de stations a travers une ville. Pour pouvoir les exploiter pleinement, il est important pour elle de savoir associer, a n'importe quel point de la ville, la station la plus proche. Ainsi, leurs taxis peuvent repondre aux appels le plus rapidement possible. (Bien sur, nous allons utiliser une ville bien particuliere ou il n'y a ni embouteillages, ni feux rouges ni arrets stop, etc...)

Ceci est l'exemple parfait de probleme tres naturel pour lequel la geometrie taxi est utile. Il est clair que pour resoudre ce probleme, il suffit de trouver l'ensemble des points qui sont equidistants de leur deux plus proches stations. Cet ensemble partitionnera le plan en regions (une par station) qui corresponderont donc aux points que cette station desservira.

Dans l'introduction, nous avons examine le cas de deux points. Le probleme est un peu plus complexe lorsque l'on considere trois points ou plus. En fait, il n'est pas du tout evident de trouver une facon efficace de construire ces limites entre les differentes regions. Vous pouvez peut-etre prendre ici le temps d'essayer de construire ce diagramme pour 3 points et vous realiserez sans doute que cela peut devenir un peu melangeant.

En geometrie, le diagramme correspondant (decouper le plan en regions dont les points sont plus pres d'une station) s'appelle le diagramme de Voronoi, et il est beaucoup utilise en geometrie (dans un contexte informatique) et en reconnaissance de forme. Le but de l'applet presenti ci-dessous est de calculer le diagramme de Voronoi en geometrie taxi. Bien sur, les diagrammes de Voronoi peuvent etre definis pour n'importe quelle notion bien definie de distance, et il existe un programme, DUST, qui les calculent dans differents espaces metriques.
 
Pour trouver le diagramme de Voronoi d'un ensemble de points, l'applet utilise ce que l'on appelle la transformation "feu de prairie", quoique dans notre contexte, il faudrait l'appeller plutot la transformation "ouragan de taxis". L'idee en est assez simple, supposons qu'a un moment precis, une grande quantite de taxis partent de chaque station. Supposons aussi que ces taxis ne fassent jamais demi-tour et augmentent sans cesse la distance qui les separent de leur station d'origine. Alors, le diagramme de Voronoi en geometrie taxi est simplement l'ensemble des points ou des taxis de stations differentes se rencontrent.
   

Comment utiliser l'applet:

-Vous pouvez rajouter ou enlever des stations en cliquant dans la ville. (rectangle blanc)
-Le boutton Go! button fait avancer tous les taxis d'un bloc.
-Le boutton Clear efface tous les taxis et toutes les stations.
-Les lignes rouges constituent le diagramme de Voronoi en geometrie taxi.

(Note: Pour assurer une certaine efficacite a l'applet, la ville est relativement petite, et les diagrammes de Voronoi n'ont pas l'air parfaits. Ils donnent cependant l'idee generale.)

Merci a Xavier Thibaud pour son aide dans la construction de cet applet. J'ai egalement utilise le code source d'autres applets, ecrits par des etudiants de McGill, pour me familiariser avec Java.
 

De retour a la page titre

Bibliographie et autres liens