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

Question

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

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

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

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

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

Answer 1

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

Мы хотим найти расстояние до большого круга d от p до большого круга C , проходящего через q и г . C - пересечение плоскости P и сферы & Sigma; , где P - плоскость, проходящая через q , r и источник 0 . d - это просто угол & theta; (выражено в радианах) между p и P . Нормальный вектор для P является нормализованным перекрестным произведением q & times; r / sin & phi ;, где & phi; это угол между q и r .

Мы получаем

* +1058 * & тэта; = arcsin ( p & sdot; ( q & times; r ) / sin & phi;)

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

Однако, если все, что вам нужно, это найти комбинацию точек / линий с кратчайшим расстоянием, вы можете пропустить умножение на R . Фактически вы можете опустить arcsin () и просто посмотреть на относительные размеры p & sdot; ( q & times; r ) / sin & phi;.