Сферическое пространственное ограничение триангуляции delaunay

Question

В целях реализации высокопроизводительного динамического алгоритма поиска траектории на сфере (на C++), я заинтересован в выполнении инкрементной ограниченной триангуляции delaunay на поверхности сферы. Существующих библиотек, по-видимому, недостаточно, тем ближе, чем я смог найти до сих пор, является CGAL, который имеет топологическое пространство справа, но метрическое пространство ошибочно.

Библиотека должна иметь:

• Разумные производительность (у меня есть около 100k точек, чтобы положить в него)
• Сферическая топологический и метрическое пространство (если честно, это отменяет # 1 с большим отрывом)
• вставки Инкрементальной точки и удаление (для последующего использования алгоритмического)

на данный момент мои только реальные варианты кажутся приближенным (с помощью проекции на 2D евклидовой мне tric space и взяв компромисс в гарантии Delaunay, который обеспечивает) или написать мою собственную, со всей вероятностью, которая влечет за собой. Существует ли библиотека для ограниченной триангуляции delaunay в сферическом метрическом пространстве?

Answer 1

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

Насколько я знаю, есть - по состоянию на июль 2017 года - два варианта расчета ограниченной триангуляции треугольника точек на сфере.

Первый из них - libdts2 (1). Он основан на алгоритмах триангуляции 2D треугольника CGAL 2D и использует рациональные точки, которые находятся именно на сфере. Точки, которые не находятся на сфере, привязаны к близкой рациональной точке, которая находится именно на сфере (2). Его недостатком является использование 4 вспомогательных точек, которые всегда являются частью триангуляции. Также невозможно вставить точки, очень близкие к северному полюсу. Вычисление пересекающихся ограничений либо чрезвычайно медленное, либо только приблизительное.

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

Таким образом, лучше всего использовать libdts2 до тех пор, пока GeometryFactory/INRIA не выпустит свой код. Это не должно представлять большую проблему, так как интерфейс libdts2 в большинстве аспектов напоминает интерфейс алгоритмов триангуляции CGAL.

В случае libdts2 представляет интерес, вы можете ожидать следующее:

• Вычисление CDT всех улиц в данных OpenStreetMap набор Саар (309K узлов, 324K сегментов) занимает около 16 секунд, используя около 170 MiB Ram (один поток, Core i7-4700MQ)
• предикаты оцениваются в сфере
• он имеет сферическую топологию, если один подсчитывает бесконечное лицо как лицо триангуляции
• Вставка/удаление возможно, так как это на основе CGAL 2D tri Алгоритмы Ангуляция

Ссылки:

1. libdts2 доступны на GitHub
2. "Rational Points on the Unit Sphere: Approximation Complexity and Practical Constructions"
3. "Robust and Efficient Delaunay triangulations of points on or close to a sphere"
4. CGAL Google Summer of Code Project Ideas