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

Вот и известному блоггеру Илье Варламову тоже так показалось, поэтому он запустил крутейший проект c вызывающим названием БДСМ, а имеенно "Большая Дорога С Мэром" (ссылка на анонс):

Хватит гулять по российским городам в одиночестве – пора приглашать мэров, губернаторов, сити-менеджеров.

Правила просты.

Компьютер случайным образом выбирает два адреса в вашем городе. После этого мы отправляемся на прогулку от одного адреса к другому. Условие одно: нельзя пользоваться автомобилем. Только ноги, велосипед, общественный транспорт, самокат, собачья упряжка. Никакой подготовки, никаких согласований маршрута. Иногда прогулки будут длинные, через весь город, иногда придётся пройти всего несколько кварталов по центру. Это главное условие: без показухи, без подготовки.

В процессе прогулки мы вместе с главой города изучаем инфраструктуру, общаемся с жителями. У чиновника будет уникальная возможность рассказать на всю Россию про свой город, объяснить тонкости городского управления, стать ближе к народу!

Кадр из первого видео проекта, с участием моего сервиса для выбора случайных точек

При чем тут Хабр, спросите вы? А все дело во фразе про случайный выбор адреса начала и конца маршрута. Не такая это простая задача, если вы не хотите в итоге очутиться в дебрях какой-нибудь промзоны или заблудиться среди бесконечных заборов частного сектора. Простое тыканье в карту с завязанными глазами тут не сработает!

О том, как я эту задачу решал и какие открытия преподнесли мне такие города как Иваново или Киров — под катом.

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

Идея

По задумке команды Варламова это должно было выглядеть так: по карте города прыгают туда-сюда маркеры начальной и конечной точек, наглядно демонстрируя случайность процесса. Сам мэр в любой момент лупит по кнопке и останавливает поиск. После чего они выбирают маршрут (жаль что вручную, тут-то мой сервис пешеходных маршрутов мог бы им предложить что-то интересное) и идут гулять по городу.

Изначально требования к точкам были такие:

1. Расстояние между точками не меньше 3 километров
2. Точки не в промзоне и не в частном секторе
3. Точки обязательно находятся в разных частях города, так чтобы маршрут между ними вел через центр

Потом в ходе разработки добавилось еще одно требование: сервис должен уметь взаимодействовать с хардверной Большой Красной Кнопкой, вот такой:

Кнопка просто посылает сигнал клика мышкой на подключенный компьютер

Вся сложность была в том, как составить этот маршрут так, чтобы с одной стороны избежать совсем уж дебрей, а с другой — все-таки охватить возможными точками все районы города, а не только несколько "приличных" кварталов в центре. При этом изначально у меня был некий сформированный набор стереотипов в голове, являющихся следствием того, что я сам живу в Санкт-Петербурге, кроме того из более-менее крупных российских городов был только в нескольких миллионниках типа Москвы и Казани. Вот только проект в основном концентрировался на городах с населением 200-500к человек (видимо мэры более крупных городов слишком заняты, чтобы ходить по улицам). В общем я в очередной раз получил подтверждение тезиса что "Москва — не Россия". Все соображения ниже — неверны:

1) Многоэтажные дома в центре, а промзоны и частные дома на окраине.
2) Хотя бы есть разделение по кварталам — в одном квартале только многоэтажки, в другом — только частные дома. Ну кто будет строить хрущевку среди деревянных изб?
3) Территория города представляет собой один простой полигон на карте, внутри которого находятся все здания
4) Ладно, в полигоне могут быть дырки, но он хотя бы один
5) Ну ладно, не один но хотя бы не более двух несвязанных кусков
6) Города в OSM данных размечены соответствующими тегами landuse и выбрать жилые районы будет просто

В общем, пришлось походить по граблям.

Алгоритм выбора точек

Для начала пришлось решить, как именно будут выбираться стартовая и конечная точки. Идею кидать точку случайным образом в произвольные координаты в границах города я отбросил почти сразу. БОльшая часть города на карте — это разного рода непроходимые территории: полигоны домов, рек, просто неразмеченные территории на которых непонятно что находится. Честно-случайная точка будет очень часто попадать в них, придется либо ее сдвигать (что довольно сильно в итоге скажется на случайности), либо перебрасывать пока не попадешь в подходящее место (а это скажется на скорости работы).

