И так, формулировка задачи следующая: есть база данных, в ней хранится информация о дорогах, включая координаты, нужно реализовать построение маршрутов из начальной точки к конечной.
Построение маршрутов - задача распространенная, и, как для каждой распространённой задачи, для неё давно существуют реализации. Мне нравится GraphHopperЧитать полностью »
Всем привет! Меня зовут Александр, я разрабатываю ActiveTrip.me — cервис для построения маршрутов для пеших, велосипедных, водных походов и путешествий, а также для хранения и группировки интересных мест в виде меток.
О том, почему мы начали делать такой сервис, расскажем подробно в отдельной статье, а здесь осветим технические особенности.
Построение маршрутов..., люди регулярно этим пользуются, особенно для автомобильных маршрутов, в навигаторах.
Решений, для построения маршрута тоже немало, в том числе существует GraphHopper, который умеет строить маршруты, и для автомобилей, и для пешеходов, и даже для пешего туризма, - подойдёт, наверно, в 99% случаев.
Незнакомый район города, небольшое количество свободного времени и необходимость (или желание) пешком добраться до метро/отеля/вокзала – наверное, каждый хоть раз попадал в такую ситуацию. При этом с одной стороны хочется посмотреть какие-нибудь красивые и интересные места, однако с другой стороны ограниченное время не позволяет слишком сильно уклоняться от прямого маршрута.
Ситуация еще больше осложняется, если рядом нет никаких крупных достопримечательностей, о которых все знают и которые можно было бы включить в свой маршрут после короткого поиска в интернете. Что делать если вы застряли в каком-нибудь Купчино, про которое вы только и слышали, что там лучше не застревать? Приходится идти по навигатору, надеясь, что на пути встретится что-то интересное. Однако популярные навигаторы учитывают лишь расстояние и время в пути, но не принимают во внимание интересность маршрута. Мне попадались еще проекты, пытающиеся учитывать удобство пешего маршрута (ведущие в обход шумных магистралей), но хочется же пройти не только комфортно, но и увидеть какие-нибудь красоты.
Подумав немного, я решил взяться за эту задачу сам. Как всегда, общая идея алгоритма довольно проста, но дьявол кроется в мелочах. А в случае навигации, мелочи могут быть довольно существенны и с риском для здоровья, ведь вряд ли какой-нибудь турист обрадуется, когда навигатор в поисках достопримечательностей заведет его в дебри полузаброшенной промзоны ради маленькой мемориальной таблички (тру стори, один раз так и случилось).
Описание алгоритма и примеры работы под катом, ссылка в конце.Читать полностью »
