Карта метро Москвы с расчётом пути +4


AliExpress RU&CIS

В своей предыдущей статье про интерактивную карту метро Москвы я описывал процесс создания векторной карты на svg-движке, сравнивая с канвасным отображением.

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

Сама задача поиска по графу потребовалась по работе для визуализации блок-схем в формате UML, DTD для предоставления заказчику. Алгоритм позволит "оживить" их, превратив в подобие задачи с известными решениями.

Я вспомнил про свою карту метро, представляющую готовый сложный, неориентированный граф, и решил апробировать алгоритм на ней.

Алгоритм состоящий из трёх небольших функций я адаптировал для использования массива с координатами станций, добавив условия:

  • Переходы по вершинам (станциям) назад и вперёд возможны только по линиям одного типа

  • Переходы с линии на линию возможны если у них есть общие станции, являющиеся пересадками (массив inches)

  • Размер массива координат станций пересадок настраивается выбором фильтра всех пересадок (тип inch): прямые, кольцевые, строящиеся, мцк. В дальнейшем добавлю в отдельный фильтр также пересадки Большого кольца и Монорельса.

Эта часть доработки оказалась самой простой, на пару часов. Получив список станций по заданному маршруту, сразу подумал, как отобразить его, на карте, и вот здесь пришлось уже изрядно повозиться.

Во-первых, выяснилось, что карта сильно устарела с момента её создания в 2013 году и пришлось синхронизировать её с текущим вариантом из Википедии.

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

В-третьих, кратчайший путь не всегда соответствовал кратчайшему пути по сути. Для этого пришлось профильтровать массив линий с координатами станций пересадок (тип inch) на прямые, кольцевые и мцк, как уже писал выше. Иначе, если в алгоритм подать полный массив пересадок, то он не прокладывал путь по кольцу, кроме случаев, когда одна из станций находилась на кольце. Потому что поиск пути, дойдя до пересадки на кольцо, уходил вглубь по другим линиям, пересекающимся с кольцом, и по самому кольцу не двигался. Вообще алгоритм поиска должен бы ещё учитывать веса вершин и расстояния между ними (или время в пути). Но я рассматриваю только возможность управления поиском без существенного усложнения алгоритма поиска.

В-четвертых, исходный алгоритм поиска был написан по стандарту ECMA2015 с использованием конструкций языка let, const, Set, которые не позволяли мне посмотреть карту на стареньком iPad 3G. Пришлось переписать код на старый формат с var, function.

Долго не мог подобрать цвет найденного маршрута, чтобы не сливался при наложении с линиями, поскольку линии используют все цвета радуги. В итоге остановился на белом цвете (белая пунктирная линия), который всегда видно.

Надеюсь, статья поможет тем, кто интересуется созданием изображений svg, оффлайн-картами с возможностью редактирования и использования в своих проектах.

Привожу отдельные ссылки на карту метро и проект в github.




Комментарии (14):

  1. sshikov
    /#23003990

    Не работает. Ошибки в js. dbcartasvg.js: 28

    • bopoh13
      /#23004490

      Открылся в 3-х браузерах. Только маршруты далеко не оптимальные: ВДНХ — Университет. Хотя, у «Московский транспорт» хуже получается при пересадке между тремя вокзалами: 9 минут — быстрым шагом, без очередей и с билетом наготове ;)
      Предпочитаю pMetro, и схем там на порядок больше.

      • egaxegax
        /#23004520

        Попробовать разные варианты можно через список Рассчитывать пути. ВДНХ — Университет без Кольцевых пересадок получается по прямой.

      • sshikov
        /#23005496

        dbcartasvg.js:28 Error: attribute d: Unexpected end of attribute. Expected number, "….5333333333333 L".
        Я верю, что у кого-то работает. У автора же работает:) Но я вас чего, обманываю что-ли? Разные окружения, разные плагины. Блокировка рекламы, например.

        • egaxegax
          /#23009192

          Подправил возможную ошибку в координатах 2 линий, оканчивавшихся на L. Сейчас должно работать. Для path это видимо некорректно, хотя в браузерах которых я смотрел (firefox, yandex, safari) ошибок не заметил. Что за браузер использовали и где (телефон, linux, windows)?. IE не в счет.

          • sshikov
            /#23009600 / +1

            chrome. windows. Подтверждаю, починилось.

  2. Bessnov
    /#23004262

    Работа похоже сделана немаленькая.
    Работает. Красиво!

  3. Alexandroppolus
    /#23004352

    Поиск маршрута иногда косячит. Просто наугад выбрал "Охотный Ряд — Бибирево", маршрут получился через Комсомольскую, кольцо и Новослободскую, не оптимально.

    • egaxegax
      /#23004492

      Вообще-то по умолчанию (без вкл/откл опций пересадок в списке Рассчитывать пути) маршрут строится через Б.им.Ленина и Чеховскую. Через кольцо он строится после отключения в списке пересадок Между ветками. Но даже в первом варианте логичней ехать через Тверскую. Результат поиска на самом деле не «кратчайший путь», а «кто первый добрался». Например, от Новокузнецкой до Бибирево маршрут идёт через Тверскую. Также как я выделил кольцевые для большей точности можно выделить ещё узловые пересадки (пересадки на 3 и более станции) в отдельный список и обрабатывать отдельно.

  4. bromzh
    /#23006136

    В-четвертых, исходный алгоритм поиска был написан по стандарту ECMA2015 с использованием конструкций языка let, const, Set, которые не позволяли мне посмотреть карту на стареньком iPad 3G. Пришлось переписать код на старый формат с var, function.

    Почему не взять babel, а ещё лучше typescript для этого? Но вообще, код там сам по себе печальный, всё вперемешку, почти всё в одном огромном god-объекте, а объект в огромном файле. Если кто будет изучать код — пожалуйста, не пишите так.


    Сами маршруты очень странные — от 1905 до курской предлагает аж с двумя пересадками, хотя в действительности достаточно одной.

  5. phikus
    /#23006448

    На телефоне, при зуме двумя пальцами постоянно прыгает куда-то в сторону

    • egaxegax
      /#23009162

      Да, тап двумя пальцами воспринимался как смещение по карте с одновременным зумом. Вроде подправил сейчас работает только зум. Особенность телефона — зум двумя пальцами растягивает все окно браузера не пересчитывая разрешение картинки. Для векторного изображения SVG это незаметно, браузер его пересчитывает под новый размер, только подтормаживать начинает навигация, а вот растягивание растровой канвасной картинки (например канвасной версии карты метро) искажает ее до «пиксельного» вида. Для качественного масштабирования с пересчетом разрешения (через функции transform и scale) картинки в SVG или канвасе я отдельно вывел кнопки ± слева или справа в зависимости от примера.

  6. ducemollari
    /#23009166 / -1

    Зачем вы не любите запятые?

  7. Varowlord4
    /#23009168

    Вроде неплохо, но я не знаю чем это существенно отличается от других приложений по прокладыванию маршруту в метро.