Confuso con l'algoritmo del diagramma di Voronoi (la linea di venti della fortuna)

Sto implementando il diagramma di Voronoi per trovare visivamente la posizione più vicina in una mappa. In questo momento voglio farlo usando le coordinate intere (x, y) solo su una tela.Confuso con l'algoritmo del diagramma di Voronoi (la linea di venti della fortuna)

Il problema è che sono molto confuso su questo algoritmo. Ho letto il libro Computational Geometry, poche altre teorie sull'algoritmo di Fortune. E sono davvero confuso ora. Mi sembra molto complesso quando vado per la programmazione.

Si prega di consulenza me molto semplice implementazione del diagramma di voronoi (con coordinate date). Si prega di avvisarmi semplicemente java o python o codice di schema preferibilmente senza hash, multi-threading, Delaunay Traingulation, colori fantasiosi ecc.

Non è possibile implementare il diagramma di Voronoi usando l'algoritmo di Fortune senza multithreading o hash map?

fonte

2009-06-11 fireball003

Il diagramma di Voronoi è solo un diagramma: non una struttura di dati o un algoritmo. Non penso che sia adatto per trovare il punto più vicino in un set. Costruire il diagramma non cambierebbe la complessità asintotica del tuo problema, anche se renderebbe il tuo problema più complicato e meno efficiente in termini di memoria. Faresti meglio a mettere i tuoi punti in un quadruplo o qualcosa di simile. Se stai cercando algoritmi, il nome del problema che stai cercando di risolvere è "indicizzazione spaziale". "Punto più vicino" è uno dei problemi risolti dai quadrifogli e da altri indici spaziali.

fonte

2009-06-11 19:11:03

Sta cercando di rappresentare il vicino più prossimo visivamente-sovrapposizione di un diagramma di Voronoi su una mappa, in modo che si può vedere a colpo d'occhio, che X è più vicina ad un punto di interesse. – erickson

I diagrammi di Voronoi sono usati per risolvere i problemi vicini più vicini: http://en.wikipedia.org/wiki/Voronoi_diagram#Applications –

Il diagramma di Voronoi _è_ non solo un diagramma. È un _planar graph_ (uno in cui i bordi non si incrociano), con vertici e bordi bidirezionali. – bobobobo

Sembra complicato perché è complicato! Non hai bisogno di una tabella hash o di thread, ma avrai bisogno di una coda di priorità (solitamente implementata come heap e disponibile nelle librerie standard java e python) e di una struttura che ti consente di eseguire query di intervallo in O (log n) (quelli delle librerie standard non sono adatti perché non si può accedere ai loro interni, suggerirei di implementare un AA tree). E l'algoritmo stesso è ancora piuttosto peloso.

È possibile eseguire un programma esterno? Se è così, consiglio davvero di lasciare il sollevamento pesante allo QHull, che è molto buono nei diagrammi di Voronoi. Molto meglio di quanto nessuno di noi sarà mai, purtroppo.

fonte

2009-06-11 19:52:32

Capisco cosa intendi. Ma devo farlo da solo per la valutazione. Quindi, stavo cercando alcune semplici implementazioni che posso studiare e modificare/aggiungere al mio design. – fireball003

Stavo guardando i diagrammi di Voronoi un bel po 'l'anno scorso e posso certamente apprezzare la confusione. Esistono alcune implementazioni del diagramma di Voronoi che generano algoritmi in giro. Vedi this page per una coppia, e anche here. Come già detto, Qhull merita certamente di essere visto - MATLAB lo usa per generare diagrammi di Voronoi e triangolazioni di Delaunay e cose divertenti come quella.

fonte

2009-06-12 12:53:04

Ecco un'altra implementazione in Ruby e C, tra cui visualizzazione:

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

fonte

2010-02-01 21:33:43

Sarebbe bello poter spiegare come funziona l'implementazione o sarebbe d'aiuto dato che la domanda originale menziona l'uso di Java o Python e questa implementazione è in Ruby. – Srinivas

Ovviamente, l'algoritmo di Fortune non è banale da implementare. Soprattutto se si è linea temporale consider numerical robustness issues. Non si dice quale linguaggio di programmazione si desidera utilizzare per implementarlo. Nel caso sia C++, puoi trovare il lavoro di Andriy Sydorchuk per il progetto Boost in frame of GSoC 2010: Sweepline Algorithm. L'implementazione di Andriy è basata sulla libreria Boost.Polygon. Entrambi, l'implementazione di Voronoi e il Boost.Polygon si basano su coordinate intere per fornire robustezza numerica.

La lezione video BoostCon su Sweep-Line Algorithm for Voronoi Diagrams of Points, Line Segments and Medial Axis of Polygons in the Plane fornisce un'ottima spiegazione dell'idea, dei problemi e delle insidie.

Un bel po 'di discussioni relative a questo progetto Voronoi. è successo nella mailing list di Boost nel 2010/2011.

fonte

2011-10-27 13:34:32 mloskot

I opened a github repository con un porto di carta originale di Fortune. L'implementazione di Fortune è stata molto difficile da seguire soprattutto a causa del modo in cui ha gestito le strutture dati.

This book appare molto più moderno

Fortune's original paper richiede alcune letture.

Ken Wong's carta descrive l'algoritmo con probabilmente più chiarezza rispetto Fortune nel documento originale

Ken Wong's presentation ha grandi slitte (10, 11) su come elaborare un sito e un vertice

C'è un interactive JavaScript demo (Archived version) puoi guardare per aiutarti a visualizzare l'algoritmo.

A pdf descrive anche l'algoritmo.

Steven Fortune's original implementation is on his homepage.

This Stony Brook site liste più implementazioni

Triangle è "A Two-Dimensional Generator qualità Mesh e Delaunay Triangulator."

C'è un entire book il Diagramma di Voronoi

fonte

2013-06-19 03:50:26 bobobobo

grandi risorse! +1 –

Confuso con l'algoritmo del diagramma di Voronoi (la linea di venti della fortuna)

risposta

Problemi correlati