Confundido con el algoritmo del diagrama de Voronoi (línea de defensa de Fortune)

Question

Estoy implementando el diagrama de Voronoi para conocer visualmente la ubicación más cercana en un mapa. Ahora mismo quiero hacer esto usando coordenadas enteras (x, y) solo en un lienzo.

El problema es- Estoy realmente confundido acerca de este algoritmo. Leí el libro de Geometría Computacional, algunas teorías más sobre el algoritmo de Fortune. Y estoy realmente confundido ahora. Me parece muy complejo cuando voy a codificar.

Por favor, concédame la implementación muy simple del diagrama voronoi (con coordenadas dadas). Por favor, avísenme java o pitón simple o código de esquema preferiblemente sin hash, multihilo, Trazado de Delaunay, colores extravagantes, etc.

¿No es posible implementar el diagrama de Voronoi utilizando el algoritmo de Fortune sin multihilo o hash map?

Answer 1

El diagrama de Voronoi es solo un diagrama: no es una estructura de datos o un algoritmo. No creo que sea adecuado para encontrar el punto más cercano en un conjunto. La construcción del diagrama no cambiaría la complejidad asintótica de su problema, aunque haría su problema más complicado y menos eficiente en la memoria. Sería mejor que pusieras tus puntos en un quadtree o algo similar. Si está buscando algoritmos, el nombre del problema que está tratando de resolver es "indexación espacial". "Punto más cercano" es uno de los problemas resueltos por quadtrees y otros índices espaciales.

Answer 2

¡Parece complicado porque es complicado! No necesita una tabla hash o subprocesos, pero necesitará una cola de prioridad (generalmente implementada como un montón, y disponible en las bibliotecas estándar de java y python) y un árbol que le permite hacer consultas de rango en O (log n) (los que están en las bibliotecas estándar no son realmente adecuados porque no se puede acceder a sus partes internas; sugiero implementar un AA tree). Y el algoritmo en sí todavía es bastante peludo.

¿Se puede ejecutar un programa externo? Si es así, realmente sugiero que dejes el trabajo pesado al QHull, que es muy bueno en los diagramas de Voronoi. Mucho mejor que ninguno de nosotros, tristemente.

Answer 3

Estuve mirando los diagramas de Voronoi bastante el año pasado y ciertamente puedo apreciar la confusión. Hay algunas implementaciones de algoritmos de generación de diagrama de Voronoi. Ver this page para una pareja, y también here. Como se menciona twic, vale la pena mirar a Qhull: MATLAB lo usa para generar diagramas de Voronoi y triangulaciones de Delaunay y cosas divertidas como esa.

Answer 4

Aquí es otra aplicación en Ruby y C, incluyendo la visualización:

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

Answer 5

Obviamente, el algoritmo de la fortuna no es trivial de implementar. Especialmente si consider numerical robustness issues línea de tiempo. No dice qué lenguaje de programación quiere usar para implementarlo. En caso de que sea C++, puede encontrar el trabajo de Andriy Sydorchuk realizado para el proyecto Boost in frame of GSoC 2010: Sweepline Algorithm. La implementación de Andriy se basa en la biblioteca Boost.Polygon. Tanto la implementación de Voronoi como el Boost.Polygon dependen de coordenadas enteras para proporcionar robustez numérica.

La conferencia de video de BoostCon en Sweep-Line Algorithm for Voronoi Diagrams of Points, Line Segments and Medial Axis of Polygons in the Plane brinda una muy buena explicación de la idea, los problemas y las trampas.

Mucho debate relacionado con este proyecto de Voronoi. sucedió en la lista de correo de Boost en 2010/2011.

Answer 6

I opened a github repository con un original de puerto de Fortune. La implementación de Fortune fue muy difícil de seguir debido principalmente a cómo manejó las estructuras de datos.

This book parece mucho más moderno

Fortune's original paper requiere unas pocas lecturas.

Ken Wong's documento se describe el algoritmo con posiblemente más claridad que la fortuna en el documento original

Ken Wong's presentation tiene un gran toboganes (10, 11) en la forma de procesar un sitio y un vértice

Hay un interactive JavaScript demo (Archived version) puede mirar para ayudarlo a visualizar el algoritmo.

A pdf describe el algoritmo también.

Steven Fortune's original implementation is on his homepage.

This Stony Brook site listas implementaciones más

Triangle es "un Bidimensional calidad de la malla generador y Delaunay Triangulator."

Hay un entire book en los diagramas de Voronoi