¿Cómo puedo obtener un diccionario de células a partir de estos datos del diagrama de Voronoi?

Question

El uso de la biblioteca de generación de diagrama de Voronoi/Delaunay encontró in this program, que se basa en la implementación original de la Fortuna de his algorithm, con un conjunto aleatorio de puntos como datos de entrada, soy capaz de obtener los siguientes datos de salida:

1. Una lista de los bordes del Delaunay Triangulation, lo que significa que para cada punto de entrada, puedo ver qué puntos de entrada son sus vecinos. No parecen estar en ningún orden particular.
2. Una lista de pares de vértices del Voronoi Diagram, que puedo usar para dibujar el diagrama de Voronoi una línea a la vez. De nuevo, aparentemente sin un orden en particular.
3. Una lista sin nombre de pares de puntos, que parece ser la misma lista que 2, pero en un orden diferente.
4. Una lista de los vértices formados en el diagrama de Voronoi, aparentemente sin ningún orden en particular.

Aquí es un ejemplo de los datos de una prueba de funcionamiento de mi programa utilizando esta biblioteca:

Input points: 
0 (426.484, 175.16) 
1 (282.004, 231.388) 
2 (487.891, 353.996) 
3 (50.8574, 5.02996) 
4 (602.252, 288.418) 

Vertex Pairs: 
0 (387.425, 288.533) (277.142, 5.15565) 
1 (387.425, 288.533) (503.484, 248.682) 
2 (277.142, 5.15565) (0, 288.161) 
3 (387.425, 288.533) (272.213, 482) 
4 (503.484, 248.682) (637.275, 482) 
5 (503.484, 248.682) (642, 33.7153) 
6 (277.142, 5.15565) (279.477, 0) 

Voronoi lines?: 
0 (279.477, 0) (277.142, 5.15565) 
1 (642, 33.7153) (503.484, 248.682) 
2 (503.484, 248.682) (637.275, 482) 
3 (387.425, 288.533) (272.213, 482) 
4 (277.142, 5.15565) (0, 288.161) 
5 (387.425, 288.533) (503.484, 248.682) 
6 (277.142, 5.15565) (387.425, 288.533) 

Delaunay Edges: 
0 (282.004, 231.388) (487.891, 353.996) 
1 (602.252, 288.418) (487.891, 353.996) 
2 (426.484, 175.16) (487.891, 353.996) 
3 (426.484, 175.16) (602.252, 288.418) 
4 (50.8574, 5.02996) (282.004, 231.388) 
5 (426.484, 175.16) (282.004, 231.388) 
6 (50.8574, 5.02996) (426.484, 175.16) 

Vertices: 
0 (277.142, 5.15565) 
1 (503.484, 248.682) 
2 (387.425, 288.533) 
3 (0, 288.161) 
4 (272.213, 482) 
5 (637.275, 482) 
6 (642, 33.7153) 
7 (279.477, 0) 

Si bien la información es la adecuada si todo lo que necesito es para dibujar los diagramas de Voronoi y Delaunay, se no es suficiente información para el trabajo real que estoy tratando de hacer con estos diagramas. Lo que necesito es un diccionario de polígonos formado por los vértices de Voronoi, indexados por el punto de entrada en torno al cual se formó cada polígono. Preferiblemente, para cada polígono, estos puntos se ordenarían en el sentido de las agujas del reloj.

Con la información anterior, podría asignar implícitamente datos a cada región, asignar datos a las esquinas si es necesario, decir qué regiones comparten los bordes (utilizando los bordes de Delaunay), y hacer el análisis correspondiente.

Así que en resumen, cómo puedo usar los datos disponibles para armar un diccionario en el que la clave es uno de los puntos de entrada, y los datos indexados por esa clave son una lista de los vértices de Voronoi que forman el polígono circundante? O, como alternativa, ¿esa información está implícita en alguna parte en los datos que se me han proporcionado?

Answer 1

El algoritmo de Fortune es O (n log n) - pero su código será O (n^2), si intenta reconstruir las celdas de la fuerza bruta según lo propuesto por Alink.

El punto de partida para mi respuesta es que lo que está utilizando para generar las celdas no es una biblioteca, sino que simplemente es a class written to neatly wrap up the code originally presented by Fortune himself, y no es realmente una biblioteca madura. Entonces, el autor de hecho no ha anticipado sus necesidades, y aunque la información que desea ha sido calculada, no es accesible.

Internamente, sus puntos de entrada se almacenan como instancias de la struct "sitio", y el algoritmo procede a crear half-edges, cada uno de los cuales mantiene una referencia "vértice" que es un puntero al Sitio encierra. Al caminar a la mitad de los bordes, circunnavegas el sitio cerrado de forma natural, exactamente lo que necesitas.

Para acceder a esta información, sugerí modificar o ampliar la clase VoronoiDiagramGenerator; Lo haría creando una tabla hash con los punteros del sitio como la clave y un único puntero HalfEdge como valor. A continuación, modifique el método generateVoroni, insertar el nuevo código inmediatamente después de la llamada a Voronoi:

For each HalfEdge in ELHash 
     Get table entry for current half edge's Site 
     If site in table has null HalfEdge reference 
      set current HalfEdge reference 
     End If 
End For each 

... y no es su diccionario. Ese único medio borde te permitirá "recorrer" el perímetro del polígono que encierra el sitio relacionado, que creo que es lo que pediste. Su próximo problema será descubrir de manera eficiente cuyo polígono encierra algún nuevo punto de datos, pero esa es otra pregunta :-). Espero que consideres compartir tu clase completada, debería ser significativamente más útil que la clase base.

Editar: Aquí es una excelente presentación descibing todo lo dicho anteriormente en imágenes: http://ima.udg.es/~sellares/ComGeo/Vor2D_1.ppt:

• definición de Diagrama Voronoy
• árbol de medias de bordes (ver las fotografías.más adelante) algoritmo
• Fortunas en imágenes

Y aquí es una aplicación de C# que podría ayudarle a recuperar el diccionario, como se propone más arriba: http://www.codeproject.com/Articles/11275/Fortune-s-Voronoi-algorithm-implemented-in-C

Answer 2

Se podía utilizar Triángulo: http://www.cs.cmu.edu/~quake/triangle.html

Answer 3

Su lista de bordes es de algún modo incompleto, es necesario añadir los que está en la frontera del rectángulo que contiene proporcionado a la llamada de la biblioteca (642.482 parece ser aquí). Técnicamente, una subdivisión de Voronoi debe usar algunos bordes infinitos, pero todos son finitos. Supongo que también quieres estos polígonos "abiertos" cerca de este borde, ya que todos son así en tu ejemplo.

Agregar esos bordes de borde no parece difícil, simplemente tedioso. Probablemente algo así como, para cada lado del rectángulo principal, encontrar todos los vértices en él (ignorando las esquinas), ordenarlos (por x para el horizontal, por y para vertical) y dividir ese lado utilizando estos valores. Esto genera los bordes que faltan, pero no los agrega directamente a su lista principal, ya que son especiales ya que son los únicos que no separan dos celdas.

Por lo tanto, para la pregunta en sí, yo diría esto: En su lista principal de bordes (proporcionada por la biblioteca), cada borde separa dos celdas y si encontramos cuáles, podemos simplemente asignar esa ventaja a cada una de estas celdas Como una celda es equivalente a un punto de entrada, tendremos el diccionario deseado, excepto con una lista de bordes en lugar de vértices, pero eso es fácil de convertir.

Ahora para obtener estas 2 celdas: Calcule el punto medio del borde y, a partir de esto, busque los dos puntos de entrada más cercanos simplemente recorriendo la lista manteniendo las 2 distancias más pequeñas. Por las propiedades de la estructura de Voronoi, esos dos son los que forman las dos células. Tenga en cuenta que estas dos distancias deben ser iguales, pero la imprecisión del flotador probablemente introducirá una ligera diferencia.

Para finalizar, agregue los bordes del borde que hemos generado a lo largo del rectángulo principal, pero para ellos, simplemente use el primer punto de entrada más cercano, ya que solo están adyacentes a una celda.

Finalmente, podemos convertir cada lista de bordes en una lista de vértices (volcar cada punto de los extremos en un conjunto). Si desea clasificarlos en el sentido de las agujas del reloj, tenga en cuenta que se trata de un polígono convexo con un punto de entrada dentro. Por lo tanto, puede generar el vector que va del punto de entrada a cada vértice, calcular su ángulo desde un eje (use std :: atan2 (x, y)) y usar este ángulo como valor de comparación para ordenarlos (ver std :: ordenar).

Answer 4

Utilicé el paquete Triangle para generar la triangulación Dalaunay: http://www.cs.cmu.edu/~quake/triangle.html

Funciona en 2 modos: a) como una utilidad triangulate.exe y b) como una biblioteca de C compilarlo como una utilidad sólo tiene que compilar y ejecutar triangle.c:

triangulate -vZ input.poly 
    #v -voronoy, Z - starting from 0 index 

a conseguir diagrama de Voronoi (Consulte el manual sobre .poly format) he hecho un experimento con sus datos de entrada en un archivo de este tipo .poly:

# <# of vertices> <dimension (must be 2)> <# of attributes> <# of boundary markers (0 or 1)> 
5 2 0 0 
# Following lines: <vertex #> <x> <y> [attributes] [boundary marker] 
0 426.484 175.16 
1 282.004 231.388 
2 487.891 353.996 
3 50.8574 5.02996 
4 602.252 288.418 
#One line: <# of segments> <# of boundary markers (0 or 1)> 
5 0 
#Following lines: <segment #> <endpoint> <endpoint> [boundary marker] 
0 0 1 
1 1 2 
2 2 3 
3 3 4 
4 4 0 

Pero simplemente informa de error de datos de entrada.

• Al trabajar con este paquete, diría que a menudo no funciona con los datos de entrada que informan un error. Solo acepta polígonos de entrada (no puntos aleatorios), y el problema aquí es que tiene un polígono de entrada que se interseca a sí mismo.
• No responde a su pregunta, una información solo conjunto de puntos, no un diccionario

Answer 5

http://svn.osgeo.org/qgis/trunk/qgis/python/plugins/fTools/tools/voronoi.py

Esta aplicación pitón por Carson granjero le da información topológica