Pull to refresh

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

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



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

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

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

В случае, если по одному и тому же месту проходит более чем 2 маршрута, то имеет смысл использовать отрицательные приращения наряду с положительными для равномерного расположения сегментов в обе стороны относительно реального маршрута.

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

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

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

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


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

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

In fact my original goal was to develop an offset line algorithm, but it turned out to be quite tricky to implement. I'm still thinking about doing offset lines, though.


Поэтому есть все основания не доверять тому алгоритму, который используется в 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 есть возможность построения «сырой» параллельной кривой (допускающей самопересечения). Пример построения такой кривой (черная линия — «сырая» кривая, красные точки — её узлы):


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

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


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

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

offsetPoints: function(pts, offset) {
    var offsetPolyline,
        ls = new jsts.geom.LineString(this.pointsToJSTSCoordinates(pts));

    if (offset != 0) {
      // Parameters which describe how a buffer should be constructed
      var bufferParameters = new jsts.operation.buffer.BufferParameters();

      // Sets whether the computed buffer should be single-sided
      bufferParameters.setSingleSided(true);

      var precisionModel = new jsts.geom.PrecisionModel();
      var offsetCurveBuilder = new jsts.operation.buffer.OffsetCurveBuilder(precisionModel, bufferParameters);

      var offsetCurve = offsetCurveBuilder.getOffsetCurve(ls.points, offset);
      var offsetBuffer = jsts.operation.buffer.BufferOp.bufferOp2(ls, offset, bufferParameters);

      var offsetPointsList = [];
      for (var i=0, l=offsetCurve.length; i<l; i++) {
        var offsetCurveNode = new jsts.geom.Point(offsetCurve[i]);
        if (offsetBuffer.touches(offsetCurveNode)) {
          var offsetPoint = offsetCurve[i];
          if (!(isNaN(offsetPoint.x) || isNaN(offsetPoint.y))) {
            offsetPointsList.push(offsetPoint);
          }
        }
      }

      offsetPolyline = offsetPointsList;

    } else {
      offsetPolyline = ls.points;
    }

    return this.JSTSCoordinatesToPoints(offsetPolyline);
  }


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

git clone --recursive git@github.com:drnextgis/Leaflet.PolylineOffset.git


Там же есть и примеры использования.

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


Результат
Tags:
Hubs:
+31
Comments 11
Comments Comments 11

Articles