Библиотека работы с географическими координатами

[A3om]

Здравствуйте.

Передо мной стоит одна очень интересная задача.
Возможно, она покажется вам очень простой, но для меня она такой пока не является

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

Дело в том, что я хочу и могу заняться изучением всей теории, и через месяца три я получу ответ на свой вопрос, но три месяца - это слишком долго, и к тому же, по своему опыту знаю, что ничто так хорошо и быстро не усваивается, как после практического подхода и с небольшим количеством теории. Кроме того, может быть существуют уже написанные библиотеки, которые позволяют всё это без труда расчитать?

Я работаю в сфере Web, и поэтому, может быть есть уже готовые библиотеки, написанные на языке PHP?
А если же таких нет, то подскажите, пожалуйста, в какую сторону мне двигаться, что необходимо прочитать и изучить?

Спасибо.

[Sergey Astakhov]

Мне необходимо как-то привязать эту точку, если это возможно, к отрезку на карте и знать её координаты.
Такое я уже наблюдал в автомобильных навигационных системах - "привязка к дороге".

Последнее называется умным термином "map matching". Но это намного более обширная задача чем ваш пример с одной линией и одной точкой. Если у вас одна линия и одна точка, то есть простое вычисление ближайшей точки - это и будет ответ на ваш вопрос. Основная сложность возникает когда линий и точек много (сеть дорог и треки движения по ним) - как выбрать какие точки каким линиям (и направлению движения по ним!) соответствуют с учётом возможной погрешности координат как у точек так и линий дорог. Под это дело разработано множество разных алгоритмов разного уровня сложности, этими разработками занималось много людей из универов на гранты. Вы определитесь сначала - вам нужна полноценная задача map matching-а или что-то можно упростить?

Дело в том, что я хочу и могу заняться изучением всей теории, и через месяца три я получу ответ на свой вопрос, но три месяца - это слишком долго, и к тому же, по своему опыту знаю, что ничто так хорошо и быстро не усваивается, как после практического подхода и с небольшим количеством теории. Кроме того, может быть существуют уже написанные библиотеки, которые позволяют всё это без труда расчитать?

Я работаю в сфере Web, и поэтому, может быть есть уже готовые библиотеки, написанные на языке PHP?
А если же таких нет, то подскажите, пожалуйста, в какую сторону мне двигаться, что необходимо прочитать и изучить?

Если вам нужен полноценный map matching - то без погружения в теорию и самостоятельного кодирования не обойтись, готовых библиотек на эту тему я пока не встречал, тем более на php.

[A3om]

Огромное спасибо за ответ, Сергей.

К сожалению, в моём случае имеется множество точек, а именно маршрут, проложенный с помощью этих точек по различным дорогам. Также имеется точка, которая может находиться в любом месте вблизи маршрута. Соответственно, хотелось бы привязать эту точку к ближайшему отрезку - части дороги. Может быть, действительно, можно как-то упростить механизм и сам подход к задаче?

Расскажу о задаче. По дорогам нашего города по определённым маршрутам ездят автобусы. Точки маршрута заранее известны. Также известны точки остановок. В определённый момент времени известно местоположение автобуса. Необходимо вычислить время, за которое автобус пройдёт от точки его местонахождения до определённой (к примеру, ближайшей) остановки.

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

[A3om]