Поскольку для прогулки нужна не произвольная точка, а та, до которой можно дойти пешком, я решил брать точки только вдоль дорог. В итоге мой алгоритм берет все OSM-ные дороги (Way с тегом highway и значениями, соответствующими пешеходным дорогам и тротуарам), разбивает слишком длинные ребра добавляя промежуточные точки (так чтобы соседние точки на одном ребре были друг от друга не более чем в ста метрах), затем удаляет точки которые оказались слишком близко друг от друга (ближе 50 метров), например на нескольких параллельных дорогах.

Размеченные точки для Ярославля, вырезаны кварталы частных домов и промзона вдоль железной дороги

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

А как их выбрать? У нас для этого есть два требования: не ближе трех километров друг от друга и в разных частях города, чтобы маршрут обязательно провел через центр. Если первое условие выполнить просто, то для второго мне потребовалось определить собственно центр. Из карт такую информацию особо не выжмешь (геометрический центр города совершенно не факт что является его историческим центром).

Для этого я решил пойти простым путем, и просто размечать центр города вручную. Добавил загрузку полигонов в GeoJSON, которые я редактировал с помощью очень удобного сайта geojson.io (серьезно, если вам надо в вашем проекте работать с простой 2д геометрией, то geojson.io позволяет очень быстро все сделать и не париться с созданием своих редакторов или с использованием всяких тяжеловесных ГИС-приложений).

Размеченный Киров, с отмеченным центром (желтый), удаленными вручную областями (красный) и добавленным кусочком (зеленый)

Таким образом первая версия алгоритма была готова за два дня и началась пора тестирования. И вот тут-то полезли подводные камни.

Частный сектор

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

Борьба с этими кварталами заняла бОльшую часть времени. Сперва я попробовал обойтись чисто OSMными данными. Есть специальное значение тега residental=rural для обозначения сельской местности и landuse=allotments для всяких садоводств.

Да, даже в Санкт-Петербурге есть встроенные садоводства в городской черте

Однако быстро выяснилось, что эти теги ставят довольно редко, и обычно удовлетворяются только самым общим landuse=residental (жилая территория).

Следующим шагом стала попытка отсеять такие кварталы вручную. К geojson-файлу с центром города я добавил поддержку ручного удаления областей. К сожалению, быстро выяснилось что куча итераций цикла "загрузил карту — поглядел глазами — нашел частный сектор — вырезал его в geojson.io — снова загрузил" занимает очень много времени, особенно в городах где частные дома идут вперемешку с многоэтажными и раскиданы небольшими группами там и тут. Например в Иваново

Частные и многоквартирные дома густо перемешаны друг с другом всего в паре кварталов от центра

Пришлось придумывать эмпирический алгоритм. Я брал квартал (область landuse=residental, хотя прямого требования к ее использованию нет, обычно ей отмечают не весь город или район, а отдельные кварталы), брал все здания в его границах (полигоны с тегом building) и считал среднюю площадь такого полигона. Если выходила меньше 400м2 (цифра взята с потолка, с условием грубости разметки и подсчетов и встречающихся в таких кварталах отдельных длинных домов) то квартал считался частным сектором и из подсчетов выкидывался.

В итоге сочетание этих трех методов позволяло более-менее эффективно отфильтровывать нежелательные районы, хотя и не без участия ручного труда.

Но разумеется потом встретились и исключения. Например Евпатория, где вообще весь исторический центр — по сути узкие улочки частного сектора. Если его весь выкинуть — от города ничего не останется.

Типичный пейзаж Евпатории в паре сотен метров от берега моря

Специально для таких случаев пришлось добавить в GeoJSON не только удаленные вручную сектора города, но и добавленные вручную. Т.е. даже если квартал не попадал под другие условия, он все равно включался в список доступных для поиска точек.

Промзоны и коммерческие площадки

С промзонами все гораздо проще чем с частным сектором. Как правило они уже размечены тегом landuse=industrial и с ними проблем нет. Разве что есть некоторые исключения, когда размечены не кварталы целиком, а отдельные здания. Но поскольку я в проекте использовал уже готовый код работы с картами из Sight Safari, там уже это учитывалось.

С коммерческими площадками landuse=retail пришлось повозиться вручную. Так как в половине случаев таким образом размечают крупные рынки или торговые центры, а во второй половине — оптовые склады где-то на окраинах, или вообще грузовые терминалы куда посторонним вход воспрещен. Стандартизация, как обычно, хромает. К счастью таких зон довольно немного, этот тег не очень популярен, так что не составило труда разобраться с ними вручную.

