1. Introduction

Ce projet vise à modéliser et visualiser le phénomène de percolation dans un milieu désordonné. Contrairement aux modèles de percolation sur grille carrée (modèles de "bond" ou "site" classiques), nous utilisons ici une tessellation de Voronoi. Cette approche est beaucoup plus proche des structures naturelles comme les milieux poreux, les tissus cellulaires ou les réseaux de capteurs irréguliers.

2. Architecture du Système

Le projet est décomposé en quatre modules interdépendants qui assurent la génération, la logique et l'affichage.

A. Génération Géométrique (Bowyer-Watson)

Pour obtenir les cellules de Voronoi, nous générons d'abord une Triangulation de Delaunay. L'algorithme de Bowyer-Watson procède de manière incrémentale :Insertion d'un point.Identification des triangles dont le cercle circonscrit contient ce point.Suppression de ces triangles pour former une cavité polygonale.Reliaison du nouveau point aux sommets de la cavité.

B. Structure de Données Spatiale (QuadTree)

Pour gérer efficacement des milliers de points, un QuadTree est utilisé. Il partitionne l'espace en quadrants, permettant de réduire la complexité des recherches de proximité lors de la construction des triangles.

C. Logique de Connexion (DSU - Disjoint Set Union)

Le DSU est le cœur décisionnel de la percolation. Il gère des ensembles disjoints et permet de répondre à la question : "Le bord gauche est-il connecté au bord droit ?" en un temps quasi-instantané grâce à la compression de chemin et l'union par rang.

3. Complexité Algorithmique

L'efficacité du programme repose sur la maîtrise des complexités temporelles de chaque étape.

ÉtapeAlgorithme {Complexité(Pire cas)Complexité (Moyenne)} :

• Génération DelaunayBowyer-Watson $O(N^2)$ et $O(N \log N)$ (avec QuadTree)
• VoisinageExtraction d'arêtes $O(T)$ (T = nbr triangles) $O(N)$ (car $T \approx 2N$ en 2D)
• Logique de groupeDSU (Union/Find) $O(\alpha(N))$ $O(1)$ (quasi-constant)
• Mise à jour RenduBoucle SFML $O(N)$ $O(N)$

Note : La fonction $\alpha(N)$ est la fonction inverse d'Ackermann, qui croît si lentement qu'elle est considérée comme constante ($< 5$) pour toute valeur de $N$ physiquement possible.

4. Interprétation Physique :

La Transition de Phase : Le simulateur met en évidence un phénomène critique. À mesure que la probabilité $p$ (porosité) augmente, la taille de la plus grande composante connexe augmente.

• Phase Isolante ($p < p_c$) : Les amas de cellules ouvertes (clusters de différentes couleurs) sont finis et localisés. Le fluide ne traverse pas.

Pour le seuil critique ($p = p_c$) : Apparition d'un "cluster géant" qui s'étend sur tout le domaine.

• Phase Conductrice ($p > p_c$) : Le chemin se densifie. Le milieu devient totalement perméable. Dans notre modèle de Voronoi, le seuil critique observé se situe souvent autour de $p \approx 0.52$ pour la percolation de sites, mais peut varier selon la distribution des points.

5. Applications Possibles

Ce projet, bien que visuel, possède des applications directes dans de nombreux domaines de l'ingénierie :

• Géologie & Industrie Pétrolière : Simulation de l'écoulement d'hydrocarbures ou d'eau à travers des roches sédimentaires poreuses.
• Science des Matériaux : Étude de la conductivité électrique dans des composites où des particules conductrices sont dispersées de manière aléatoire dans un isolant.
• Épidémiologie : Modélisation de la propagation d'un virus dans une population dont la répartition spatiale n'est pas uniforme.
• Télécommunications : Analyse de la robustesse d'un réseau de capteurs ou de bornes 5G (si une borne tombe en panne, le signal peut-il encore traverser la ville ?).
• Urbanisme : Étude de la connectivité des espaces verts ou des zones piétonnes dans une structure urbaine irrégulière.

6. Conclusion :

Ce simulateur démontre la puissance du couplage entre la géométrie algorithmique et la physique statistique. Grâce à l'optimisation via le QuadTree et la vélocité du DSU, nous parvenons à visualiser en temps réel un processus complexe, rendant palpable la notion de transition de phase pour l'œil humain.