В процессе создания своей схемы метро я использовал 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(<Path>).abs() возвращает массив segments, содержащий точки с абсолютными координатами, например, было 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 и парсингом можете протестировать ещё один поиск по схеме метро Москвы. Неплохо работает и на смартфоне.