Confondu avec l'algorithme de diagramme de Voronoi (ligne de balayage de Fortune)

Question

J'applique le diagramme de Voronoi pour trouver visuellement l'emplacement le plus proche sur une carte. En ce moment je veux le faire en utilisant des coordonnées entières (x, y) seulement dans un canevas.

Le problème est - je suis vraiment confus au sujet de cet algorithme. J'ai lu le livre de géométrie computationnelle, quelques autres théorie sur l'algorithme de Fortune. Et je suis vraiment confus maintenant. Cela me semble très complexe quand je vais coder.

S'il vous plaît me conseillez la mise en œuvre très simple du diagramme de voronoi (avec des coordonnées données). Veuillez me conseiller un code java, python ou scheme simple de préférence, sans thread, multi-threading, Delaunay Traingulation, couleurs fantaisistes, etc.

N'est-il pas possible d'implémenter un diagramme de Voronoi en utilisant l'algorithme de Fortune sans multithread ou hash map?

Answer 1

Le diagramme de Voronoï est juste un diagramme: pas une structure de données ou un algorithme. Je ne pense pas que ce soit approprié pour trouver le point le plus proche dans un ensemble. Construire le diagramme ne changerait pas la complexité asymptotique de votre problème, bien que cela compliquerait votre problème et réduirait la mémoire. Vous feriez mieux de mettre vos points dans un quadtree ou quelque chose de similaire. Si vous cherchez des algorithmes, le nom du problème que vous essayez de résoudre est "indexation spatiale". Le "point le plus proche" est l'un des problèmes résolus par les quadtrees et autres index spatiaux.

Answer 2

Cela semble compliqué parce que c'est compliqué! Vous n'avez pas besoin d'une table de hachage ou de threads, mais vous aurez besoin d'une file d'attente prioritaire (généralement implémentée en tas, disponible dans les bibliothèques standard java et python) et d'une arborescence qui vous permet de faire des requêtes de plage dans O (ceux dans les bibliothèques standard ne sont pas vraiment appropriés parce que vous ne pouvez pas obtenir à leurs internes, je suggérerais d'implémenter un AA tree). Et l'algorithme lui-même est encore assez poilu.

Pouvez-vous exécuter un programme externe? Si c'est le cas, je vous suggère vraiment de laisser le lourd travail de levage à QHull, ce qui est très bien dans les diagrammes de Voronoi. Bien mieux que nous ne le serons jamais, malheureusement.

Answer 3

Je regardais les diagrammes de Voronoi un peu l'année dernière et je peux certainement apprécier la confusion. Il existe quelques implémentations d'algorithmes de génération de diagrammes de Voronoï. Voir this page pour un couple, et aussi here. Comme mentionné, Qhull vaut certainement la peine d'être regardé - MATLAB l'utilise pour générer des diagrammes de Voronoi et des triangulations de Delaunay et des choses amusantes comme ça.

Answer 4

Voici une autre application en Ruby et C, y compris la visualisation:

http://github.com/abscondment/rubyvor/

Answer 5

De toute évidence, l'algorithme de la Fortune n'est pas trivial à mettre en œuvre. Surtout si vous consider numerical robustness issues chronologie. Vous ne dites pas quel langage de programmation vous voulez utiliser pour l'implémenter. Dans le cas où c'est le C++, vous pouvez trouver le travail d'Andriy Sydorchuk pour le projet Boost in frame of GSoC 2010: Sweepline Algorithm. L'implémentation d'Andriy est basée sur la bibliothèque Boost.Polygon. Les deux, l'implémentation de Voronoi et le Boost.Polygon s'appuient sur des coordonnées entières afin de fournir une robustesse numérique.

La conférence vidéo BoostCon sur Sweep-Line Algorithm for Voronoi Diagrams of Points, Line Segments and Medial Axis of Polygons in the Plane donne une très bonne explication de l'idée, des problèmes et des pièges.

Beaucoup de discussions liées à ce projet de Voronoi. passé dans la liste de diffusion Boost en 2010/2011.

Answer 6

I opened a github repository avec un port du papier original de Fortune. La mise en œuvre de Fortune a été très difficile à suivre, principalement en raison de la façon dont il a géré les structures de données.

This book semble beaucoup plus moderne

Fortune's original paper nécessite quelques lectures.

papier Ken Wong's décrit l'algorithme avec sans doute plus de clarté que la fortune dans l'article original

Ken Wong's presentation a de grandes diapositives (10, 11) sur la façon de traiter un site et un sommet

Il y a un interactive JavaScript demo (Archived version), vous pouvez regarder pour vous aider à visualiser l'algorithme. Un pdf décrit également l'algorithme.

Steven Fortune's original implementation is on his homepage.

This Stony Brook site listes plus implémentations

Triangle est "A deux dimensions de la qualité Mailleur et Delaunay Triangulator."

Il y a un entire book sur Voronoi diagrammes