Diagramme de Voronoï

Diagramme de Voronoï

Messagepar Alphonse Capriani » 03 Juil 2018 20:40

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

Image


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 !
Ya Ba Da Ba Dooo!!!
Avatar de l’utilisateur
Alphonse Capriani
 
Messages: 576
Inscription: 18 Juil 2009 19:10
Localisation: East Harlem - NY

Re: Diagramme de Voronoï

Messagepar P.Fradin » 03 Juil 2018 21:02

Salut Alphonse !

Merci pour ce code. Je vais pouvoir le regarder de près très bientôt puisque c'est quasiment les vacances !
P.Fradin
Avatar de l’utilisateur
P.Fradin
Administrateur du site
 
Messages: 1902
Inscription: 29 Oct 2008 15:04

Re: Diagramme de Voronoï

Messagepar Alphonse Capriani » 03 Juil 2018 22:03

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...
Ya Ba Da Ba Dooo!!!
Avatar de l’utilisateur
Alphonse Capriani
 
Messages: 576
Inscription: 18 Juil 2009 19:10
Localisation: East Harlem - NY

Re: Diagramme de Voronoï

Messagepar P.Fradin » 12 Juil 2018 11:46

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
DelaunayVoronoi.png (18.19 Kio) Consulté 10849 fois

Source :
DelaunayVoronoi.teg
(8.41 Kio) Téléchargé 1129 fois
P.Fradin
Avatar de l’utilisateur
P.Fradin
Administrateur du site
 
Messages: 1902
Inscription: 29 Oct 2008 15:04


Revenir vers Géométrie du plan

Qui est en ligne ?

Utilisateurs parcourant ce forum : Aucun utilisateur inscrit et 1 invité