Es imprescindible entender el código de forma correcta antes de adaptarlo a tu trabajo si ttienes algo que aportar puedes compartirlo con nosotros.
Solución:
Actualización en julio de 2016:
Gracias a varios voluntarios (especialmente Nikolai Nowaczyk y yo), ahora hay un código mucho más robusto/correcto para manejar diagramas de Voronoi en la superficie de una esfera en Python. Esto está 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 los documentos oficiales.
El algoritmo sigue la complejidad del tiempo cuadrático. Si bien loglineal es el óptimo teórico para los diagramas de Voronoi en las superficies de las esferas, actualmente es lo mejor que hemos podido implementar. Si desea obtener más información y ayudar con el esfuerzo de desarrollo, hay algunos problemas abiertos relacionados con la mejora de la forma en que Python maneja los diagramas esféricos de Voronoi y las estructuras de datos relacionadas:
- Esfuerzo para mejorar el trazado de polígonos esféricos en matplotlib
- Esfuerzo para mejorar el manejo de los cálculos de área de superficie de polígonos esféricos en scipy
Para obtener más información sobre la teoría, el desarrollo y los desafíos relacionados con este código de Python y los esfuerzos relacionados con la geometría computacional, también puede consultar algunas charlas de Nikolai y yo:
- Charla de Nikolai PyData Londres 2016
- Charla Tyler PyData Londres 2015
- Tyler PyCon 2016 Tutorial de geometría computacional
Respuesta original:
De hecho, recientemente escribí 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
El uso, el algoritmo y las limitaciones están documentados en readthedocs (http://py-sphere-voronoi.readthedocs.org/en/latest/voronoi_utility.html). Hay algunos ejemplos detallados allí, pero también colocaré uno o dos a continuación. El módulo también maneja el cálculo de las áreas superficiales de la región de Voronoi, aunque con algunas debilidades numéricas en la versión de desarrollo actual.
No he visto muchas implementaciones de código abierto bien documentadas para diagramas esféricos de Voronoi, pero ha habido un poco de revuelo sobre la implementación de JavaScript en el sitio web de Jason Davies (http://www.jasondavies.com/maps/voronoi/) . Sin embargo, no creo que su código esté abierto. También vi una publicación de blog sobre el uso de Python para solucionar parte del problema (http://jellymatter.com/2014/01/29/voronoi-tessellation-on-the-surface-of-a-sphere-python-code /). Muchas de las principales fuentes de literatura citadas en las publicaciones anteriores parecían muy difíciles de implementar (probé algunas de ellas), pero tal vez algunas personas encuentren útil mi implementación o incluso sugieran formas de mejorarla.
Ejemplos:
1) Produzca un diagrama de Voronoi para un conjunto pseudoaleatorio de puntos en la esfera unitaria:
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)
2) Calcule las áreas de superficie de los polígonos de la región de Voronoi y verifique que el área de superficie reconstituida sea razonable:
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
Aquí hay un artículo sobre diagramas esféricos de Voronoi.
O si asimilas a Fortran (¡bleah!), ahí está este sitio.
Enlace original (muerto): https://people.sc.fsu.edu/~jburkardt/f_src/sxyz_voronoi/sxyz_voronoi.html
Observe que la triangulación de Delaunay en una esfera es solo el casco convexo. Por lo tanto, puede calcular el casco convexo 3D (por ejemplo, usando CGAL) y tomar el dual.