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

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



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

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

  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. Никаких вылетов и исчезновений линий не наблюдается.


Результат
Поделиться публикацией
Комментарии 11
    0
    Почему-то результат выглядит как нарисованный от руки.
    На самом деле далеко не всегда и не для всего можно построить вот такие «параллельные» обводки.
    И, на самом деле — это stroke, или outline, или «контурный полигон» — функции которые есть почти во всех библиотеках.
    Чтобы построить две линии «метро»: надо взять обычную, построить ей контур с нужной шириной(офсет), после чего две части этого контура(левый и правый) отрисовать с нужной толщиной разными цветами.
    Это самый сложный момент, потому как начинаются пересечения, наложения и другие некрасивости.
    Если не привлекать серьезные формулы то решение очень простое — симплифицировать кривые до нужной точности. Но сохранить гладкость. Для этого можно использовать не стандартный Рамера — Дугласа — Пекера, а банальное округление координат.
      0
      Насчёт того, что от руки — можете склонировать репозиторий, там есть работающий пример, координаты линий взяты из OpenStreetMap.
    +2
    Так это же Эквидистанта
    1. Строим в точках заданной кривой нормали
    2. Нормируем
    3. Домножаем на оступ
    4. К точке заданной кривой прибавляем координаты ветора из пункта 3
    5. Получили координаты точки на эквидистанте
      +1
      Маловато:
      • Для острых внешних углов надо добавлять точки (те «join», см. www.html5canvastutorials.com/tutorials/html5-canvas-line-joins/)
      • Для острых внутренних — как-то нормировать максимальное отклонение от центровой точки(обычно две ширины)
        +1
        Согласен, я привел «математический» вариант алгоритма для идеализованной кривой. Для реальных данных стоит предварительно провести фильтрацию (а не поискать ли методом наименьших квадратов интерполяционный полином?).
        0
        Если соединить полученные таким образом точки, то получим результат, названный в статье «сырой» параллельной кривой, то есть линию, содержащую в общем случае множество самопересечений.
          0
          Стоит поправку на главную кривизну добавить — если исходная кривая круто поворачивает (радиус кривизны уменьшился с почти бесконечности до разумного значения), и центр этого поворота находится от нее по ту же сторону, что и строящаяся эквидистанта, то вместо всех добавляемых точек эквидистанты (которые и создадут на выходе особенность «ласточкин хвост») нужно добавить ровно одну — центр поворота.
        +2
        Сделал чуть более нормальную и «гладкую» картинку:

        но, к сожалению, до опенсорса мой код не дорос
          0
          Точно такая же задача стоит перед системами Computer-Aided Manufacturing при генерации программ для фрезерных станков с ЧПУ (CNC). Там требуется огибать внешние углы детали дугой, чей радиус равен радиусу выбранного режущего инструмента (фрезы), а во внутренних углах необходимо добавлять вписанную дугу с минимально возможным радиусом, для которой обе прямые части траектории в окрестности угла являются касательными.

          Но самое забавное, что хотя CAM-софт с этим прекрасно справляется, встроенные в станки блоки управления самостоятельно эту задачу решают весьма упрощенным методом, от чего попытка использовать автоматическую компенсацию радиуса (то есть вычисляемую самим станком) приводит к генерации траектории, как на картинке с «сырой кривой», что вызывает коллизию, и программа не может быть выполнена.
            0
            Большое спасибо. Именно сейчас встала похожая задача. Вспомнил что когда-то читал на хабре, и вот нашел!

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

            Самое читаемое