Перколяция в роутинге

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

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

Никогда не поверю, что на развитии алгоритма Дейкстры все остановилось. В чем причина? В иной терминологии? В специфике задач? Или может, реальность такова, что любая разновидность модели Шкловского — де Жена оказывается бесполезной? Даже если так, все-равно кого-то должна была соблазнить идея рассматривать построение связного графа в качестве фазового перехода.

Тема безгранична для теории и практики картографов-урбанистов. Особенно, если представить дорожную сеть как набор ламинарных и хаотических участков. Введя ограничение на максимальную протяженность маршрута, вы получите области в которых небольшое отклонение от маршрута ведет к невозможности его завершения. Значит можно рассчитать размерность Хаусдорфа-Безиковича для фазового пространства дорожной сети. Я только не понимаю, что такая размерность будет означать и как ее рассчитывать. Но это все-равно интереснее инструкции по установке графхоппера.

Уличная топонимика

Пройдусь по Абрикосовой

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

Провел небольшое исследование на городе Шахты. Оказалось, что из 1073 именованных в OSM улиц почти половина (45 процентов) названа в честь людей. На втором месте по частоте (19 процентов) улицы, которые назвали в честь других топонимов, например Московская, Челябинская, Байкальская и др. Кстати, по неизвестной причине такие названия часто группируют, образуя целые кварталы. Самый известный пример — питерская балерина («Разве можно верить пустым словам балерины») — ряд параллельных улиц вдоль Обводного, которые названы в честь пригородов Москвы.

Третье место занимают топонимы, названия которых отражают свойства местности. Это те самые «Полевые», «Речные», «Вишневые» и подобные им. Если не брать популярное название «Садовая», улицы эти обычно коротки и второстепенны. Короче них только улицы с названиями, которые вообще классифицировать невозможно. Например, «Мясокомбинатовский тупик». Зато такие улицы на пятом месте по встречаемости (9,5 процентов). Они уступают лишь топонимам, которые связаны с производственной деятельностью (11 процентов). Улицы с трудовыми названиями удалены одновременно и от исторического центра и от городских окраин.

Любопытно, что революционные топонимы вроде «Депутатская», «Советская», «Комиссаровский» одни из самых редких, их около пяти процентов. Но большинство в центре города. Это самые многолюдные улицы, поэтому иногда думаешь, что других топонимов у города вообще нет.

Замыкают список названия улиц, связанные с культурой, наукой и спортом («Творческая», «Стадионный») с тремя процентами и военные названия («Оборонная», «Солдатская» и др.) доля которых всего два с половиной процента.

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

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

Пивопровод на ХБК

В поселке ХБК сто четыре жилых дома, которые необходимо подключить к пивопроводу. Само собой, сделать это необходимо с минимальными издержками на прокладку труб и дальнейшее их обслуживание.

Для проектирования пивопроводной сети, откроем в QGis карту OpenStreetMap с помощью плагина QuickMapServices или его старого аналога OpenLayersPlugin:

1

Приблизим интересующий нас район, и создадим полигональный шейп-файл:
2

Обведем контуры поселка:
3
Теперь, требуется загрузить контуры домов, нуждающихся в подключении. В нашем случае самым простым решением будет импорт зданий из базы геоданных OpenStreetMap с помощью сервиса Overpass turbo. Мы для этих целей воспользуемся плагином QuickOSM, загрузив полигональные объекты со значением «building=apartmens». В OSM полигонального типа нет, модуль выполняет эту конвертацию за нас:
4
В результате получим векторные слой, который будем использовать для построения графа.

5

Прежде всего, получим вершины графа, путем извлечения центроидов полигонов:
6
Если бы мы располагали графическими картами в качестве исходного материала, то пришлось бы их отсканировать, затем привязать, затем оцифровать. Это конечно дольше, но мы бы расставили точки более сложным образом. Центроиды полигонов хорошо применять только в случае простых полигонов, на сложных это приводит к погрешности:
8
Впрочем, нас такая точность устраивает, тем более, что от каждого центроида будет идти разводящая сеть. Мы получили вершины графа. Теперь, используя триангуляцию Делоне создадим множество полигонов, каждая вершина которых будет точкой центроида зданий.
7
Преобразуем полигональную триангуляцию в сеть линий. С помощью команды «split» плагина Networks разобьем сеть на отдельные линии. Мы получили граф, достаточный для роутинга. Если нам потребуется кратчайшим образом связать между собой две его вершины, достаточно будет просто использовать модуль RoadGraph:
9
При необходимости, можно добавить каждому ребру графа определенный вес. Полученные полилинии можно экспортировать в виртуальный слой и во внешний шейп.
15

Но у нас немного другая задача — построить сеть с ребрами минимальной длины. Для этого рассчитаем длину каждого ребра, используя встроенный калькулятор QGis:
13
Раскрасим слой ребер по градиенту возрастания длины ребра.
14
Ребер у нас много, поэтому выведем длину каждого из них в качестве подписи:

4

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

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

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

2

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