Расположение проекта на пути (большой круг)

9

Я искал этот сайт SE довольно много часов, и я все еще изо всех сил пытаюсь найти решение моего вопроса. Моя цель заключается в том, чтобы, учитывая путь в OSM и мое местоположение (координаты широты / долготы), я хочу найти ближайшее местоположение (координаты широты / долготы) на этом пути. Точка может находиться в любом месте пути, не ограничиваясь точками, используемыми для определения пути.

Итак, я думаю о следующем алгоритме:

  1. Разделите путь на отдельные ребра, каждое ребро соединяет только две точки.
  2. Выберите ближайший край.
  3. Спроецируйте мое местоположение на этот край.

Теперь есть много вопросов о расчете расстояния между местоположением и путем:

Также очень похожий вопрос, из которого я не могу получить правильные или проверенные вычисления:

Есть также некоторая информация от доктора Мат по этому вопросу. Однако я не могу найти алгоритм для вычисления местоположения в шаге 3. Поскольку я не касался (векторной) алгебры в течение долгого времени, я не совсем понимаю логику в этих ответах.

Может кто-нибудь показать алгоритм для этого? Решение на любом приемлемом языке программирования мне подходит.

Bouke
источник
1
Поскольку это кажется критически важным для вашего "отказа" от других вопросов, пожалуйста, уточните "проецировать мое местоположение на этот край". Проекция может быть не на краю. Я считаю , что этот вопрос будет рассмотрен в других вопросах. (Отлично, для исследования, кстати.)
Мартин Ф
@MartinF этот вопрос вычисляет расстояние от точки до линии, но не самую близкую точку на самой линии.
бук
Там это решение в gis.stackexchange.com/a/23500/3195 , хотя это может быть трудно понять.
Мартин Ф
Ах да, спасибо, я обновил ссылку нет. 3. «Решение» в данном конкретном вопросе связано с общим объяснением поля проблемы. Хотя этого может быть достаточно для хорошо обоснованных математиков, я не совсем понимаю математику в этой статье.
бук

Ответы:

7

Использование сферической модели Земли может дать адекватную точность и привести к простым быстрым вычислениям.

Преобразуйте все координаты в декартовые координаты, ориентированные на землю. Например, формула

(cos(lon)*cos(lat), sin(lon)*cos(lat), sin(lat))

Сделаю. (Используется мера расстояния, в которой радиус Земли равен одной единице, что удобно.)

Запись X0 = (x0, y0, z0) для начальной точки и X1 = (x1, y1, z1) для точки назначения, которые определяют большой круг (при условии, что X0 отличается от X1, и эти два не диаметрально противоположны), пусть U - нормализованное перекрестное произведение X0 и X1. Это вычисляется в два этапа:

V = (xv, yv, zv) = (y0*z1 - z0*y1, z0*x1 - x0*z1, x0*y1 - y0*x1)

Длина V

|V| = sqrt(xv^2 + yv^2 + zv^2)

Нормализация растягивает V до длины единицы:

U = (xu, yu, zu) = V / |V| = (xv/|V|, yv/|V|, zv/|V|).

Ориентированное трехмерное расстояние между любой точкой X = (x, y, z) и плоскостью этого большого круга является просто точечным произведением X с Z, определяемым как

d = X * U = x*xu + y*yu + z*zu

Самая близкая точка с точки зрения расстояния на поверхности земли - та, которая ближе всего к плоскости: таким образом, она имеет наименьшее абсолютное значение d .

фигура

На этом рисунке показан большой круг (черного цвета), определенный двумя белыми точками и 2000 случайными точками на сфере, окрашенными и заштрихованными в соответствии с их абсолютным трехмерным расстоянием до плоскости этого большого круга; то есть | d |.

Найдя ближайшую точку, спроецируйте ее на большой круг, сначала спроецировав ее на плоскость большого круга (в 3D), а затем вытянув ее в радиальном направлении к поверхности Земли. Проекция просто вычитает d * U:

X' = (x', y', z') = X - d*U = (x - d*xu, y - d*yu, z - d*zu).

Радиальная проекция просто перенормирует X 'так же, как V перенормировался в U:

X'' = X' / |X'|.

(Это будет проблематично, если | X '| = 0, что происходит, когда ближайшая точка является одним из полюсов большого круга. Включите тест в код для этого условия, если это может произойти, и разберитесь с ним отдельно, используя знак d, чтобы определить, какой полюс.)

При желании, преобразовать координаты X '' обратно в (широта, долгота), используя обычные формулы .

Whuber
источник
Один вопрос. Рассмотрим не слишком необычный случай, когда мы можем выбрать любые X1 и X0 (на большом круге), с точки зрения точности, лучше ли выбирать X1 и X0 близко или далеко друг от друга (опять же, при условии, что X0 отличается от X1 и два не диаметрально противоположны)?
user189035
1
@ user189035 Выберите их на 90 градусов друг от друга. Когда они очень близки, их перекрестное произведение численно неопределенно: в вычитаниях много отмен, что приводит к потере значимых цифр.
whuber