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

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

Ответы на вопрос(11)

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

как на вопрос был дан ответ, но я нашел две статьи, в которыхАлгоритм фортуны (эффективность 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

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

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

Вот (включая исходный код для Delphi 5/6).

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

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

 Alexandre C.15 апр. 2011 г., 21:00
@stevenvh: Триангуляция Делоне, кажется, работает как есть после отображения сферы на плоскость (например, с помощью полярной проекции: большие круги переходят в круги, а нахождение внутри описанного круга будет одинаково работать для сферических и плоских треугольников). Затем вы возвращаетесь к сфере и дуализируете график. Это, вероятно, сработает.
 wnoise04 авг. 2011 г., 23:00
@stevenh: Технически вам не нужно сохранять расстояния, вы просто должны сохранять порядок всех расстояний. Конечно, я не думаю, что даже это возможно.
 stevenvh13 февр. 2009 г., 15:06
Я думал о переназначении в 2D-плоскость, но это не работает; AFAIK нет отображения сферы на плоскость, которая сохраняет расстояние. Простой пример: расстояния между любой парой вершин правильного тетраэдра одинаковы, но вы не можете нарисовать это в 2D-плоскости. Спасибо за ваш ответ в любом случае.

лежащих на сфере:КАРОЛИ, Мануэль и др. Надежные и эффективные триангуляции Делоне для точек на сфере или рядом с ней. 2009. где они говорят о реализации вCGAL.

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

Цитата из статьи:

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

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

Халл, программа для выпуклых оболочек.Qhull.Трехмерные выпуклые корпуса. в Фортране. Трехмерные выпуклые корпуса.STRIPACK в Фортране.

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

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

Решение Вопроса

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

Или, если вы грок Фортран (блин!) Естьэтот сайт.

 Thomas Hodges27 авг. 2018 г., 19:29
Страница на Фортране не загружается и не загружается на WayBack Machine. Кто-нибудь знает, где я могу найти этот контент?
 schnaader13 февр. 2009 г., 15:10
Для меня есть ссылка для скачивания статьи здесь:citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.19.6737 - это не так полезно, хотя ...
 math15 июл. 2013 г., 15:09
В 2011 году вышла отличная статья, в которой описан алгоритм развертки плоскости (на основе алгоритма Fortune для плоскости):e-lc.org/tmp/Xiaoyu__Zheng_2011_12_05_14_35_11.pdf

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

Это не полный ответ, но это то, где я бы начал ..

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

 math15 июл. 2013 г., 15:04
Это уже достигнуто?

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

 olivier20 дек. 2012 г., 11:34
Что касается специальной сферы упаковки, то она еще не готова. Надеюсь, в CGAL 4.3
Обновление в июле 2016 года:

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

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

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

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

Николай PyData London 2016 talkТайлер 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
 treddy29 июн. 2018 г., 00:17
@RutgerHofste Верно, и даже если мы примем идеальную сферу, это сложная проблема; Я знаю, что в мире ГИС предпринимаются некоторые усилия для обработки эллипсоида различными способами, но моя задача была просто посмотреть, сможем ли мы на начальном этапе хорошо поработать над сферой.
 Alessandro Jacopson08 апр. 2015 г., 20:04
Мне кажется, что вашVoronoi_Sphere_Surface принимает точки, выраженные в трехмерной декартовой системе координат, я прав? Возможно, принятие точек, выраженных в сферических координатах (только долгота и широта), может упростить использование вашего кода в случае точек, которые являются географическими точками.
 treddy09 апр. 2015 г., 21:13
Я полагаю, я мог бы добавить флаг, чтобы разрешить сферические координаты. Справедливости ради, мой модуль voronoi_utility уже предоставляет функцию convert_spherical_array_to_cartesian_array (), которую можно было бы достаточно легко использовать до запуска кода Вороного.
 Rutger Hofste28 июн. 2018 г., 11:04
В большинстве проекций земля - ​​это не сфера, а эллипсоид. Есть мысли по этому поводу?

http://www.qhull.org/html/qdelaun.htm

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

 math15 июл. 2013 г., 15:07
В общем,выпуклый корпус отличается проблема, чем триангуляция Делоне. Но алгоритм QHull для выпуклой оболочки дает также триангуляцию Делоне, двойственную к диаграмме Вороного.

Ваш ответ на вопрос