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

[kashey]

Почему-то результат выглядит как нарисованный от руки.
На самом деле далеко не всегда и не для всего можно построить вот такие «параллельные» обводки.
И, на самом деле — это stroke, или outline, или «контурный полигон» — функции которые есть почти во всех библиотеках.
Чтобы построить две линии «метро»: надо взять обычную, построить ей контур с нужной шириной(офсет), после чего две части этого контура(левый и правый) отрисовать с нужной толщиной разными цветами.
Это самый сложный момент, потому как начинаются пересечения, наложения и другие некрасивости.
Если не привлекать серьезные формулы то решение очень простое — симплифицировать кривые до нужной точности. Но сохранить гладкость. Для этого можно использовать не стандартный Рамера — Дугласа — Пекера, а банальное округление координат.

[drnextgis]

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

[kashey]

Уже :P

[gbg]

Так это же Эквидистанта

1. Строим в точках заданной кривой нормали
2. Нормируем
3. Домножаем на оступ
4. К точке заданной кривой прибавляем координаты ветора из пункта 3
5. Получили координаты точки на эквидистанте

[kashey]

Маловато:

• Для острых внешних углов надо добавлять точки (те «join», см. www.html5canvastutorials.com/tutorials/html5-canvas-line-joins/)
• Для острых внутренних — как-то нормировать максимальное отклонение от центровой точки(обычно две ширины)

[gbg]

Согласен, я привел «математический» вариант алгоритма для идеализованной кривой. Для реальных данных стоит предварительно провести фильтрацию (а не поискать ли методом наименьших квадратов интерполяционный полином?).

[drnextgis]

Если соединить полученные таким образом точки, то получим результат, названный в статье «сырой» параллельной кривой, то есть линию, содержащую в общем случае множество самопересечений.

[gbg]

Стоит поправку на главную кривизну добавить — если исходная кривая круто поворачивает (радиус кривизны уменьшился с почти бесконечности до разумного значения), и центр этого поворота находится от нее по ту же сторону, что и строящаяся эквидистанта, то вместо всех добавляемых точек эквидистанты (которые и создадут на выходе особенность «ласточкин хвост») нужно добавить ровно одну — центр поворота.

[kashey]

Сделал чуть более нормальную и «гладкую» картинку:

но, к сожалению, до опенсорса мой код не дорос

[Moskus]

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

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

[Zavtramen]

Большое спасибо. Именно сейчас встала похожая задача. Вспомнил что когда-то читал на хабре, и вот нашел!