Я ищу простой алгоритм (если существует), чтобы найти диаграмму Вороного для множества точек на поверхности сферы. Исходный код будет отличным. Я человек Дельфы (да, я знаю...), но я тоже ем С-код.
Алгоритм вычисления диаграммы Вороного на сфере?
Ответ 1
Здесь статья о сферических диаграммах Вороного.
Или, если вы грок Фортран (бле!) Там этот сайт.
Исходная ссылка (мертвая): https://people.sc.fsu.edu/~jburkardt/f_src/sxyz_voronoi/sxyz_voronoi.html
Ответ 2
Обновление в июле 2016 года:
Благодаря ряду добровольцев (особенно Николая Новаджика и я), в настоящее время существует гораздо более надежный/правильный код для обработки диаграмм Вороного на поверхности сферы в Python. Это официально доступно как scipy.spatial.SphericalVoronoi из версии 0.18 scipy и далее. Там есть рабочий пример использования и печати в официальном docs.
Алгоритм соответствует квадратичной временной сложности. Хотя логарифмический является теоретическим оптимальным для диаграмм Вороного на поверхностях сфер, в настоящее время это лучшее, что мы смогли реализовать. Если вы хотите узнать больше и помогать в процессе разработки, есть некоторые открытые проблемы, связанные с улучшением способа обработки Python сферических диаграмм Вороного и связанных структур данных:
- Усилия по улучшению построения сферических многоугольников в matplotlib
- Усилия по улучшению обработки расчетов площади поверхности сферического многоугольника в scipy
Для получения дополнительной информации о теории/развитии/проблемах, связанных с этим кодом Python и связанных с ними вычислительных геометриях, вы также можете ознакомиться с некоторыми беседами Николая и Я:
- Рассказ Николая Пидата в Лондоне 2016
- Обсуждение Tyler PyData London 2015
- Учебник по вычислительной геометрии Tyler PyCon 2016
Исходный ответ:
Недавно я написал код с открытым кодом 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
Ответ 3
Обратите внимание, что триангуляция Делоне на сфере - это просто выпуклая оболочка. Таким образом, вы можете вычислить трехмерную выпуклую оболочку (например, используя CGAL) и взять двойной.
Ответ 4
Короче говоря, попробуйте cssgrid из NCAR Graphics. Я написал более длинный ответ для аналогичного вопроса на codereview.stackexchange.com.
Ответ 5
Существует статья из INRIA о триангуляции Делоне (DT) точек, лежащих на сфере: CAROLI, Manuel, et al. Надежные и эффективные триангуляции Делоне точек на или вблизи сферы. 2009., где они говорят о реализации в CGAL.
В документе говорится о различных доступных реализациях алгоритмов DT.
Цитата из статьи:
Легкий и стандартный ответ заключается в вычислении трехмерной выпуклой оболочки точек, что, как известно, эквивалентно.
для вычисления выпуклой оболочки, предложенной в статье:
- Халл, программа для выпуклых оболочек.
- Qhull.
- Трехмерные выпуклые оболочки. в FORTRAN. Трехмерные выпуклые оболочки.
- STRIPACK в FORTRAN.
Класс DT С++ CGAL имеет метод dual, чтобы получить диаграмму Вороного.
В соответствии с этот пост Моник Тейод (один из авторов вышеупомянутой статьи) мне кажется, что в ноябре 2012 года реализация еще не был готов.
Ответ 6
Прошло некоторое время, так как на вопрос был дан ответ, но я нашел две статьи, которые реализуют алгоритм удачи (эффективность O (N lg N), память O (N)) по поверхности сферы. Возможно, будущий зритель найдет эту информацию полезной.
- "Подметание сферы" Диниса и Мамеда, опубликованной в Международном симпозиуме 2010 по Вороным в области науки и техники. Можно приобрести в http://dx.doi.org/10.1109/ISVD.2010.32
- "Алгоритм плановой развертки для тезисерации сферы Вороного" по Zheng et al. Я не уверен, что он был опубликован из-за первого, но он датирован 13 декабря 2011 года. Он доступен бесплатно на http://www.e-lc.org/tmp/Xiaoyu__Zheng_2011_12_05_14_35_11.pdf
Я работаю через них сам в данный момент, поэтому я не могу это объяснить. Основная идея заключается в том, что алгоритм Фортуны работает на поверхности сферы, пока вы правильно вычисляете ограничивающие параболы точек. Поскольку поверхность сферы обертывается, вы также можете использовать круговой список, чтобы содержать линию пляжа, и не беспокоиться о работе с ячейками на краю прямоугольного пространства. При этом вы можете сместиться с северного полюса сферы на юг и снова вернуться обратно, перейдя на сайты, которые вводят новые точки на линию пляжа (добавление параболы к пляжной линии) или введение вершин клеток (удаление парабола с береговой линии).
Обе статьи ожидают высокого уровня комфорта с линейной алгеброй, чтобы понять концепции, и они оба продолжают терять меня в тот момент, когда они начинают объяснять сам алгоритм. К сожалению, также предоставить исходный код.
Ответ 7
Я думаю, что плоскость Вороного для каждой точки может быть построена с использованием неевклидовой геометрии. То, что обычно было линией на 2-й плоскости, теперь является "большим кругом" на сфере (см. Википедию: эллиптическая геометрия). Легко найти, какие точки находятся на неправильной стороне любого большого круга между двумя точками, просто вращая сферу так, что разделяющий большой круг является экватором, а затем все это указывает на другое полушарие, чем точка, в которой вы находитесь построив плоскость Вороного для.
Это не весь ответ, но я начинаю...
Ответ 8
Здесь есть хорошая программа примера диаграммы Voronoi здесь (включая исходный код для Delphi 5/6).
Я думаю, что "точки на поверхности сферы" означают, что вам сначала нужно переназначить их в 2D-координаты, создать диаграмму Вороного и затем переназначить их в координаты поверхности сферы. Являются ли две формулы из статьи, посвященной UV-картографии Википедии, работающей здесь?
Также обратите внимание, что диаграмма Voronoi будет иметь неправильную топологию (она находится внутри прямоугольника и не "обтекает" ), здесь она может помочь скопировать все точки из (0,0) - (x, y) к соседним областям выше (0, -y * 2) - (x, 0), ниже (0, y) - (x, y * 2), left (-x, 0) - (0, y) и right (x, 0) - (x * 2, y). Надеюсь, вы знаете, что я имею в виду, не стесняйтесь спрашивать:)
Ответ 9
CGAL работает над пакетом "сферическое ядро ", который позволит вычислить именно такие вещи. К сожалению, еще не выпущен, но, возможно, это будет в следующей версии, так как они уже упомянули об этом в разговоре по Google Talk в марте
Ответ 10
Цитата из этой справки: http://www.qhull.org/html/qdelaun.htm
Чтобы вычислить триангуляцию Делоне точек на сфере, вычислите их выпуклую оболочку. Если сфера является единичной сферой в начале координат, нормали фасетов являются вершинами Вороного входа.
Ответ 11
Если ваши точки находятся в одном полушарии, вы можете сделать гнономическую проекцию от сферического до планарного координат, а затем триангуляцию, так как большие круги становятся прямыми линиями кратчайшего расстояния.