Создание схем общественного транспорта на основе геоданных (проект)

Материал из Wiki - Факультет компьютерных наук
Перейти к: навигация, поиск
Ментор Владимир Клепов
Учебный семестр Осень 2016
Учебный курс 2-й курс
Максимальное количество студентов, выбравших проект: 11


Внимание! Данный проект находится в архиве и реализован не будет.

Что это за проект?

Генератор маршрутных схем создает карты маршрутов общественного транспорта на основе данных из интернета.

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

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

В зависимости от сложности и масштаба схемы используют несколько степеней упрощения:

  • Карта: с буквальной привязкой к географии, подходит для небольших транспортных систем.
  • Схема: подходит для сложных систем (или карт в мелком масштабе). Географию необходимо упростить: объединить несколько близкоидущих линий, привязать направления к регулярной сетке, поменять масштаб в зависимости от плотности остановок (например, на схеме метро Москвы центр гораздо больше, чем на самом деле)
  • Комбинированная схема: ближайшие остановки привязаны к географии, но за пределами района работает как схема. Некоторые линии можно убрать (большой творческий простор).

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

Проект состоит из двух частей. Для начала нужно собрать инфомацию о координатах остановок и маршрутах между ними. Если очень повезет, часть данных может найтись в каком-нибудь АПИ. Иначе нужно будет найти какой-нибудь сайт с картой маршрутов и выгрузить данные оттуда. Эта часть проекта сложно обобщается на разные города и делается один раз. Вторая часть — веб-интерфейс, который принимает на вход данные о маршрутах и остановках и строит схему:

  1. Применяет алгоритмы для упрощения схемы (опционально)
  2. Отрисовать схему (для карт с привязкой -- на карте)
  3. Возможно, скорректировать дизайн (выбрать обозначения остановок, толщину линий и т.д.)
  4. Иногда (например, для обозначения сложных пересадок) может потребоваться ручная коррекция результатов.

Чему вы научитесь?

  • Писать веб-скреперы (программы для сбора данных с веб-страниц без API).
  • Нескольким алгоритмам на планарных графах.
  • Работать с геоданными (API OpenStreetMap, Leaflet).
  • Генерировать векторную графику по данным (очень полезно для анализа данных!)

Какие начальные требования?

Конечно же желание покодить. Желательно иметь опыт работы с веб-стеком: js, HTML, CSS-селекторы (не настаиваю, это не очень сложно).

Какие будут использоваться технологии?

  • Javascript (для интерфейса и отрисовки)
  • Собирать данные можно на чем угодно. Я использую node + cheerio и расскажу о них, но принципы везде одинаковые.
  • Геоданные берутся из API OpenStreetMap.
  • Результат генерируется в SVG через библиотеку общей (как d3) или географической (как Leaflet) визуализации. Можно использовать фронтенд-фреймворк: React очень хорош.

Темы вводных занятий

  • Программирование на js/node.js, работа с npm, использование модуля request (HTTP-запросы), выгрузка данных в JSON.
  • Веб-скрепинг: поиск нужных данных в интернете и автоматизация их сбора.
  • Принципы дизайна транспортных схем.
  • Алгоритмы автоматизации постоения схем.
  • Создание веб-интерфейсов для динамической визуализации схем.

Направления развития

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

Критерии оценки

4-5: Собрать данные о графе остановок и отрисовать карту.

6-7: Реализовать алгоритмы схематизации

8-10: Добавить что-либо из продвинутых возможностей (см. описание)

Ориентировочное расписание занятий

ПН-ПТ: с 15:00 по договоренности.