Незнакомый район города, небольшое количество свободного времени и необходимость (или желание) пешком добраться до метро/отеля/вокзала – наверное, каждый хоть раз попадал в такую ситуацию. При этом с одной стороны хочется посмотреть какие-нибудь красивые и интересные места, однако с другой стороны ограниченное время не позволяет слишком сильно уклоняться от прямого маршрута.
Ситуация еще больше осложняется, если рядом нет никаких крупных достопримечательностей, о которых все знают и которые можно было бы включить в свой маршрут после короткого поиска в интернете. Что делать если вы застряли в каком-нибудь Купчино, про которое вы только и слышали, что там лучше не застревать? Приходится идти по навигатору, надеясь, что на пути встретится что-то интересное. Однако популярные навигаторы учитывают лишь расстояние и время в пути, но не принимают во внимание интересность маршрута. Мне попадались еще проекты, пытающиеся учитывать удобство пешего маршрута (ведущие в обход шумных магистралей), но хочется же пройти не только комфортно, но и увидеть какие-нибудь красоты.
Подумав немного, я решил взяться за эту задачу сам. Как всегда, общая идея алгоритма довольно проста, но дьявол кроется в мелочах. А в случае навигации, мелочи могут быть довольно существенны и с риском для здоровья, ведь вряд ли какой-нибудь турист обрадуется, когда навигатор в поисках достопримечательностей заведет его в дебри полузаброшенной промзоны ради маленькой мемориальной таблички (тру стори, один раз так и случилось).
Описание алгоритма и примеры работы под катом, ссылка в конце.Читать полностью »