TIPE de Mathématiques : diagrammes de Voronoï

Résumé du document

Nous connaissons tous et cela dès l'enfance des animaux tels que la girafe ou la tortue. De même nous avons tous vu des images de déserts tellement arides que le sol craque. Mais y a-t-il un lien entre ces animaux et le sol d'un désert aride? Ce lien existe et ce sont les diagrammes de Voronoï.
Nous verrons tout d'abord ce qu'est un diagramme de Voronoï puis nous nous intéresserons aux principales applications.

Un espace topologique est un couple (E,T), où E est un ensemble et T un ensemble de parties de E que l'on appelle les ouverts de (E,T), vérifiant les propriétés suivantes :
1. L'ensemble vide et E sont ouverts ;
2. Toute réunion d'ouverts est un ouvert,
3. Toute intersection de deux ouverts est un ouvert,
- L'ensemble T est appelé topologie de E. Il résulte de la théorie élémentaire des ensembles que toute intersection finie d'ouverts est un ouvert.
- Les fermés d'une topologie sont les complémentaires des ouverts. Par conséquent, la famille des fermés contient E et l'ensemble vide.

La formule d'Euler
La caractéristique d'Euler - ou d'Euler-Poincaré - est un invariant numérique, un nombre qui décrit un aspect d'une forme de l'espace topologique ou de la structure.

Extraits

[...] 13) Flip d'une arête illégale. Test d'une arête. 14) Flip d'une arête illégale. Test d'une arête 15) Choix d'un point au hasard, recherche du triangle, subdivision. Test d'une arête. 16) Choix d'un point au hasard, recherche du triangle, subdivision. Test d'une arête. 17) Flip d'une arête illégale. Test d'une arête. 18) Choix d'un point au hasard, recherche du triangle, subdivision. Test d'une arête. 19) Flip d'une arête illégale. Test d'une arête. [...]

[...] Ces segments de droite sont les arêtes du diagramme de Voronoï. En pratique, si les points sont répartis à peu près au hasard dans on constate expérimentalement (voir figure qui suit) les faits suivants : 1. les nœuds du maillage ou sommets définis par le découpage en zones sont le plus souvent communs à exactement trois d'entre elles; 2. pour un diagramme de Voronoï associé à r points, lorsque r est grand, le nombre moyen de côtés des zones est le plus souvent voisin de 6. [...]

[...] Les traits délimitent la frontière de la région considérée. Le graphe associé au diagramme de Voronoï de gauche a 8 sommets arêtes et 4 faces. Le graphe associé au diagramme de Voronoï de droite a 10 sommets arêtes et 5 faces. Les sommets intérieurs sont de degré 3 Plan de l'étage avec la trajectoire du robot Les traits en gras représentent les murs, les traits fins le diagramme de Voronoï et les cercles les positions successives du robot. [...]

[...] Et toutes les triangulations ne sont pas des triangulations de Delaunay. Sur la figure de la page suivante on peut observer deux triangulations différentes. En traçant les cercles circonscrits aux triangles, on se rend compte que l'une de la triangulation est illégale, c'est-à-dire que ce n'est pas une triangulation de Delaunay. En effet, on peut voir sur la figure de gauche que le cercle circonscrit à l'un des triangles contient l'un des sites de la triangulation et ne satisfait donc pas à la propriété caractéristique de la triangulation de Delaunay. [...]

[...] Triangulation de Delaunay et maillages Voici comment on peut réaliser un maillage à partir d'un nuage de points. Initialisation à l'aide d'un très grand triangle englobant tous les points de P Choix d'un point au hasard, recherche du triangle, subdivision. Pas d'arête illégale. Choix d'un point au hasard, recherche du triangle, subdivision. Test d'une arête. Choix d'un point au hasard, recherche du triangle, subdivision. Test d'une arête. Quadrilatère non convexe. Choix d'un point au hasard, recherche du triangle, subdivision. Test d'une arête. [...]