Добавление расчёта пути к схеме метро Москвы из Википедии
В процессе создания своей схемы метро я использовал SVG-схему из статьи Википедии как визуальный образец. После добавления возможности расчёта и вывода пути к своей схеме стал думать о том, как использовать алгоритм поиска по графу и для других подобных схем. И решил недавно попробовать адаптировать его для схемы метро из Википедии.
Для этого решил адаптировать не алгоритм к схеме, а схему к алгоритму. Поскольку алгоритм BFS использует перебор массивов станций, координат линий и пересадок, то нужно было распарсить схему из Википедии в массивы: для этого я написал различные варианты CSS-селекторов.
Приведу сложности, возникшие при разборе схемы, в виде списка:
Координаты станций в схеме заданы в атрибутах x, y и в transform атрибуте в translate. При этом translate может повторяться и сочетаться с командами rotate и scale. Например, для пересадочной станции «Октябрьская» transform выглядит так translate(688,583)rotate(103.1558)translate(260)rotate(-103.1558). То есть для получения абсолютных координат объекта станции (тег use) нужно последовательно сместить и повернуть координаты дважды. Пробуя разные варианты, я оформил их в две функции topoints и trpoint для парсинга и вычисления координаты отдельно.
Список полученных станций нужно было отсортировать в последовательности их нахождения на линиях для правильного прохода по ним алгоритмом поиска пути. Для этого массив станций пересортировал и добавил в него станции для замыкания колец: радиального, БКЛ и МЦК. В БКЛ также добавил станции, отсутствующие на схеме, которые перекрывает Некрасовская линия.
Массив с координатами станций с внешними пересадками на МЦК, Монорельс и Некрасовскую линию составил вручную, поскольку на схеме они никак не выделены, а их координаты не всегда точно совпадают с началом и концом маршрута пересадки, по которому их можно вычислить. Поскольку их всего 24, список забил вручную, считывания станции по id.
Координаты линий на схеме заданы в самых разных вариантах, используя абсолютные и относительные команды L, l, Q, q и укороченные команды с одной координатой H, h, V, v. Для составления списка линий (тег path) нужно было получить абсолютные координаты точек линий. Задача непростая. Попробовал использовать разные библиотеки с GitHub для вычисления абсолютных координат объектов SVG. В итоге остановилcя на проекте fontello/svgpath и включил библиотеку в код. Метод SvgPath (M 700,936 H 501 q -14,0 -24,10 L 221,1202 и стало [["M",700,936],["L",501,936],["Q",487,936,477,946],["L",221,1202]]]. Такой массив удобен для поиска точек пути.
Отрисовка найденного пути с учётом изгибов и направления движения. Линии на схеме не всегда отрисованы последовательно, например, Филёвская и БКЛ линии имеют ответвления в сторону станции «Деловой центр» и найденный маршрут разрывался в этом месте. Плавные изгибы найденного пути неправильно замыкались из-за смены местами начала и конца отрезка перед началом дуги Q или A при отрисовке пути снизу вверх или сверху вниз, например, маршрут «Чертановская» — «Кантемировская» и «Кантемировская» — «Чертановская» oдинаковый, но рисуется по-разному. Чтобы убрать отличия создал списки blacklist и replacelist для удаления лишних и замены неправильных точек пути.
Для навигации по схеме: перемещение, увеличение, уменьшение, — использую свою библиотеку dbcartajs. В целом задача оказалась сложнее, чем себе её представлял, но не хотел бросать наработки и постарался доделать до приемлемого вида.
Управление: Выделяются станции по клику, сбрасывается маршрут по двойному клику. Пересадки управляются списком в правом верхнем углу.
Плюсы этой схемы:
Не нужно дорисовывать схему самому после открытия новых линий и станций. Это делают авторы Википедии. А моём примере будет грузиться уже новая схема.
Недоделки в этой схеме:
Нет проверки прохода по строящимся станциям. Например, маршрут «Чертановская» — «Кантемировская» построится через строящуюся «Варшавскую», а должен через кольцевую «Серпуховскую». Или от «Делового центра» до «Таганской» путь пройдёт по несуществующим станциям «Волхонка» и «Плющиха». Планирую потом доработать алгоритм.
Код примера получился довольно громоздким с большим количеством «ручных» вставок: выравнивание путей с помощью заполнения списокв координат blacklist и replacelist, пересортировка списка станций после парсинга. После изменения схемы процесс нужно будет повторить.
В целом, кого интересует тема с SVG и парсингом можете протестировать ещё один поиск по схеме метро Москвы. Неплохо работает и на смартфоне.
