Сферическая пространственно-ограниченная триангуляция Делоне
В целях реализации высокопроизводительного алгоритма динамического нахождения пути на сфере (в C ++) меня интересует инкрементная ограниченная триангуляция Делоне на поверхности сферы. Существующие библиотеки не кажутся достаточными — ближе всего я смог найти CGAL, у которого правильное топологическое пространство, но неправильное метрическое пространство.
Библиотека должна иметь:
- Разумная производительность (у меня есть около 100k очков, чтобы положить в него)
- Сферическое топологическое и метрическое пространство (честно говоря, это отменяет № 1 с большим отрывом)
- Инкрементная вставка и удаление точек (для последующего алгоритмического использования)
На данный момент мои единственные реальные варианты кажутся приблизительными (с помощью проекции на евклидово метрическое пространство 2D и с учетом компромисса в гарантии Делоне, которая предоставляет) или написать мои собственные, со всеми вытекающими отсюда трудностями. Существует ли библиотека для ограниченной триангуляции Делоне в сферическом метрическом пространстве?
Решение
Поскольку это теперь помечено как не по теме (из-за спама?), Я мог бы также дать хотя бы исчерпывающий ответ.
Насколько я знаю, по состоянию на июль 2017 года существует два варианта вычисления ограниченной триангуляции Делоне для точек на сфере.
Первый — это libdts2 (1). Он основан на алгоритмах CGAL 2D триангуляции Делоне и использует рациональные точки, которые находятся точно на сфере. Точки, которые не находятся на сфере, привязываются к близкой рациональной точке, которая находится точно на сфере (2).
Его недостатком является использование 4 вспомогательных точек, которые всегда являются частью триангуляции. Также невозможно вставить какие-либо точки очень близко к северному полюсу. Вычисление пересекающихся ограничений является либо чрезвычайно медленным, либо только приблизительным.
Другой вариант заключается в реализации предложенного алгоритма в (3). При таком подходе точки не обязательно должны быть точно на сфере. К сожалению, пока нет кода, хотя есть планы по его интеграции в CGAL (4).
Поэтому лучше всего использовать libdts2, пока GeometryFactory / INRIA не выпустят свой код. Это не должно представлять большой проблемы, так как интерфейс libdts2 в большинстве аспектов напоминает интерфейс алгоритмов триангуляции CGAL.
В случае, если libdts2 представляет интерес, вы можете ожидать следующее:
- Вычисление CDT всех улиц в наборе данных OpenStreetMap Saarland (309 тыс. Узлов, 324 тыс. Сегментов) занимает около 16 секунд, используя около 170 МБ ОЗУ (однопоточное, Core i7-4700MQ).
- Предикаты оцениваются по сфере
- Он имеет сферическую топологию, если считать лицо бесконечной гранью триангуляции
- Вставка / удаление возможно, так как оно основано на алгоритмах 2D триангуляции CGAL
Рекомендации:
Другие решения