Discussion :

[MonadicLabs]

Bonjour,
je recherche un algorithme pour la construction de diagramme de Voronoi en 3 dimensions... Ayant deja cherche sur google, je m'en remets maintenant a ce forum. Connaitriez vous un tel algorithme ?
Merci beaucoup.

PS: Je suis egalement alle chercher du cote de la librairie CGAL... Mais je n'ai rien trouve... J'ai peut etre mal lu la documentation.

[mchk0123]

Je ne vois pas en quoi les algorithmes de partitionnement de Voronoï ne peuvent pas être transposé de 2D en 3D.

La plupart des algorithmes de traitement d'images 2D le sont aussi pour la 3D. C'est juste un changement de dimension d'espace vectoriel.

[MonadicLabs]

Pourrais tu me donner quelques infos la dessus ?

[pseudocode]

Je ne vois pas en quoi les algorithmes de partitionnement de Voronoï ne peuvent pas être transposé de 2D en 3D.

La plupart des algorithmes de traitement d'images 2D le sont aussi pour la 3D. C'est juste un changement de dimension d'espace vectoriel.

Hum... Pour moi, Ce n'est pas si facile.

Si le principe des algos restent les memes, les operations typiques comme la "fusion de deux diagrammes" ou la "recherche+reconstuction des regions" deviennent plus complexe en 3D.

A priori, je dirais qu'il doit etre plus facile de generaliser l'algo de Watson/Bowyer plutot que celui du sweep-line. Mais c'est a voir

[mchk0123]

Ben je vois pas pourquoi :

Ton problème se ramène à trouver un maillage 3D des tes points sous forme de tétraèdres irréguliers.

Une fois que tu as ton maillage, le partitionnement de Voronoi est le même qu'en 2D : tu trace les segment de droites depuis le barycentre du tétraèdre vers les barycentre des facettes ; y a pas plus simple !

Pour le maillage, un petit post dans le forum des jeux 3D devrait te permettre de trouver ce que tu recherches.

[MonadicLabs]

Alors j'ai envoye un mail aux developpeurs de CGAL :

Monique.Teillaud@sophia.inria.fr <Monique.Teillaud@sophia.inria.fr> Mon, Apr 23, 2007 at 12:05 PM
To: xxx
Cc: cgal-develop@lists-sop.inria.fr
Hi,

We don't provide a structure like in 2D yet (the 2D Voronoi Diagram
Adaptor), but there are dual functions in the 3D Delaunay triangulation
class.

Best regards,
Monique Teillaud

Andreas Meyer wrote:
> ---------------------------- Original Message ----------------------------
> Subject: 3D Voronoi diagram ?
> From: xxx
> Date: Mon, April 23, 2007 8:07
> To: info@cgal.org
> --------------------------------------------------------------------------
>
> Hello,
>
> I was wondering if it was possible to generate 3D Voronoi diagrams with
> CGAL ...
> I can't find anything in the documentation though.
>
> Thanks in advance.

Voila.

Faut que je farfouille dans la doc, maintenant
En tout cas bravo a eux.

[pseudocode]

@MonadicLabs,mchk0123: visiblement vous avez eu la meme approche: construire une triangulation (enfin, une tetraedrisation) puis prendre son dual.

Moi je cherchais plutot a calculer directement le diagramme de Voronoi, sans passer par le dual.