Я искал этот сайт SE довольно много часов, и я все еще изо всех сил пытаюсь найти решение моего вопроса. Моя цель заключается в том, чтобы, учитывая путь в OSM и мое местоположение (координаты широты / долготы), я хочу найти ближайшее местоположение (координаты широты / долготы) на этом пути. Точка может находиться в любом месте пути, не ограничиваясь точками, используемыми для определения пути.
Итак, я думаю о следующем алгоритме:
- Разделите путь на отдельные ребра, каждое ребро соединяет только две точки.
- Выберите ближайший край.
- Спроецируйте мое местоположение на этот край.
Теперь есть много вопросов о расчете расстояния между местоположением и путем:
- WGS указывает на отрезок линии WGS (большой круг)
- Вычисление расстояния между точкой и виртуальной линией двух широт
- Как приблизить расстояние от точки до отрезка на сфере?
Также очень похожий вопрос, из которого я не могу получить правильные или проверенные вычисления:
Есть также некоторая информация от доктора Мат по этому вопросу. Однако я не могу найти алгоритм для вычисления местоположения в шаге 3. Поскольку я не касался (векторной) алгебры в течение долгого времени, я не совсем понимаю логику в этих ответах.
Может кто-нибудь показать алгоритм для этого? Решение на любом приемлемом языке программирования мне подходит.
Ответы:
Использование сферической модели Земли может дать адекватную точность и привести к простым быстрым вычислениям.
Преобразуйте все координаты в декартовые координаты, ориентированные на землю. Например, формула
Сделаю. (Используется мера расстояния, в которой радиус Земли равен одной единице, что удобно.)
Запись X0 = (x0, y0, z0) для начальной точки и X1 = (x1, y1, z1) для точки назначения, которые определяют большой круг (при условии, что X0 отличается от X1, и эти два не диаметрально противоположны), пусть U - нормализованное перекрестное произведение X0 и X1. Это вычисляется в два этапа:
Длина V
Нормализация растягивает V до длины единицы:
Ориентированное трехмерное расстояние между любой точкой X = (x, y, z) и плоскостью этого большого круга является просто точечным произведением X с Z, определяемым как
Самая близкая точка с точки зрения расстояния на поверхности земли - та, которая ближе всего к плоскости: таким образом, она имеет наименьшее абсолютное значение d .
На этом рисунке показан большой круг (черного цвета), определенный двумя белыми точками и 2000 случайными точками на сфере, окрашенными и заштрихованными в соответствии с их абсолютным трехмерным расстоянием до плоскости этого большого круга; то есть | d |.
Найдя ближайшую точку, спроецируйте ее на большой круг, сначала спроецировав ее на плоскость большого круга (в 3D), а затем вытянув ее в радиальном направлении к поверхности Земли. Проекция просто вычитает d * U:
Радиальная проекция просто перенормирует X 'так же, как V перенормировался в U:
(Это будет проблематично, если | X '| = 0, что происходит, когда ближайшая точка является одним из полюсов большого круга. Включите тест в код для этого условия, если это может произойти, и разберитесь с ним отдельно, используя знак d, чтобы определить, какой полюс.)
При желании, преобразовать координаты X '' обратно в (широта, долгота), используя обычные формулы .
источник