Обновление в июле 2016 года:
Благодаря ряду добровольцев (особенно Николая Новачика и меня), теперь есть гораздо более надежный / правильный код для обработки диаграмм Вороного на поверхности сферы в Python. Это официально доступно как scipy.spatial.SphericalVoronoi от версии 0.18 scipy и далее. В официальных документах .
есть рабочий пример использования и печати.
Алгоритм следует квадратичной сложности времени. Хотя логлинейный является теоретическим оптимумом для диаграмм Вороного на поверхностях сфер, в настоящее время это лучшее, что мы смогли реализовать. Если вы хотите узнать больше и помочь в разработке, есть некоторые открытые проблемы, связанные с улучшением способа обработки Python сферических диаграмм Вороного и соответствующих структур данных:
Для получения дополнительной информации о теории / разработке / проблемах, связанных с этим кодом Python и связанных с этим работах по вычислительной геометрии, вы также можете ознакомиться с некоторыми докладами Николая и I:
Оригинальный ответ:
На самом деле я недавно написал некоторый открытый код Python для диаграмм Вороного на поверхности сферы: https://github.com/tylerjereddy/py_sphere_Voronoi
Использование, алгоритм и ограничения задокументированы на readthedocs (http://py -sphere-voronoi.readthedocs.org / en / latest / voronoi_utility.html ). Там есть несколько подробных примеров, но я приведу один или два ниже. Модуль также обрабатывает расчет площади поверхности области Вороного, хотя и с некоторыми численными недостатками в текущей версии разработки.
Я не видел много хорошо документированных реализаций с открытым исходным кодом для сферических диаграмм Вороного, но было немного шума по поводу реализации JavaScript на сайте Джейсона Дэвиса (http://www.jasondavies.com/maps/voronoi/). Я не думаю, что его хотя код открыт. Я также видел сообщение в блоге об использовании Python для решения части проблемы (http://jellymatter.com/2014/01/29/voronoi-tessellation-on-the-surface-of-a-sphere-python-code/). Многие первичные литературные источники, процитированные в приведенных выше публикациях, казались очень сложными для реализации (некоторые из них я пробовал) ) но, возможно, некоторые люди сочтут мою реализацию полезной или даже предложат способы ее улучшения.
Примеры:
1) Создание диаграммы Вороного для псевдослучайного набора точек на единичной сфере:
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) Рассчитать площади поверхности полигонов области Вороного и убедиться, что восстановленная площадь поверхности является разумной:
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