Привязка точек к линиям

Turf.js предоставляет набор геопространственных алгоритмов, позволяющих выполнять операции над точками, линиями и полигонами в географических координатах. Привязка точек к линиям (point snapping / map matching упрощённого уровня) — одна из ключевых задач при обработке GPS-треков, построении маршрутов и анализе перемещений.

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

Линия в GeoJSON представляется как LineString — последовательность координат:

{
  "type": "LineString",
  "coordinates": [
    [lng1, lat1],
    [lng2, lat2],
    [lng3, lat3]
  ]
}

Точка:

{
  "type": "Point",
  "coordinates": [lng, lat]
}

Задача заключается в том, чтобы:

  • найти ближайший отрезок линии;
  • вычислить перпендикулярную проекцию точки на этот отрезок;
  • вернуть координаты точки на линии;
  • дополнительно получить расстояние и параметр вдоль линии.

Базовая операция: ближайшая точка на линии

Основной инструмент для решения задачи — nearestPointOnLine.

import * as turf from "@turf/turf";

const point = turf.point([37.6156, 55.7522]);
const line = turf.lineString([
  [37.60, 55.75],
  [37.62, 55.76],
  [37.65, 55.74]
]);

const snapped = turf.nearestPointOnLine(line, point);

Результат содержит расширенную структуру:

{
  type: "Feature",
  geometry: {
    type: "Point",
    coordinates: [...]
  },
  properties: {
    index: 1,
    dist: 0.42,
    location: 12.7
  }
}

Интерпретация результата

  • geometry.coordinates — координаты точки, «прилипшей» к линии
  • properties.index — индекс сегмента линии, на котором найдена проекция
  • properties.dist — расстояние от исходной точки до линии
  • properties.location — положение вдоль линии в единицах её длины

Расстояние до линии как основа фильтрации

Перед выполнением полноценного снаппинга часто вычисляется расстояние до линии:

const dist = turf.pointToLineDistance(point, line, { units: "kilometers" });

Функция возвращает минимальное расстояние от точки до всей полилинии, не вычисляя саму проекцию.

Использование:

  • отсечение точек, слишком удалённых от маршрута
  • предварительная фильтрация GPS-шума
  • оценка качества трека

Практическое применение порога

const MAX_DISTANCE = 0.2; // км

if (dist < MAX_DISTANCE) {
  const snapped = turf.nearestPointOnLine(line, point);
}

Алгоритм привязки точки к линии

Полный процесс привязки обычно включает несколько шагов:

1. Предварительная проверка расстояния

const dist = turf.pointToLineDistance(point, line, { units: "meters" });
if (dist > 100) return null;

2. Поиск ближайшего сегмента

Turf.js внутри nearestPointOnLine перебирает сегменты LineString и вычисляет минимальное расстояние до каждого.

3. Проекция точки на сегмент

Для сегмента A-B вычисляется ортогональная проекция точки P:

  • вектор AB
  • вектор AP
  • скалярное произведение для параметра t

Если:

  • t < 0 — ближе к A
  • t > 1 — ближе к B
  • иначе точка лежит внутри отрезка

4. Формирование итоговой точки

Результат — координата, вычисленная как:

P' = A + t * (B - A)

Привязка с учётом сегментов и индексов

Для сложных линий важно учитывать индекс сегмента:

const snapped = turf.nearestPointOnLine(line, point);

console.log(snapped.properties.index);

Это позволяет:

  • разбивать маршрут на участки
  • строить прогресс движения
  • анализировать отклонения по сегментам

Работа с MultiLineString

Для мультилиний используется та же функция:

const multiLine = turf.multiLineString([
  [[0, 0], [1, 1]],
  [[1, 1], [2, 2]]
]);

const snapped = turf.nearestPointOnLine(multiLine, point);

Особенность:

  • поиск выполняется по всем линиям
  • возвращается глобально ближайшая проекция

Использование location для измерения вдоль линии

Поле location — ключевой элемент для линейной привязки:

snapped.properties.location

Оно позволяет:

  • вычислять прогресс маршрута
  • синхронизировать GPS и дорожную геометрию
  • строить параметрические модели движения

Пример интерполяции:

const progress = snapped.properties.location / turf.length(line, { units: "kilometers" });

Привязка нескольких точек (GPS трек)

При обработке трека алгоритм применяется последовательно:

const snappedTrack = points.map(p =>
  turf.nearestPointOnLine(line, p)
);

Дополнительно применяются оптимизации:

  • ограничение поиска соседними сегментами
  • фильтрация выбросов
  • сглаживание координат

Сглаживание результата

Сырые GPS-данные дают «дрожание» точки на линии. Для стабилизации применяются методы:

Усреднение по окну

function smooth(points, windowSize = 3) {
  return points.map((p, i, arr) => {
    const slice = arr.slice(Math.max(0, i - windowSize), i + windowSize);
    const avgLng = slice.reduce((s, x) => s + x.geometry.coordinates[0], 0) / slice.length;
    const avgLat = slice.reduce((s, x) => s + x.geometry.coordinates[1], 0) / slice.length;
    return turf.point([avgLng, avgLat]);
  });
}

Ограничение прыжков

Если расстояние между соседними снапами слишком велико, точка считается выбросом.

Ошибки и крайние случаи

1. Пустая или вырожденная линия

Если линия состоит из одной точки, проекция невозможна.

2. Резкие углы

На острых углах возможны скачки индекса сегмента.

3. Геодезическая погрешность

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

4. Самопересекающиеся линии

При пересечениях возможен выбор «неожиданного» сегмента как ближайшего.

Оптимизация производительности

При большом количестве точек (десятки тысяч) важно учитывать сложность:

  • базовый алгоритм: O(n * m)
  • n — точки
  • m — сегменты линии

Методы ускорения:

Предварительное разбиение линии

Разделение на чанки снижает количество проверок.

Пространственная индексация

Использование R-tree или grid-индекса вне Turf.js.

Кэширование результатов

Если точки идут последовательно вдоль маршрута:

let lastIndex = 0;

function fastSnap(point, line) {
  return turf.nearestPointOnLine(line, point, { units: "meters", closestPoint: true });
}

(в реальных системах дополнительно ограничивают поиск соседними сегментами вручную)

Применение в реальных сценариях

GPS-трекинг

  • привязка координат пользователя к дороге
  • устранение шумов навигации

Map matching (упрощённый уровень)

  • сопоставление трека с дорожной сетью
  • восстановление маршрута движения

Аналитика перемещений

  • вычисление пройденных участков
  • анализ остановок и отклонений

Игровые и симуляционные системы

  • привязка объектов к кривым траекториям
  • движение по заданным маршрутам

Комбинация с другими функциями

С длиной линии

const total = turf.length(line, { units: "kilometers" });

С обрезкой линии

const segment = turf.lineSlice(start, snapped.geometry, line);

С буфером вокруг линии

const buffer = turf.buffer(line, 0.1, { units: "kilometers" });

Поведение при разных единицах измерения

Функции поддерживают:

  • meters
  • kilometers
  • miles
  • degrees

Выбор единиц влияет на:

  • интерпретацию расстояний
  • точность вычислений
  • масштаб применимости алгоритма

Особенности численной устойчивости

При вычислениях на сфере возникают:

  • ошибки округления
  • различия при пересечении меридианов
  • нестабильность на полюсах

Turf.js компенсирует часть этих проблем использованием геодезических формул, но при высокоточных задачах требуется дополнительная фильтрация и проверка результатов.

Оглавление