Построение параллельных кривых в картографических веб-приложениях

В ходе работы над веб-картой в рамках проекта возникла задача отображения линий метрополитена на карте. Казалось бы, что в этом сложного? По сути — ничего, пока вам не требуется визуализировать различные маршруты, физически проходящие по одному месту. С такой ситуацией мы столкнулись при попытке отобразить линии амстердамского метрополитена.

Первая мысль, которая приходит в голову — это просто продублировать те сегменты, по которым проходит несколько маршрутов, немного сдвинув их друг относительно друга, меняя географические координаты. Однако в результате подобного действия мы получаем линии, которые на мелких масштабах сливаются друг с другом, а на крупных, наоборот, разлетаются в разные стороны, то есть, глядя на подобную карту, невозможно понять, что указанные маршруты физически проходят по одному месту.

Более правильный способ заключается в том, что сдвиг линий относительно друг друга должен задаваться в пикселах с учётом толщины линий. Приблизительный порядок действий должен быть следующим:

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

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

Поскольку в веб-карте проекта «Метро для всех» используется картографическая библиотека Leaflet, то было решено попробовать найти какой-нибудь плагин для построения параллельных кривых. И такой плагин нашёлся — Leaflet.PolylineOffset, пример.

На тестовом наборе данных всё выглядит довольно неплохо. Однако при попытке отрисовать реальные данные (линии метрополитена) возник ряд неприемлемых артефактов (вылеты линий за пределы экрана, исчезновение линий на определённых масштабных уровнях), в связи с чем была принята попытка поиска альтернативного способа нахождения параллельных кривых.

Стоит отметить, что во время написания данной статьи, в код Leaflet.PolylineOffset был добавлен коммит #e2166fa, устраняющий большинство из вышеописанных артефактов. Однако проблемы с отображением сегментов на мелком масштабе остались.

Артефакты при использовании плагина Leaflet.PolylineOffset

Если посмотреть код Leaflet.PolylineOffset, то становится понятно, что это легковесный плагин, реализующий в том числе и всю математику по расчету параллельных кривых. Однако нахождение параллельных кривых — это отнюдь не тривиальная задача, более того, подобной функции нет даже в JTS Topology Suite. Вот что говорит об этом один из основных разработчиков JTS Topology Suite Martin Davis:

Поэтому есть все основания не доверять тому алгоритму, который используется в Leaflet.PolylineOffset.

К сведению: реализация функции нахождения параллельных кривых имеется в библиотеке GEOS, код.

Одна из наиболее известных и функциональных библиотек на JavaScript, предназначенных для выполнения всевозможных пространственных операций над объектами в двумерном пространстве — JSTS Topology Suite. Это JavaScript порт упомянутой выше библиотеки JTS Topology Suite. Однако, как уже отмечалось, в JTS Topology Suite нет функции построения параллельных кривых, поэтому нет его и в JSTS Topology Suite. Можно было бы, конечно, разобраться в алгоритме, реализованном в GEOS и перенести его на JavaScript, используя соответствующие функции JSTS Topology Suite, но мы рассмотрим другой вариант, не столь точный, но как показала практика — вполне достаточный для решения конкретной задачи: визуализировать различные маршруты, физически проходящие по одному месту, без ощутимых артефактов. Не факт, что описанный ниже алгоритм будет приемлемо работать с другим набором данных, но все равно — будет хотя бы какая-то отправная точка.

В JSTS Topology Suite есть возможность построения одностороннего буфера (в ту или иную сторону в зависимости от знака). Пример построения одностороннего буфера (синяя линяя — внешнее кольцо построенного полигона, зелёная — исходная линия):

Односторонний буфер

Также в JSTS Topology Suite есть возможность построения «сырой» параллельной кривой (допускающей самопересечения). Пример построения такой кривой (черная линия — «сырая» кривая, красные точки — её узлы):

«Сырая» параллельная кривая

Итоговую параллельную кривую (голубая) будем набирать из узлов «сырой» кривой, касающихся внешнего кольца одностороннего буфера:

Итоговая параллельная кривая

Код получившейся функции расчета параллельной кривой:

Код всего модуля модуля можно взять на гитхабе. Чтобы склонировать его себе, выполните команду: