Algoritmo para calcular un diagrama Voronoi en una esfera?

StackOverflow https://stackoverflow.com/questions/545870

Pregunta

Estoy buscando un simple algoritmo (si existe) para encontrar el diagrama de Voronoi de un conjunto de puntos en la superficie de una esfera. El código fuente sería grande. Soy un hombre de Delphi (sí, lo sé ...), pero yo como código C también.

¿Fue útil?

Solución

Aquí hay un documento sobre esférica Voronoi diagramas .

O si lo asimilo Fortran (bleah!) Hay este sitio .

Otros consejos

Actualización en julio de 2016:

Gracias a un número de voluntarios (especialmente Nikolai Nowaczyk y I), ahora hay mucho más robusto código / correcta para el manejo de los diagramas de Voronoi en la superficie de una esfera en Python. Esto es oficialmente disponible como scipy.spatial.SphericalVoronoi de la versión 0.18 de scipy en adelante. Hay un ejemplo práctico de uso y trazado en el docs .

El algoritmo sigue complejidad del tiempo cuadrática. Mientras loglineales es el óptimo teórico para los diagramas de Voronoi en las superficies de las esferas, esto es actualmente el mejor que hemos sido capaces de implementar. Si desea obtener más información y ayudar con el esfuerzo de desarrollo hay algunas cuestiones pendientes relacionadas con la mejora de la forma en Python maneja los diagramas de Voronoi esféricas y las estructuras de datos relacionados:

Para más antecedentes sobre la teoría / desarrollo / desafíos relacionados con el código de Python y los esfuerzos relacionados con la geometría computacional también se puede comprobar a cabo algunas conversaciones desde Nikolai y yo:

Respuesta Original:

De hecho, he escrito recientemente un código Python de código abierto para los diagramas de Voronoi en la superficie de una esfera: https: / /github.com/tylerjereddy/py_sphere_Voronoi

Los de uso, algoritmo, y limitaciones están documentados en readthedocs ( http: //py-sphere-voronoi.readthedocs.org/en/latest/voronoi_utility.html ). Hay algunos ejemplos detallados allí pero voy a colocar una o dos por debajo también. El módulo también se encarga del cálculo de las áreas de superficie de la región de Voronoi, aunque con algunas deficiencias numéricas en la versión de desarrollo actual.

No he visto muchas implementaciones de código abierto bien documentados para los diagramas de Voronoi esféricas, pero ha habido un poco de agitación acerca de la implementación de JavaScript en el sitio web de Jason Davies ( http://www.jasondavies.com/maps/voronoi/ ). No creo que su código es abierto sin embargo. También vi un post sobre el uso de Python para hacer frente a una parte del problema ( http://jellymatter.com/2014/01/29/voronoi-tessellation-on-the-surface-of-a-sphere-python-code/ ). Muchas de las fuentes bibliográficas primarias citadas en los puestos de arriba parecía muy difícil de poner en práctica (probé algunos de ellos), pero tal vez algunas personas van a encontrar mi aplicación útil o incluso sugerir formas de mejorarlo.

Ejemplos:

1) Producir un diagrama Voronoi de un conjunto pseudo-aleatoria de puntos sobre la esfera unidad: 

import matplotlib
import matplotlib.pyplot as plt
import matplotlib.colors as colors
from mpl_toolkits.mplot3d import Axes3D
from mpl_toolkits.mplot3d.art3d import Poly3DCollection
import numpy as np
import scipy as sp
import voronoi_utility
#pin down the pseudo random number generator (prng) object to avoid certain pathological generator sets
prng = np.random.RandomState(117) #otherwise, would need to filter the random data to ensure Voronoi diagram is possible
#produce 1000 random points on the unit sphere using the above seed
random_coordinate_array = voronoi_utility.generate_random_array_spherical_generators(1000,1.0,prng)
#produce the Voronoi diagram data
voronoi_instance = voronoi_utility.Voronoi_Sphere_Surface(random_coordinate_array,1.0)
dictionary_voronoi_polygon_vertices = voronoi_instance.voronoi_region_vertices_spherical_surface()
#plot the Voronoi diagram
fig = plt.figure()
fig.set_size_inches(2,2)
ax = fig.add_subplot(111, projection='3d')
for generator_index, voronoi_region in dictionary_voronoi_polygon_vertices.iteritems():
   random_color = colors.rgb2hex(sp.rand(3))
   #fill in the Voronoi region (polygon) that contains the generator:
   polygon = Poly3DCollection([voronoi_region],alpha=1.0)
   polygon.set_color(random_color)
   ax.add_collection3d(polygon)
ax.set_xlim(-1,1);ax.set_ylim(-1,1);ax.set_zlim(-1,1);
ax.set_xticks([-1,1]);ax.set_yticks([-1,1]);ax.set_zticks([-1,1]); 
plt.tick_params(axis='both', which='major', labelsize=6)

introducir descripción de la imagen aquí

2) Calcular las áreas de superficie de los polígonos región de Voronoi y verificar que el área de la superficie reconstituida es sensato: 

import math
dictionary_voronoi_polygon_surface_areas = voronoi_instance.voronoi_region_surface_areas_spherical_surface()
theoretical_surface_area_unit_sphere = 4 * math.pi
reconstituted_surface_area_Voronoi_regions = sum(dictionary_voronoi_polygon_surface_areas.itervalues())
percent_area_recovery = round((reconstituted_surface_area_Voronoi_regions / theoretical_surface_area_unit_sphere) * 100., 5)
print percent_area_recovery
97.87551 #that seems reasonable for now

Tenga en cuenta que la triangulación de Delaunay en una esfera es sólo el casco convexo. De este modo se puede calcular la envoltura convexa 3D (por ejemplo, utilizando CGAL) y tomar el doble.

Hay un papel de INRIA sobre la triangulación de Delaunay (DT) de puntos que se encuentran sobre una esfera: CAROLI , Manuel, et al. triangulaciones ciente Delaunay, robusto y e fi de puntos en o cerca de una esfera. 2009. donde hablan de una implementación en CGAL .

El documento se refiere a varios aplicación disponibles de los algoritmos de DT.

Citando del papel:

  

Una respuesta fácil y estándar consiste en el cálculo de la envolvente convexa 3D   de los puntos, que es notoriamente equivalente.

para el cálculo de la envolvente convexa El documento sugiere:

  1. Hull, un programa para los cascos convexas.
  2. Qhull .
  3. cascos convexas tridimensionales. en FORTRAN. tridimensionales cascos convexas.
  4. STRIPACK en FORTRAN.

La clase DT C ++ de CGAL tiene el método dual para obtener el diagrama de Voronoi.

Según este post por Monique Teillaud (uno de los autores del artículo mencionado anteriormente) me parece que en noviembre de 2012, la aplicación no estaba todavía listo.

Ha sido un tiempo desde que la pregunta ha sido contestada, pero he encontrado dos papeles que aplicar algoritmo de Fortune (eficiencia O (N lg N), la memoria O (N)) sobre la superficie de la esfera. Tal vez un visor futuro será útil esta información.

Estoy trabajando a través de ellos a mí mismo en este momento, así que no puedo explicarlo bien. La idea básica es que el algoritmo de la Fortuna trabaja en la superficie de la esfera, siempre y cuando se calcula parábolas que limita la puntos correctamente. Debido a que la superficie de la esfera envuelve, también se puede utilizar una lista circular para contener la línea de playa y no preocuparse por el manejo de las células en el borde del espacio rectangular. Con esto, se puede barrer desde el polo norte de la esfera hacia el sur y una copia de seguridad de nuevo, saltando a los sitios que introducen nuevos puntos a la línea de playa (la adición de una parábola a la línea de playa) o la introducción de vértices celulares (extracción de una parábola de la línea de playa).

Ambos trabajos esperan un alto nivel de confort con el álgebra lineal para entender los conceptos, y ambos me siguen perdiendo en el punto que empiezan a explicar el propio algoritmo. Ni proporcionar el código fuente, por desgracia.

Creo que el plano de Voronoi para cada punto se puede construir usando la geometría no euclidiana. Lo que normalmente era una línea en un plano 2D, es ahora un 'gran círculo' sobre la esfera (véase Wikipedia: elíptica geometría ). Es fácil encontrar los puntos que están en el lado equivocado de cualquier círculo máximo entre dos puntos, por una simple rotación de la esfera de tal manera que el gran círculo que divide es el ecuador, y entonces es todos los puntos en el otro hemisferio que el punto que está construir el plano de Voronoi para.

Esta no es la respuesta completa, pero aquí es donde me gustaría empezar ..

Hay un buen programa de diagrama de Voronoi ejemplo aquí (incluyendo el código fuente para Delphi 5/6).

Creo que "los puntos de la superficie de una esfera" significa que primero tiene que volver a asignar a 2D coordenadas, crear el diagrama de Voronoi y luego volver a asignar las coordenadas de la superficie a la esfera. Son las dos fórmulas de artículo de Wikipedia mapeo UV trabajar aquí?

También note que el diagrama de Voronoi tendrá la topología mal (que está dentro de un rectángulo y no "wrap around"), aquí podría ayudar a copiar todos los puntos a partir de (0,0) - (x, y) a las regiones vecinas anteriores (0, -Y * 2) - (x, 0), por debajo de (0, y) - (x, y * 2), izquierda (-x, 0) - (0, y) y derecha (x, 0) - (x * 2, y). Espero que sepas lo que quiero decir, no dude en preguntar:)

CGAL está trabajando en el paquete "kernel esférica", lo que permitiría calcular exactamente este tipo de cosas . Por desgracia, no se libera aún , pero tal vez va a estar en su próxima versión, puesto que ya mencionado en una charla técnica en google de marzo de

Citando de esta referencia: http://www.qhull.org/html/qdelaun.htm

  

Para calcular la triangulación de Delaunay de los puntos sobre una esfera, calcular su casco convexo. Si la esfera es la esfera unidad en el origen, las normales de faceta son los vértices de Voronoi de la entrada.

Si los puntos están dentro de un hemisferio, se puede hacer una proyección gnomónica desde esférica a coordenadas planas, y luego triangular, ya que grandes círculos se convierten en líneas rectas de distancia más corta.

Licenciado bajo: CC-BY-SA con atribución
No afiliado a StackOverflow
scroll top