Алгоритм вычисления диаграммы Вороного на сфере?

Question

Я ищу простой (если существует) алгоритм поиска диаграммы Вороного для набора точек на поверхности сферы.Исходный код был бы отличным.Я использую Delphi (да, я знаю...), но я тоже использую C-код.

Answer 1

Вот статья о сферические диаграммы Вороного.

Или, если ты владеешь Фортраном (бля!), то есть этот сайт.

Answer 2

Обновление в июле 2016 г.:

Благодаря ряду добровольцев (особенно Николаю Новачику и мне) теперь существует гораздо более надежный/правильный код для обработки диаграмм Вороного на поверхности сферы в Python.Это официально доступно как scipy.spatial.SphericalVoronoi из версии 0.18 Сципи и далее.В официальном документе есть рабочий пример использования и построения графиков. документы.

Алгоритм соответствует квадратичной временной сложности.Хотя логлинейность является теоретическим оптимумом для диаграмм Вороного на поверхностях сфер, на данный момент это лучшее, что нам удалось реализовать.Если вы хотите узнать больше и помочь в разработке, есть несколько открытых вопросов, связанных с улучшением способа обработки Python сферических диаграмм Вороного и связанных с ними структур данных:

• Усилия по улучшению построения сферических многоугольников в matplotlib.
• Попытка улучшить обработку вычислений площади поверхности сферического многоугольника в scipy.

Для получения дополнительной информации о теории/разработке/проблемах, связанных с этим кодом Python и связанными с ним усилиями по вычислительной геометрии, вы также можете ознакомиться с некоторыми беседами с Николаем и мной:

• Выступление Николая PyData в Лондоне 2016
• Выступление Тайлера PyData в Лондоне, 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

Answer 3

Обратите внимание, что триангуляция Делоне на сфере — это всего лишь выпуклая оболочка.Таким образом, вы можете вычислить выпуклую трехмерную оболочку (например.используя CGAL) и возьмите двойную.

Answer 4

Короче, попробуй cssgrid от НКАР Графика.Я написал более подробный ответ на аналогичный вопрос на codereview.stackexchange.com.

Answer 5

Существует статья INRIA о триангуляции Делоне (DT) точек, лежащих на сфере: КАРОЛИ, Мануэль и др.Надежные и эффективные триангуляции Делоне точек на сфере или вблизи нее.2009. где они говорят о реализации в КГАЛ.

В статье говорится о различных доступных реализациях алгоритмов DT.

Цитата из газеты:

Простой и стандартный ответ заключается в вычислении 3D выпуклой оболочки точек, что, как известно, эквивалентно.

для расчета выпуклой оболочки в статье предлагается:

1. Hull, программа для выпуклых оболочек.
2. Кхалл.
3. Трехмерные выпуклые оболочки. на ФОРТРАНЕ.Трехмерные выпуклые оболочки.
4. СТРИПАК на ФОРТРАНЕ.

Класс DT C++ CGAL имеет метод dual чтобы получить диаграмму Вороного.

В соответствии с эта почта Моника Тейо (одна из авторов вышеупомянутой статьи), мне кажется, что в ноябре 2012 года реализация еще не была готова.

Answer 6

Прошло много времени с тех пор, как на вопрос был дан ответ, но я нашел две статьи, которые реализуют Алгоритм Фортуны (эффективность O(N lg N), память O(N)) по поверхности сферы.Возможно, будущему зрителю эта информация будет полезна.

• «Охват сферы» Диниса и Мамеде, опубликованная на Международном симпозиуме 2010 года по диаграммам Вороного в науке и технике.Можно приобрести на http://dx.doi.org/10.1109/ISVD.2010.32
• «Алгоритм плоской развертки для мозаики сферы Вороного» Чжэн и др.Я не уверен, что оно было опубликовано из-за первого, но оно датировано 13 декабря 2011 года.Он доступен бесплатно на http://www.e-lc.org/tmp/Xiaoyu__Zheng_2011_12_05_14_35_11.pdf

В данный момент я сам над ними работаю, поэтому не могу хорошо это объяснить.Основная идея заключается в том, что алгоритм Фортуны работает на поверхности сферы, если вы правильно рассчитываете ограничивающие точки параболы.Поскольку поверхность сферы переносится, вы также можете использовать круговой список, чтобы содержать линию пляжа и не беспокоиться об обработке ячеек на краю прямоугольного пространства.При этом вы можете перемещаться от северного полюса сферы к югу и снова назад, переходя к местам, которые вводят новые точки на пляжную линию (добавление параболы к пляжной линии) или введение вершин ячеек (удаление парабола от линии пляжа).

Обе статьи ожидают высокого уровня владения линейной алгеброй для понимания концепций, и обе продолжают терять меня в тот момент, когда начинают объяснять сам алгоритм.К сожалению, ни один из них не предоставил исходный код.

Answer 7

Я думаю, что плоскость Вороного для каждой точки можно построить, используя неевклидову геометрию.То, что обычно было линией на 2D-плоскости, теперь представляет собой «большой круг» на сфере (см. Википедию:эллиптическая геометрия).Легко определить, какие точки находятся на неправильной стороне любого большого круга между двумя точками, просто повернув сферу так, чтобы разделяющий большой круг был экватором, а затем все точки оказались на другом полушарии, чем точка, в которой вы находитесь. постройка самолета Вороного.

Это не весь ответ, но я бы начал с этого..

Answer 8

Есть хороший пример программы с диаграммой Вороного. здесь (включая исходный код для Delphi 5/6).

Я думаю, что «точки на поверхности сферы» означают, что вам сначала нужно переназначить их в 2D-координаты, создать диаграмму Вороного, а затем переназначить их на координаты поверхности сферы.Являются ли две формулы из Статья в Википедии об УФ-картировании здесь работает?

Также обратите внимание, что диаграмма Вороного будет иметь неправильную топологию (она находится внутри прямоугольника и не «заворачивается»), здесь может помочь копирование всех точек из (0,0)-(x, y) к соседу. области выше (0,-y*2)-(x,0), ниже (0,y)-(x,y*2), слева (-x,0)-(0,y) и справа (x, 0)-(х*2, у).Надеюсь, вы понимаете, о чем я, не стесняйтесь спрашивать :)

Answer 9

КГАЛ работает над пакетом «сферическое ядро», который позволит вычислять именно такие вещи.К сожалению, еще не выпущен, но возможно это будет в следующем их выпуске, раз уж они уже упоминал об этом в Google Tech Talk в марте

Answer 10

Цитата из этой ссылки: http://www.qhull.org/html/qdelaun.htm

Чтобы вычислить триангуляцию Делоне точек на сфере, вычислите их выпуклую оболочку.Если сфера является единичной сферой в начале координат, нормали фасетов являются вершинами Вороного входных данных.

Answer 11

Если ваши точки находятся в пределах одного полушария, вы можете выполнить гномоническую проекцию сферических координат на плоские, а затем выполнить триангуляцию, поскольку большие круги становятся прямыми линиями кратчайшего расстояния.