УПД: Поскольку тема прошла успешно и показала, что спрос на такую услугу есть, буду развивать ее дальше.
Я завел паблик во ВКонтакте для сбора отзывов и публикации информации об обновлениях.
https://vk.com/sightsafari Незнакомый район города, малое количество свободного времени и необходимость (или желание) добираться до метро/гостиницы/станции пешком – наверное, каждый хоть раз попадал в такую ситуацию.
При этом, с одной стороны, хочется увидеть красивые и интересные места, а с другой – ограниченность времени не позволяет слишком сильно отклоняться от прямого маршрута.
Ситуация еще более усложняется, если поблизости нет крупных достопримечательностей, о которых все знают и которые можно было бы включить в свой маршрут после непродолжительного поиска в Интернете.
Что делать, если вы застряли в каком-нибудь Купчино, о котором только и слышали, что там лучше не застревать? Вам предстоит следовать за навигатором, надеясь, что по пути вам встретится что-нибудь интересное.
Однако популярные навигаторы учитывают только расстояние и время в пути, но не учитывают интересность маршрута.
Встречались и другие проекты, в которых стараются учесть удобство пешеходного маршрута (в обход шумных магистралей), но хочется не только комфортно прогуляться, но и увидеть немного красоты.
Немного подумав, я решил взять эту задачу на себя.
Как всегда, общая идея алгоритма довольно проста, но дьявол кроется в деталях.
А в случае с мореплаванием мелочи могут оказаться весьма существенными и представлять опасность для здоровья, ведь вряд ли какой-либо турист будет рад, когда навигатор в поисках достопримечательностей увезет его в дебри полузаброшенного промышленного города.
площадь ради небольшой мемориальной доски (правдивая история, такое было однажды).
Описание алгоритма и примеры работы под катом, ссылка в конце.
Основная идея
Моя первоначальная идея была такая: скачать карту Open Street Map, разобрать ее, извлечь из нее информацию обо всех объектах, потенциально интересных для пешеходов (их список еще не был определен), нарисовать вокруг них какие-то буферные зоны.Мы ищем пути, используя какой-то стандартный фреймворк, немного подправляем процесс построения навигационного графа, чтобы в этих зонах веса ребер становились меньше и тем самым организуем притяжение к ним пешеходных маршрутов.
Сказано - сделано.
Для поиска пути мы использовали библиотеку GraphHopper, которая из коробки умеет читать карты OSM, строить маршруты для разных видов транспорта (автомобильный, пешеходный, велосипедный), имеет несколько разных алгоритмов поиска пути (простой поиск, поиск пути).
альтернативные маршруты, всякие ускоренно-оптимизированные варианты) и может предварительно обработать граф навигации для ускорения поиска (базовый поиск города работает очень быстро, за несколько миллисекунд).
Для примера работы был выбран мой родной Санкт-Петербург – здесь я смог сам оценить качество и интересность построенных маршрутов.
В итоге базовая версия алгоритма была собрана у меня на коленках за пару вечеров, а дальше началось увлекательное путешествие по граблям и мелочам, в которых, как известно, кроется дьявол и о которых я расскажу.
о дальнейшем.
Объекты для туристов и проблемы с OSM
В Open Street Map каждый объект представляет собой геометрию (узел, путь или отношение) плюс несколько строковых пар ключ-значение.
Вот как выглядит Зимний дворец в OSM: 
Проблема в том, что поскольку OSM — открытая карта и редактируется участниками, то стандартизация там хромает с обеих сторон.
Для обозначения однотипных объектов может использоваться разный набор тегов и разные комбинации объектов, некоторые теги считаются «каноническими» и описаны в вики, но вариантов еще масса, как просто альтернативные и откровенно ошибочный, но тем не менее использованный.
В результате любой код, работающий с OSM (особенно всякие навигаторы и рендереры), вынужден всё это учитывать и содержать кучу кода для обработки таких особых случаев.
Например, тег road=unspecified означает не «какую-то дорогу неизвестного типа», как думают многие картографы, а вполне конкретный тип дороги по европейской классификации, но ставят его где угодно из-за названия.
Более того, у этого типа дороги предполагается наличие пешеходной обочины или тротуара, поэтому навигатор строит по ней пешеходные маршруты, в то время как по настоящей дороге, такой как в Санкт-Петербурге (это проезжая часть улицы), пешеходы не ходят. Или вот еще пример: тег addr:housename иногда используется для названия зданий, например, почему-то через этот тег названо западное крыло Главного штаба на Дворцовой площади.
При этом в руководствах самого OSM говорится, что его следует использовать только в тех странах, где вместо номеров домов используются имена (в Японии вроде так делают), а для официальных названий зданий используйте тег имени и тому подобное.
.
Еще меня бесит это разметка зеленых зон.
Для этой цели есть два разных тега: Lease=park и Landuse=grass. На карте они выглядят примерно одинаково: просто зеленая зона, немного отличающаяся по цвету.
В результате их лепят смешивают между собой как хотят. Из-за этого газон, разделяющий проезжие части, часто превращается в «парк» и начинает привлекать пешеходные маршруты.
Все эти нюансы пришлось выяснять по мере построения и анализа маршрутов.
В качестве набора объектов, представляющих интерес для пешеходов, в конечном итоге был выбран следующий список: Туристические достопримечательности с тегом туризм Зеленые зоны.
досуг = парк, сад. После некоторых раздумий были добавлены Landuse=cemetry и кладбища.
С одной стороны, это так себе достопримечательность, с другой, например, на Васильевском острове в Санкт-Петербурге единственная большая зеленая зона — это кладбище, которое местные жители используют вместо парка, а настоящих здесь нет. парки там вообще.
Вода: реки, озера, пруды.
Существует мешанина тегов вода, водный путь и куча повторяющихся значений.
Как приятно прогуляться по набережной в жаркий день.
Во всяком случае, я так думал, пока не попробовал работать над Смоленском - вдруг выяснилось, что в глубинке берега реки не красивая набережная, как у нас в Питере, а заросший и замусоренный пустырь, из которого пешеходы предпочли бы держаться подальше.
Но отличить эти ситуации исключительно на основе картографических данных пока невозможно.
Исторические здания и сооружения, отмеченные тегом исторический.
Они обычно просто красивые Все остальные мелочи города отмечены дорожной биркой.
Значений у него много, я выбрал лишь несколько, например, уличные часы (часы) - часто красивые, религиозные здания (места_поклонения), все виды уличного искусства (граффити) и некоторые другие.
Пешеходные улицы и площади, шоссе=пешеходное По ходу исследования я понял, что помимо положительных моментов, привлекающих пешеходов, необходимо добавить и отрицательные, отталкивающие их.
В этот список на данный момент входят: Использование земли под застройку = строительство.
Пешеходам не очень приятно ходить под строительными лесами и в пыли, летящей со стройплощадки Промышленные зоны и гаражи, Landuse=промышленные, гаражи.
Вот тут-то и случился нюанс с установлением пешеходной дорожки (и мы в Институте дизайна и урбанистики ИТМО проверяли это на студентах, которые ходили по проложенным маршрутам, а потом писали отзывы в рамках исследования пешеходного удобства Петроградского района).
р-н) в дебрях промзоны Ленполиграфмаша.
Оказалось, что этим тегом отмечен не весь квартал (как это обычно делается для обозначения крупных промзон), а каждое здание в отдельности.
В идеале хочется еще и увести пешеходов с широких городских магистралей, где пыльно, шумно, много машин и смотреть обычно не на что.
Но пока однозначно обнаружить их не удалось.
В ОСМ по сути есть только количество автомобильных полос, но этого критерия недостаточно (многие важные туристические улицы, например Невский проспект, тоже многополосны)
Тот самый Ленполиграфмаш, который где-то в своих дебрях содержит памятник печатному станку, и куда мой алгоритм затащил бедного студента 
Важность достопримечательностей
Понятно, что достопримечательности разные.Есть крупные, всемирно известные объекты - вроде Эйфелевой башни или Исаакиевского собора в Санкт-Петербурге, которые привлекают огромное количество туристов, и для посещения которых можно совершить приличный объезд. И есть какие-то небольшие, местные декорации – какой-то стрит-арт, маленькая скульптура во дворе, которую люди готовы рассматривать только по дороге и не хотят тащиться к ним издалека.
Чтобы правильно строить интересные и удобные маршруты, нам пришлось научиться как-то разделять разные категории достопримечательностей, а в OSM все, что у нас есть, — это определенная геометрия и набор тегов.
Нам пришлось придумать набор эмпирических правил для определения «важности» ориентира, что впоследствии определяет изменения весов на графике.
Первоначально важность равна нулю и увеличивается при выполнении следующих условий: +3 если есть историческая метка - она есть только у важных исторических зданий, да и то не у всех +3 за наличие тегов Википедии или Викиданных.
Обычно только важные объекты имеют свои страницы в вики.
+1 за наличие ссылки или урла - опять же не у каждого есть свой сайт, но часто этот тег ведет на страницу какого-то каталога и у небольших объектов он есть +1 за каждое имя.
Имя можно указать кучей способов, могут быть всякие old_name для исторических названий или названий, переведенных на другие языки.
Опять же наличие множества названий говорит о достаточной важности объекта (поскольку кому-то надоело их все записывать) Building:architecture — архитектурный стиль, обычно размещаемый на всевозможных красивых памятниках архитектуры.
Этот список определен эмпирическим путем и, по крайней мере, позволяет отделить Зимний дворец от безымянных граффити на окраинах.
В итоге важность, равная 0, означает какой-то локальный небольшой безымянный объект (кусочек зелени, граффити), около 3-4 означает что-то интересное (церковь, площадь, где можно посидеть и отдохнуть), ближе к 10 город- Уровень аттракционов начинается, тот же Зимний дворец.
Список не идеален и во многом опирается на данные OSM, которые зачастую неполны.
Например, Нарвские ворота изначально имели только одну единицу значения, поскольку кроме названия для них ничего не было написано.
Пришлось самому зайти в OSM и добавить названия, стиль, годы постройки, высоту (чтобы правильно определить видимость, об этом позже) и т.д. В общем, в этом есть и общественная польза - улучшить качество маршрутов.
, время от времени захожу в OSM и добавляю туда недостающие теги, которые потом могут использовать другие навигаторы или программы.
Сферы влияния
Аттракционы бывают разных размеров.Любую небольшую скульптуру следует рассматривать с расстояния не более 5-7 метров.
Медный всадник хорошо виден с 20-30. Исаакиевский собор - одно из самых высоких зданий в центре города - хорошо виден с 200-300 м (я имею в виду, что туристу не обязательно подходить близко, а вполне комфортно наслаждаться видом с такого расстояния; видно за километр с другого берега Невы, но без подробностей).
Как определить, на каком расстоянии ориентир должен влиять на пешеходные маршруты?
Медный всадник и купол Исаакиевского собора вдали 
Сначала я эмпирически построил радиусы видимости.
Они опираются на всю доступную информацию о точке интереса и превращают ее в один из четырех радиусов: маленький 30 метров, средний 100, большой 250 и огромный 350 метров.
Видимость рек и парков немного другая.
Для них я установил 30 метров, т. е.
примерно соответствует ширине набережной или улицы вокруг парка.
Поскольку смотреть на парк издалека совершенно бессмысленно, нужно идти рядом с ним.
Тип видимости определяется следующими правилами: Точечные (т. е.
заданные типом OSM Point) объекты имеют Малую видимость, обычно это небольшие памятники и уличное искусство.
А вот точечные и с тегом исторический — Средние, потому что.
это часто большие памятники на высоких постаментах, такие как Медный всадник.
Участки размером менее 20*20 метров (пути или родственники) относятся к средним.
Больше - Большой Если у объекта есть тег height (высота в метрах) или Building:levels (количество этажей), то при высоте более 50 метров он считается Огромным — это сделано специально для Исаакиевских и других крупных соборов и зданий, видимых с издалека Но возникла проблема: в плотно застроенном историческом центре Петербурга наивный подход с радиусами не сработал, так как реальная площадь видимости какого-то храма, стоящего в глубине двора, была значительно меньше ; на самом деле его было видно только с участка улицы, прямо напротив него.
Пришлось начать строить честные (ну почти) полигоны видимости.
Церковь Святой Екатерины стоит в глубине двора, со всех сторон окруженная домами: 
Сначала нам нужно было определиться с препятствиями.
Ну тут все просто, я взял и прочитал из данных OSM все полигоны с тегом здания.
Это будут полигоны, закрывающие нашу видимость.
Затем я написал простой наивный алгоритм построения многоугольника видимости точки с помощью трассировки лучей.
Мне там не нужна высокая точность; десяти лучей было достаточно для точки.
Сначала я, не мудрствуя лукаво, взял центр тяжести геометрии ориентира, но для вытянутых (длинных и узких) зданий это дало не лучшие результаты.
Поэтому в дальнейшем для крупных достопримечательностей я стал брать три точки — центр тяжести и две наиболее удаленные от него и друг от друга точки на внешней границе.
Почему я не построил честный внешний вид? Потому что если алгоритм построения зоны видимости точки тривиален (стреляем лучи из точки во все стороны, смотрим, где они пересекли ближайшие препятствия, соединяем эти точки), то построение честной видимости ребра (и , в результате получается многоугольник) гораздо сложнее (первое, что приходит в голову решение — построить внешний вид двух концов ребра и совместить — заведомо неправильное).
Результат оказался хорошим приближением.
Он построен не идеально, но для нужд пешеходной навигации нам достаточно такой точности.
Проблема только в том, что здесь не учитывается высота зданий, т. е.
любая маленькая будка закроет нам обзор пятиэтажной колокольни.
Но с этим ничего не поделаешь — данные OSM не всегда содержат этажность, а построить объемы видимости в 3D гораздо сложнее.
Хотя, возможно, я вернусь к этому позже.
Построены полигоны видимости для этой и соседних церквей.
Красота маршрута и как его улучшить
Итак, мы научились учитывать важность и заметность достопримечательностей и, кажется, начали строить хорошие маршруты.Во всяком случае, так было, пока я тестировал в центральных районах Петербурга, где очень высокая плотность красивых вещей на квадратный километр.
Однако стоило нам немного отойти от центра, как алгоритм вдруг начал признавать свое бессилие.
И построенный им маршрут стал совпадать с кратчайшим.
Так как достопримечательности в этих областях - кот плакал, они расположены далеко друг от друга, поэтому при поиске пути по комбинированной метрике «красота + расстояние» вклад первого слагаемого оказался близок к нулю, т.к.
в результате алгоритм просто построил кратчайшие маршруты.
Конечно, всегда можно было бы сказать «это не мы, это наши города такие скучные», но это было бы не очень правильно.
Поэтому я задался вопросом, как оценить построенный маршрут и как его можно улучшить.
Самое простое решение, которое сразу приходит в голову — удлиним маршрут, принудительно вставив в него объезд к какой-нибудь достопримечательности, оставшейся в стороне.
Теперь в тех случаях, когда а) общая сумма важности всех достопримечательностей маршрута на километр меньше определенного значения или б) пользователь сам выбрал для построения наиболее интересный маршрут, мой алгоритм пытается его улучшить.
Для этого строится первоначальный маршрут, вокруг него берется буфер (его толщина определяется длиной, чем длиннее маршрут, тем более длинный объезд допускается делать), внутри этого буфера несколько новых (еще не включенных в маршруте) ищутся достопримечательности с баллом > 2 (мы не хотим делать объезды на километр до безымянных скверов) и прокладываются новые маршруты от начальной точки до этой промежуточной цели, а от нее до конечной точки.
При этом дополнительно контролируется длина; в итоге мы должны получить маршрут не более чем в два раза длиннее кратчайшего пути между начальной и конечной точками.
Первая версия алгоритма (слева) оказалась бессильна найти что-нибудь интересное и построила кратчайший маршрут. А вот версия с добавлением промежуточного ориентира (справа) включала ДОТ КВ-19 , он расположен в правом нижнем углу маршрута (на этом уровне масштабирования он не виден, но сервис покажет его в списке и позволит найти на карте, нажав на название).
Тот самый бункер.
В целом подобных объектов, связанных с обороной Ленинграда, в Купчино достаточно, поскольку именно здесь располагались оборонительные рубежи города: 
Конечно, не каждый пешеход согласится сделать объезд ради какой-то незначительной, по его мнению, достопримечательности.
Именно поэтому сервис показывает длину маршрута по сравнению с кратчайшим и список достопримечательностей на нем, а пользователь может сам решить, интересен ли ему такой маршрут. Плюс есть ползунок, позволяющий уменьшить (или наоборот увеличить) максимально допустимый зацеп.
На практике мне пришлось столкнуться еще с некоторыми проблемами и странностями.
Во-первых, при наивной реализации буфера вокруг маршрута он «вылезал» за начало и конец.
И часто возникали ситуации, когда маршрут уходил за конечную точку еще на пару сотен метров.
Или, наоборот, он шел с начала в противоположную от конца сторону, и только потом возвращался в нужное направление.
Хотя такие маршруты позволяли увидеть больше достопримечательностей, пешеходы очень не любят, когда их увозят слишком далеко от места назначения.
Пришлось сначала «выколоть» область вокруг конечной точки на графе навигации (сделать ребра непроходимыми при поиске пути до промежуточной точки), а потом строить буфер не вокруг всей линии маршрута, а только начиная с определенное расстояние от начала и окончание на определенном расстоянии до конца.
Вторая проблема заключалась в том, что маршруты возвращались по одной и той же улице.
Не знаю, как вы, а я ненавижу возвращаться тем же путем, которым пошел вперед. Я всегда предпочитаю идти другим путем.
И поэтому я пытаюсь добиться такого же поведения от моего алгоритма.
Правда, это все еще проблема.
В качестве первой попытки я добился того, что все ребра (кроме последнего), участвовавшие в пути от начала до промежуточной точки, были вырезаны из графа при поиске пути от промежуточной точки до конца.
Это позволяет избежать возврата точно тем же путем, но не защищает от почти того же пути — например, возвращения на другую сторону той же улицы.
Вырезание всех ребер в окрестности часто делает совершенно невозможным поиск пути назад. В общем, есть еще над чем подумать.
Хотя в этом плане мой алгоритм уже работает лучше, чем у некоторых моих конкурентов, которые просто не задумываются над этой темой и легко строят тупиковые ответвления маршрута.
Примеры работ
Текущая реализация находится на Достопримечательности Сафари.Сити
Геокодера там пока почти нет (есть OSM, но он работает довольно плохо), поэтому точки лучше размещать прямо на карте, правым кликом или долгим тапом.Ползунок отвечает за тип маршрута: крайнее левое положение ищет самый короткий, без учета достопримечательностей, третье по умолчанию дает хороший баланс, крайнее правое всегда пытается улучшить маршрут и часто генерирует довольно запутанный маршрут. пути.
Вот несколько примеров.
Маршрут от дома, где я раньше жил, до метро «Московская», по мнению Яндекса, представляет собой скучный путь по дворам и улочкам: 
А вот маршрут по моему алгоритму.
Она проходит по окраине парка Победы, мимо исторического музея, мимо Чесменской церкви и дворца, по площади Дома Советов мимо фонтанов и крутой сталинской архитектуры.
Чесменская церковь.
Сам я обычно делал небольшой крюк, чтобы пройти через это место, а не прямо через скучные дворы хрущевских построек.
Вот еще пример: кратчайший путь от Смольного (где находится администрация Санкт-Петербурга) до станции метро «Площадь Восстания» идет по Суворовскому проспекту.
Но рядом, немного в стороне, находится прекрасный Таврический сад, куда мой алгоритм и пригласит вас заглянуть.
Заключение
Пока сервис работает только для Санкт-Петербурга, Пушкина и Смоленска (районы с доступной навигацией отмечены красным пунктиром).Нам еще многое предстоит улучшить, и для этого нам в первую очередь нужна обратная связь.
Так что пробуйте, пишите отзывы о маршрутах (над списком достопримечательностей есть кнопка), надеюсь, кому-то будет интересно и полезно.
По запросу могу подключить новые города - Москва, возможно, боюсь сервер треснет (хотя можно и не весь сервер, а только центр, конечно), но можно и что-то поменьше.
Главное, что OSM более-менее хорошо обозначен для этого региона, и что есть некоторые достопримечательности, что не очень интересно в маленьких городах (в том же Смоленске, который я добавил там для одного друга, все интересное есть сосредоточены в 2-3 местах города, и их можно обойти без какой-либо умной навигации).
УПД: добавлены Москва в пределах ТТК, Уфа, Калининград, Нижний Новгород, Киев, Казань, Ростов-на-Дону, Благовещенск, Саратов, Пенза, Одесса, Минск, Екатеринбург, после чего на сервере закончилась память.
Так что заявки на новые города временно не принимаются, пока я не придумаю, как оптимизировать это дело.
УПД 2: Геокодер OSM, как я уже писал, работает плохо (он знает мало адресов и требует структурированных входных данных), поэтому лучше расставлять точки на карте вручную, чем вводить адрес.
В будущем нам придется что-то придумать по этому поводу, но все нормальные геокодеры (например, от Яндекса) стоят слишком больших денег для хобби-проекта, а в бесплатной версии у них слишком ограничительная лицензия (например, выводить результаты поиска можно только на карту самого Яндекса).
УПД 3: Завел паблик в ВК, где могу размещать свои идеи, запросы на новые города и где буду писать об обновлениях сервиса.
https://vk.com/public168028574 Теги: #Алгоритмы #Урбанизм #Геоинформационные услуги #навигация #graphhopper #поиск пути #туризм #пешеход
-
Основы Сравнения Программного Обеспечения
19 Oct, 24 -
Разработка Веб-Приложений: Наша Методология
19 Oct, 24 -
Новая Опера-9.6 - Новые Возможности
19 Oct, 24 -
Интернет Для Дачников. Часть 3. Русские Идут
19 Oct, 24
