Автоматическое создание карты метро
Карты метро - очень важный инструмент, когда речь идет о маршрутах общественного транспорта. История карт метро или, в более общем плане, транспортных карт восходит к знаменитой карте метро, созданной Гарри Беком в 1931 году, на которой изображено лондонское метро. В настоящее время они существуют почти во всех крупных городских районах, что позволяет пассажирам быстро получить представление о возможных маршрутах и доступных станциях. Проще говоря, карты метро состоят из станций или остановок, соединенных линиями. Поэтому мы подумали, что они идеально подходят для визуализации с помощью нашей библиотеки диаграмм yFiles. Наша цель состояла в том, чтобы автоматически создавать карты на основе данных, полученных в Интернете, и дорабатывать результаты, используя стили, аналогичные тем, которые используются в официальных картах. Поскольку расчет нового макета карты метро требует значительных ресурсов ЦП, цель не заключалась в создании карт в реальном времени.
Автоматическое вычисление карт метро очень загружает процессор.
Получение данных
Во-первых, нам нужно было получить данные о транспортной линии. Мы решили эту проблему с помощью OpenStreetMap и overpass-turbo, которые используют Overpass-API для запроса данных из OpenStreetMap. Это позволило нам быстро и автоматически запрашивать данные для систем общественного транспорта любого желаемого района, анализировать их и создавать из них диаграмму yFiles. То, что мы получили, по сути, представляет собой диаграмму, которая показывает транспортную систему географически точным образом:
Моделирование и решение проблемы
Наши карты должны удовлетворять нескольким общим правилам визуализации, которые также присущи большинству официальных карт. Линии должны быть только горизонтальными, вертикальными или диагональными под углом 45 градусов. Такое расположение линий называется октилинейным. Карты метро должны сохранять главный географический характер, например относительное расположение станций, но они не обязательно должны быть географически точными. Создание карт метро по этим правилам - тема достаточно хорошо изученная. Наше решение следует подходу Мартина Нёлленбурга («Автоматизированные чертежи карт метро», 2005 г.). Вкратце, этот подход моделирует проблему с помощью смешанной целочисленной линейной программы (MIP). Решение задачи дает координаты станций.
Карты метро сохраняют главный географический характер, но не обязательно должны быть географически точными.
В нашей реализации мы в основном создавали ограничения, предложенные Нёлленбургом, и применяли решатель MIP (через API), чтобы получить решение проблемы. Мы пробовали как lpsolve, так и Оптимизатор CPLEX. Последний дал нам хорошие результаты намного быстрее, чем первый. Затем решение программы MIP интерпретируется и переносится на диаграмму yFiles, созданную на первом шаге, в результате чего получается макет карты метро. Чтобы улучшить время выполнения и улучшить результаты, мы также применили некоторые дополнительные эвристики.
Визуализация результатов
Теперь у нас уже был рисунок карты метро, но мы также хотели, чтобы он выглядел великолепно. Здесь в игру вступил наш мощный API визуализации yFiles, который позволил стилизовать схему карты метро. Для линий мы используем цвета из данных OpenStreetMap, если они доступны. Узлы станций автоматически уменьшаются или увеличиваются в зависимости от количества соседних линий метро.
Маркировать станции метро было непросто, но с yFiles легко.
Последней проблемой была маркировка станций метро (смоделированная как метки узлов). Это довольно сложная проблема сама по себе, потому что на больших картах часто мало места для иногда длинных текстов меток. С помощью универсального алгоритма маркировки (доступного прямо из библиотеки макетов) эта задача стала решаемой. Чтобы результаты были более похожи на карты реального мира, мы постарались разместить надписи как можно более единообразно и автоматически использовали перенос слов, если для надписи мало места.
Глядя на наши окончательные результаты, мы думаем, что карты уже могут не отставать от некоторых официальных карт метро! И очевидно, что результаты нашего автоматического подхода могут стать основой для дизайнеров, которые могут дополнительно настроить карты в некоторых аспектах. Но посмотрите сами: ниже вы найдете некоторые из наших результатов. См. изображения в исходной записи блога здесь. Здесь вы найдете карты в виде высококачественных векторных карт с возможностью масштабирования для следующих городов: Москва, Лондон, Берлин, Сан-Паулу, Санкт-Петербург, Тюбинген, Вашингтон, Шанхай, Токио, Мехико, Париж, Вена, и Нью-Дели!
Что вы думаете? Это что-то, что мы должны включить в качестве алгоритма в yFiles? Полный алгоритм, который мы здесь реализовали, не в настоящее время является частью библиотеки yFiles. Часть маркировки и визуализации включена в yFiles, но часть линейного программирования в настоящее время зависит от стороннего программного обеспечения. Если вы заинтересованы в использовании алгоритма для собственных диаграмм, напишите нам!
