Найти треугольник, содержащий точку в сферической треугольной сетке (Python, сферические координаты)

Question

Основная проблема

В Python я триангулировал поверхность (единичного) шара с помощью икосаэдрической сетки. У меня есть список simplices кортежей, содержащих индексы трех вершин каждого треугольника, и у меня есть два списка, описывающих координаты (в радианах) каждой вершины: ее широту и долготу.

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

Я готов пожертвовать памятью ради эффективности, поэтому я в порядке с построением дерева или использованием какого-либо метода поиска.

Предостережения

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

Дополнительная информация

Икосаэдрическая сетка была получена с использованием пакета stripy. Он проецирует вершины икосаэдра на единичную сферу и затем делит пополам треугольники, так что каждое ребро делится пополам, или наоборот, каждый треугольник делится на четыре. stripy имеет встроенный метод для вычисления треугольника, в котором содержится точка, но для уточнения сетки 6 (то есть 6 делений пополам) и около миллиона точек это занимает часы. Я подозреваю, что этот метод не использует метод дерева / поиска, и я надеюсь, что есть метод, который значительно улучшит это.

Answer 1

1. Вычисляет ограничивающую рамку широты / долготы для каждого треугольника. Помните, что широты наибольшей величины могут быть на краю (легко найти, рассматривая нормаль к большому кругу, включая каждый край) или (если полюс заключен) во внутренней части.
2. Разделить все треугольники, которые пересекаютпериодическая граница долготы в два или, чтобы быть дешевым, только их ограничивающие рамки.
3. Построить расширенный объект k - d дерево по треугольникам (и треугольникам сверху). При этом по-прежнему используются только значения широты / долготы.
4. Запустите очевидный рекурсивный, консервативный поиск локализации, чтобы найти подходящие треугольники. (Неважно, какую часть разделенных треугольников вы найдете.)
5. Тщательно проверьте наличие треугольника: для каждой стороны треугольника определите, какое полушарие (определяемое большим кругом, содержащим сегмент) содержит точку запросав моде (возможно, просто перекрестном произведении на трехмерных векторах), который не зависит от порядка, в котором представлены вершины, и никогда не производит «на разделительной линии». Тогда каждая точка гарантированно будет находиться в одном треугольнике.