faire du voronoi3D [Résolu]

[thomMonteillet]

Bonjour tous,

j'aimerai générer avec matlab des figures de Voronoi3D
==> comme l'image que j'ai mis en PJ

J'ai déjà posé ma question sur le forum matlab et il y a pas mal de fonction qui vont me permettre de faire ceci comme :
1) voronoi-> qui permet de faire des diagramme 2Dvoronoi
2) delaunay-> qui permet de faire de la triangulation
3) convhull-> qui permet de générer une enveloppe convexe de plusieurs points

le soucis est que je ne comprends pas vraiment le principe de la triangulation de voronoi...

pourriez vous m'expliquez en quelques mots comment faire ceci en 2D (afin que je comprenne le principe) tout d'abord et ensuite en 3D (ce que je compte reellement faire)?

je vous remercie pour l'aide que vous pourrez m'apporter

[magelan]

Bonjour,

le principe géométrique du diagramme de Voronoï en 2D est assez simple : "la frontière entre les cellules de Voronoi de deux germes distincts se situe forcément sur la médiatrice qui sépare ces deux germes" (cf Wikipedia). Je te laisse lire la suite de l'article.

Pour les algos, je te conseille de regarder les papiers qui ont été utilisés dans qhull.

Quel est ton but? écrire un code de génération de diagramme en 3D (en calculant toi-même les sommets des frontières) ou comprendre le principe puis utiliser des codes existants?

[thomMonteillet]

Bonjour Magelan et merci pour ton aide

Envoyé par magelan

le principe géométrique du diagramme de Voronoï en 2D est assez simple : "la frontière entre les cellules de Voronoi de deux germes distincts se situe forcément sur la médiatrice qui sépare ces deux germes" (cf Wikipedia). Je te laisse lire la suite de l'article.

je viens de relire ce passage est je pense avoir compris pour faire un diagramme de voronoi :
1°) je place des germes aleatoirement
2°) je prends le 1er germe du lot et je cherche ses voisins
3°) je je trace un segment entre ce germe et son voisin numero "i" et la droite perpendiculaire qui passera par le milieu de ce segment sera la frontiere
4°) je fais de même avec touts les voisins du gerne n°1
5°) je fais la meme chose pour tout les germes (sans refaire les couples deja effectués)
6°) l'intersection entre les frontieres permet de definir les sommets

es ce bien ceci ?

Par contre j'ai un probleme pour l'etape 6°) :
-> l'intersection des frontieres me donne les sommets je le comprends bien et à la main c'est facile à faire mais je ne vois pas comment mettre ceci en oeuvre algorithmiquement parlant ?

Envoyé par magelan

Pour les algos, je te conseille de regarder les papiers qui ont été utilisés dans qhull.

merci pour l'info, je regarderai lorsque j'aurais bien saisi le principe.

Envoyé par magelan

Quel est ton but? écrire un code de génération de diagramme en 3D (en calculant toi-même les sommets des frontières) ou comprendre le principe puis utiliser des codes existants?

dans un premier temps j'aimerai bien comprendre le principe pour utiliser un code existant (qhull?) mais ensuite j'aimerai bien arriver à faire ceci moi même ça m'éclaterai bien d'arriver à programmer ceci

[magelan]

Envoyé par thomMonteillet

Par contre j'ai un probleme pour l'etape 6°) :
-> l'intersection des frontieres me donne les sommets je le comprends bien et à la main c'est facile à faire mais je ne vois pas comment mettre ceci en oeuvre algorithmiquement parlant ?

Sur le principe c'est bien cela, mais tu auras un grand nombre de test à effectuer pour déterminer les sommets de chaque régions.

Une façon "simple" est de passer par la triangulation de Delaunay. Une fois cette triangulation obtenue, comme voronoi est le dual de delaunay, les sommets recherchés sont les centres des cercles circonscrits aux triangles de la triangulation. Le problème devient donc la triangulation, mais l'algorithme est plus simple que ceux utilisés pour le diagramme de Voronoï.

Sinon, il y a d'autres algorithmes comme ceux cités dans l'article anglais de wiki ou les nombreuses références que tu trouveras sur le net.

Envoyé par thomMonteillet

dans un premier temps j'aimerai bien comprendre le principe pour utiliser un code existant (qhull?) mais ensuite j'aimerai bien arriver à faire ceci moi même ça m'éclaterai bien d'arriver à programmer ceci

Comme tu utilises matlab, voici une toolbox gratuite qui génère des diagrammes de Voronoi 3D : Multi-Parametric Toolbox (MPT)

[thomMonteillet]

je te remercie pour toute ces explications.

merci aussi pour la toolbox !

A bientôt