Нашёл Ваш пост (http://forum.openstreetmap.org/viewtopi ... 449#p91449), займусь изучением алгоритмов.
Если же есть более простой вариант, то напишите, пожалуйста. Буду очень признателен.

[gamm]

Если же есть более простой вариант

а то (учитывая мощу современных девайсов, особенно объем памяти).

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

вся работа делается в любой ГИС, трасировка - руками ... как то так

[A3om]

gamm, а ваша идея неплохая
Однако, возиться с каждым маршрутом придётся очень долго.

[ericsson]

Хм, gamm, а нельзя построить эту растровую карту с градиентом просто взяв растр с линиями маршрутов и натравив на него размывание по Гауссу? С областями в окрестности изгибов, правда, выйдет неопределенность...

[Александр Мурый]

Может быть, здесь помогут "сетевые" модули GRASS? Там можно после создания сети "подключать" к ней новые узлы (по кратчайшему расстоянию), находить расстояния между узлами; многие операции производятся с учётом "весов" в виде, например, той же скорости движения или ограничений на скорость. Подробнее расписано тут. Ну и в гугле находится много чего по теме.

[gamm]

Хм, gamm, а нельзя построить эту растровую карту с градиентом просто взяв растр с линиями маршрутов и натравив на него размывание по Гауссу? С областями в окрестности изгибов, правда, выйдет неопределенность...

предлагаемое размытие - неудачная имитация дистанционного преобразования. А для достижения однозначности, как я уже сказал, нужно поработать. Например, использовать то, что ваши точки есть временная последовательность, а автобус едет в одну сторону, а не взад-вперед. В любом случае, для прикидки хватит. А может и вообще хватит.

[Sergey Astakhov]

Расскажу о задаче. По дорогам нашего города по определённым маршрутам ездят автобусы. Точки маршрута заранее известны. Также известны точки остановок. В определённый момент времени известно местоположение автобуса. Необходимо вычислить время, за которое автобус пройдёт от точки его местонахождения до определённой (к примеру, ближайшей) остановки.

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

Ну это гараздо более простая задача, просто в силу того что линий маршрутов намного меньше чем линий дорог.
Я решал аналогичную задачу для нашей системы, map matching для этого не обязателен. Всё что нужно - это отслеживать текущее направление рейса и текущий перегон. Для этого достаточно проверять наличие перегонов текущего маршрута в заданной дистанции и отслеживать порядок их изменений. Map matching тут может быть полезен для автоматического определения маршрутов движения, но это не обязательно, у нас для этого используются свои алгоритмы поиска.

Простейший вариант формирования прогноза прибытия - после определения прибытия на очередную остановку считается прогноз прибытия на последующие остановки по маршруту в данном направлении согласно заведённым нормативам для маршрута. Но это возможно только если известен маршрут и направление рейса. Более сложные варианты - учитывать перемещение вдоль перегона, статистику скоростей, пробочные данные и т.п.

Детали рассказывать не буду - known how как никак.

[gamm]

Я решал аналогичную задачу для нашей системы, map matching для этого не обязателен.

там же Глонассы наверняка стоят? или Глонассы так врут (метров на 500), что без статмодели никуда?

[Sergey Astakhov]

С областями в окрестности изгибов, правда, выйдет неопределенность...

Если бы только изгибы...
Большая засада кроется в маршрутах с петлями, типа таких - 56
А так же есть маршруты где есть больше двух линий (туда-обратно).
А так же есть маршруты, где часть рейсов делается по одним линиям, а часть по другим.
А так же есть маршруты, один - подмножество другого (46 и 46А).
А так же есть маршруты отличающиеся друг от друга парой перегонов (102 и 103).

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

[Sergey Astakhov]

Я решал аналогичную задачу для нашей системы, map matching для этого не обязателен.

там же Глонассы наверняка стоят? или Глонассы так врут (метров на 500), что без статмодели никуда?

Ха, 500 метров... Было дело, видел автобусы, телепортирующиеся в Финляндию и обратно.
А так же автобусы, трек которых был похож на равномерную ковровую бомбардировку всего города.
ГЛОНАСС - это не панацея. Достаточно поставить в автобус китайский видеорегистратор с фонящим блоком питания, как всё слежение насмарку, будь там хоть 10 ГЛОНАСС-ов...
Да и условия эксплуатации для блоков не самые простые, бывает вылетают и по помехам питания (на троллейбусах/трамваях это особенно часто случается), и плесенью зарастают от сырости и т.д. и т.п...

Общий принцип при обработке треков - чем точнее исходные данные, тем проще могут быть алгоритмы. Чем хуже данные - тем более изощрённые алгоритмы приходится применять чтобы хоть что-то адекватное получить в результате.

[A3om]

Sergey Astakhov, а насколько точно определяет время прибытия автобуса Ваша система? Имеется ли в расчёте подключение статистики скоростей и информации о пробках?

[gamm]

Общий принцип при обработке треков - чем точнее исходные данные, тем проще могут быть алгоритмы. Чем хуже данные - тем более изощрённые алгоритмы приходится применять чтобы хоть что-то адекватное получить в результате.

и я о том же, но это обычно про постобработку. Если у вас такие приемники GPS/ГЛОНАСС (что странно, поскольку китайские "брелки" по "$5 за пучок" дают в эксперименте СКО примерно 20 метров), то проще вообще без них обойтись, а, как при советской власти, повесить на остановках RF-ID считыватели, которые фиксируют прибытие на остановку (шикарные такие антенны висели, в ободе от хулахупа). И никаких проблем с map matching, дешево и сердито

P.S. а вот постобработка - интересная вещь, например такая - тыц, тыц. Тут правда животные вместо автобусов, но их тоже славно носит по свету