Page 1 sur 1

Diagramme de Voronoï

MessagePublié: 03 Juil 2018 20:40
par 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

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 !

Re: Diagramme de Voronoï

MessagePublié: 03 Juil 2018 21:02
par 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 !

Re: Diagramme de Voronoï

MessagePublié: 03 Juil 2018 22:03
par 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...

Re: Diagramme de Voronoï

MessagePublié: 12 Juil 2018 11:46
par 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
DelaunayVoronoi.png (18.19 Kio) Consulté 5702 fois

Source :
DelaunayVoronoi.teg
(8.41 Kio) Téléchargé 692 fois