Дуглас-Пейкер - кратчайшая дуга от точки до круга на поверхности сферы

Question

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

Теперь все примеры, которые я видел до сих пор, применяют алгоритм очень наивно, просто заменяя x и y на широту и долготу. Это может привести к приемлемым результатам, если полилиния очень локализована, не слишком близко к полюсу и не пересекает 180-градусный меридиан, но я хотел бы реализовать более общую версию алгоритма.

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

Кто-нибудь знает формулу, которая вычисляет эту длину?

заранее спасибо

Answer 1

Я постараюсь выразить все через единичные векторы p, q и r, которые можно рассматривать как точки на единичной сфере Σ с центром в начале координат 0. Вы можете преобразовать это в земные величины, увеличив масштаб на радиус Земли. Здесь есть некоторые справочные материалы.

Мы хотим найти расстояние большого круга d от p до большого круга C, проходящего через q и r. C - пересечение плоскости P и сферы Σ, где P - плоскость, проходящая через q, r и начало координат 0. d - это просто угол θ (выраженный в радианах) между p и P. Вектор нормали для P является нормализованным перекрестным произведением q×r/ sinφ, где φ - угол между q и r.

Мы заканчиваем с

θ = арксин (p⋅ (q×r) / sinφ)

Как я уже сказал, все здесь масштабируется радиусом R земли. Таким образом, три точки: *R***p**, *R***q**, *R***r**, а расстояние - Rθ.

Однако, если все, что вам нужно, это найти комбинацию точек / линий с кратчайшим расстоянием, вы можете опустить умножение на R. На самом деле вы можете опустить arcsin() и просто посмотреть на относительные размеры p⋅ (q×r) / sinφ.