Заодно пополнил свой список веселых топонимов, которые часто встречаются в промзонах. Например в Ярославле есть Тормозная улица. Если бы я там жил, то обязательно бы завел там офис для своей ИТ конторы.

Картографические внезапности

Хоть у меня уже и был определенный опыт работы с OSM, все равно постоянно всплывало что-то новое.

Например у Ярославля оказался незамкнутый внешний контур. Визуально он выглядит замкнутым, однако ссылается на отсутствующие узлы и линии. Возможно проблема экспорта.

Много наркомании нашлось в границах городов. Я-то по своей наивности думал, что граница города — это всегда простая замкнутая ломаная линия. Ан нет.

Есть города с дырками. Например Обнинск. То есть вот реально кусок внутри города административно ему не принадлежит.

Обнинск с дыркой

Есть города, состоящие из нескольких несвязанных областей, такие как Киров. Причем если в среднем кусочке Кирова есть несколько кварталов, то левый, самый маленький — вообще лишь кусок дороги, ведущей к аэропорту, и четыре дома. В чем была соль вырезать такой кусок и присоединять его к городу?

Киров состоит из трех несвязанных областей

Наверняка если программа БДСМ будет продолжаться и я продолжу в ней участвовать — познакомлюсь еще с какими-нибудь нетривиальными картографическими ситуациями, которые сейчас сходу и вообразить не могу.

Проблемы с разметкой карт

Пара слов про разметку OSM.

В последних городах, которые я обрабатывал, я столкнулся с тем что люди не ставят теги landuse, или ставят их кое-как. В самом деле, человеку который далек от ИТ, может быть не очень понятен глубокий смысл этих тегов. Ну подумаешь, цвет карты они меняют (жилые кварталы серенькие, промзоны розовые и т.п.), казалось бы непринципиально. И потому относятся многие к ним довольно небрежно.

Однако на мой взгляд сила OSM — именно в возможности машинной обработки больших объемов данных, типа того что делал я тут или в Sight Safari. Просто карт в интернете много, а вот карт с возможностью выкачать всю геометрию и теги и свободно использовать в своих алгоритмах я больше не знаю. И вот как раз для таких целей эти теги начинают играть важное значение. Так как почти всегда задачи выглядят как "найдите что-то там в районах определенного типа", а тег landuse — первый и самый простой способ определить и найти нужные районы.

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

В общем ставьте теги, господа! Ну пожалуйста!

И да, на основании найденных проблем я сам прошелся по картам и немного тегов порасставлял. Так что польза сообществу от этого проекта тоже нарисовалась.

Так куда же я все-таки отправил мэра?

Поскольку в самих съемках я участия не принимал, да и большая часть моей работы была закончена еще до съемок первого эпизода, я вынужден был довольствоваться той же отрывочной информацией из публичных источников, что и все остальные.

Вообще было немного стремно, не заведет ли мой алгоритм их совсем в какую-нибудь глухомань. Особенно стремно стало, когда я прочитал такое вот в посте про Иваново:

Владимир Шарыпов, мэр города, оставил приятное впечатление. Открытый и откровенный человек. Я бы сказал, слишком откровенный для чиновника. Разговор получился интересный. Сходили на Сортировку, где спонтанно состоялась встреча с некоторыми избирателями.

Всё бы ничего, но в 14 часов на Сортировке трезвых нет. По условиям шоу мэр должен ходить без охраны. Я даже в какой-то момент подумал, что будет драка, так как некоторые граждане были явно в неадекватном состоянии. Но обошлось.

Ну и наконец вышла первая серия на канале, можно смотреть.

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

Заключение

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

Как видите, не такая уж это тривиальная задача — копаться в картах и выбирать случайные точки. И на каждый очевидный алгоритм жизнь готова подкинуть вам десяток городов, где он не работает.

На правах рекламы: всем этим я сейчас занимаюсь на базе Института дизайна и урбанистики в ИТМО. Мы там делаем много интересных штук связанных с ИТ и городскими данными, если кому-то эта тема интересна — приходите к нам учиться в магистратуру или работать.

В ходе подготовки проекта активно использовался код и опыт проекта Sight Safari — навигатора для поиска туристических маршрутов.

Ну и напоследок: как вы думаете, полезная ли это инициатива — такие прогулки с мэрами? Изменят ли они что-нибудь? Какие вопросы вы бы задали мэру своего города?