Quels sont les algorithmes faciles à mettre en œuvre pour réaliser un diagramme de Voronoï ?
Je n'ai pas pu trouver d'algorithme spécialement sous forme de pseudo. Veuillez partager des liens vers des algorithmes de diagramme de Voronoï, des didacticiels, etc.
Un algorithme simple permettant de calculer la triangulation de Delaunay d'un ensemble de points est le suivant bords retournés . Comme une triangulation de Delaunay est le graphe dual d'un diagramme de Voronoï, vous pouvez construire le diagramme à partir de la triangulation en temps linéaire.
Malheureusement, le temps d'exécution le plus défavorable de l'approche par retournement est O(n^2). Il existe de meilleurs algorithmes, comme le balayage de ligne de Fortune, qui prennent O(n log n). Cette méthode est cependant quelque peu délicate à mettre en œuvre. Si vous êtes paresseux (comme moi), je vous suggère de chercher une implémentation existante d'une triangulation de Delaunay, de l'utiliser, puis de calculer le graphe dual.
En général, un bon livre sur le sujet est Géométrie computationnelle par de Berg et al.
Le plus simple ? C'est l'approche par la force brute : Pour chaque pixel de la sortie, on itère sur tous les points, on calcule la distance, on utilise le plus proche. C'est très lent, mais très simple. Si les performances ne sont pas importantes, cela fait l'affaire. J'ai moi-même travaillé sur un raffinement intéressant, mais je cherche toujours à savoir si quelqu'un d'autre a eu la même idée (plutôt évidente).
L'algorithme de Bowyer-Watson est assez facile à comprendre. Voici une implémentation : http://paulbourke.net/papers/triangulate/ . C'est une triangulation delaunay pour un ensemble de points mais vous pouvez l'utiliser pour obtenir le dual du delaunay, c'est-à-dire un diagramme de voronoï. L'arbre de portée minimale est un sous-ensemble de la triangulation delaunay.
La page Wikipedia ( http://en.wikipedia.org/wiki/Voronoi_diagram ) a une section Algorithmes avec des liens vers des algorithmes pour la mise en œuvre des diagrammes de Voronoï.
Il existe une implémentation de Voronoï pour les graphes à 2 dimensions en C et en C++, librement disponible, de Stephan Fortune / Shane O'Sullivan :
VoronoiDiagramGenerator.cpp
VoronoiDiagramGenerator.h Vous le trouverez à de nombreux endroits. Par exemple, chez http://www.skynet.ie/~sos/masters/
Largement référencé, non documenté, et presque toutes les réimplémentations que j'ai vues basées sur ce code sont fausses (dans différents langages, beaucoup de gens ont besoin de Voronoi, peu le comprennent assez bien pour le porter correctement). Les seuls portages fonctionnels que j'ai vus proviennent de la communauté scientifique/académique et ont des signatures de fonctions massivement sur-compliquées - ou massivement optimisées (de sorte qu'elles ne peuvent pas être utilisées pour la plupart des objectifs) ce qui les rend inutilisables par des programmeurs normaux.
Prograide est une communauté de développeurs qui cherche à élargir la connaissance de la programmation au-delà de l'anglais.
Pour cela nous avons les plus grands doutes résolus en français et vous pouvez aussi poser vos propres questions ou résoudre celles des autres.
1 votes
Voir le code et l'API à saturnapi.com/vpartition/voronoi-seed-partition-plot