Diagramme de Voronoï

[Alphonse Capriani]

Bonjour tout le monde.

Petit retour inatendu sous un soleil de plomb sur le forum.
Depuis quelques jours, ayant un peu plus de temps libre, je me suis remis à faire tourner TeXgraph pour le plaisir. Du coup, voici une petite création qui m'a permis de me remettre un peu dans le bain.

Il s'agit d'un diagramme de Voronoï avec la distance de Manhattan sur des points répartis aléatoirement dans le plan ; le code de celui-ci est disponible ici



J'en profite pour mettre le lien sur lequel j'uploaderai à l'avenir mes créations : elle regroupent le code et les images générés.
(Je précise que mon code n'est certainement pas optimal : je sais par exemple qu'il existe des algorithmes efficaces pour tracer de tels diagrammes. L'idée ici était juste de m'amuser un peu et de voir l'allure des diagrammes de Voronoï dans le cas de métriques plus exotiques)

Répertoire de travail Git

Bonne journée !

[P.Fradin]

Salut Alphonse !

Merci pour ce code. Je vais pouvoir le regarder de près très bientôt puisque c'est quasiment les vacances !

[Alphonse Capriani]

C'est un bitmap, donc du coup, je teste juste pixel par pixel quel point de ma liste est le plus proche. Donc forcément, c'est pas hyper rapide.

Il y a l'algorithme de Fortune qui existe pour déterminer les arêtes du diagramme de Voronoï, mais de ce que j'ai pu voir, il est valable uniquement avec la métrique euclidienne. Et puis, une fois qu'on a les arêtes, il faut réarranger tout ça pour faire de vrais polygones si on veut jouer avec les remplissages.

Tiens, il y a d'ailleurs une suggestion qui m'est venu pendant que je faisais ça : je vais alimenter la section correspondante...

[P.Fradin]

Salut,

J'ai essayé de mon côté de m'intéresser aux triangles de Delaunay et cellules de Voronoi, mais en métrique euclidienne. Le plus embêtant a été de recoller les arêtes pour faire les cellules de Voronoi. Il y a sûrement de l'optimisation à faire, mon truc doit être allègrement en $n^2$ !

Code: Tout sélectionner

[
view(-4.5,4.5,-4.5,4.5), Marges(0,0,0,0), size(6),
S:=[0.285+1.46*i,1.556-0.142*i,2.344+1.313*i,-2.38+1.218*i,1.548-0.624*i,
    0.969+1.819*i,-0.086-2.191*i,-0.477+1.834*i,-0.904+1.322*i,-2.892+0.025*i],
R:=Delaunay(S,V),// R=liste de : triangle,jump.
//V= liste de : triangle, centre du cercle circonscrit (point de Voronoi)
T:=Voronoi(V),// T=liste de : point, cellule de Voronoi correspondante, jump
palette := [purple, blue,  green,  yellow, orange,  red, crimson],
Color:=white, Width:=12, FillStyle:=full, k:=0,
for z in T By jump do
    FillColor:=Palette(palette,k/(Nops(S)-1)), Inc(k,1),
    Ligne(z[2,0],1) //dessin de la cellule
od,

Width:=8, Color:=gray, FillStyle:=none,
Ligne(R,1), // triangles de Delaunay
Color:=black, Point(S)  //montrer les points
]


DelaunayVoronoi.png (18.19 Kio) Consulté 10879 fois

Source :

DelaunayVoronoi.teg

(8.41 Kio) Téléchargé 1130 fois