Создание полигонов из точек

Turf.js работает поверх стандарта GeoJSON и предоставляет набор алгоритмов для обработки геометрий, включая построение, преобразование и анализ пространственных объектов. Создание полигонов из набора точек является одной из базовых операций, которая встречается при обработке кластеров координат, восстановлении границ объектов, построении зон покрытия и анализе распределения данных.

Полигон в GeoJSON задаётся как массив координатных колец:

  • первое кольцо — внешний контур
  • последующие кольца — внутренние вырезы (holes)

Формат:

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

Ключевое требование: первый и последний элемент массива координат должны совпадать, замыкая контур.

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

Представление точек в Turf.js

В Turf.js точка представляется как GeoJSON Feature:

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

const pt = turf.point([30.5, 50.5]);

Набор точек формируется через FeatureCollection:

const points = turf.featureCollection([
  turf.point([30.1, 50.1]),
  turf.point([30.2, 50.4]),
  turf.point([30.4, 50.2])
]);

FeatureCollection является основой для большинства алгоритмов, связанных с построением геометрий из множества объектов.

Прямая сборка полигона через turf.polygon

Самый простой способ создания полигона — ручное указание упорядоченных координат:

const polygon = turf.polygon([[
  [30.0, 50.0],
  [30.5, 50.0],
  [30.5, 50.5],
  [30.0, 50.5],
  [30.0, 50.0]
]]);

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

Проблема неупорядоченных точек

Набор точек, полученных из GPS, датчиков или кластеризации, не содержит информации о границе. Прямое соединение в произвольном порядке приводит к самопересечениям:

  • ломается топология
  • образуются «бантики»
  • площадь становится некорректной
  • алгоритмы анализа дают неверные результаты

Поэтому требуется алгоритм построения оболочки.

Построение выпуклой оболочки (Convex Hull)

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

В Turf.js используется функция:

const hull = turf.convex(points);

Принцип работы

Алгоритм игнорирует внутреннюю структуру распределения и строит внешнюю границу:

  • все точки оказываются внутри или на границе
  • результат всегда выпуклый
  • не отражает реальную форму кластера, если он вогнутый

Пример применения

const pts = turf.featureCollection([
  turf.point([0, 0]),
  turf.point([1, 0.2]),
  turf.point([1, 1]),
  turf.point([0.2, 1]),
  turf.point([0.5, 0.5])
]);

const hull = turf.convex(pts);

Полученный полигон будет обводить крайние точки без учёта внутреннего «выреза».

Построение вогнутой оболочки (Concave Hull)

Для более точного отражения формы используется вогнутая оболочка:

const concave = turf.concave(points, {
  maxEdge: 1.5,
  units: "kilometers"
});

Параметр maxEdge

maxEdge определяет максимальную длину ребра:

  • маленькое значение → более детализированная форма
  • большое значение → приближение к convex hull
  • слишком маленькое значение → возможные разрывы полигона

Логика алгоритма

В отличие от convex hull:

  • учитывает плотность точек
  • пытается следовать форме кластера
  • может возвращать null, если данных недостаточно

Практическое поведение

Concave hull часто используется для:

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

Альтернативный подход: alpha shapes (псевдо-вогнутые полигоны)

Хотя Turf.js напрямую не реализует полноценные alpha shapes как математический объект, concave является приближением этого подхода.

Ключевая идея:

  • задаётся радиус «связности»
  • точки соединяются, если расстояние между ними допустимо
  • формируется сложная граница

Подготовка данных перед построением полигона

Перед применением алгоритмов необходимо нормализовать входные данные.

1. Очистка точек

Удаляются:

  • дубликаты координат
  • точки с null/undefined
  • выбросы (если требуется статистическая фильтрация)
const cleaned = turf.featureCollection(
  points.features.filter(p => p.geometry?.coordinates)
);

2. Проверка плотности

Concave hull требует достаточного количества точек:

  • минимум 4–5 для простых форм
  • десятки и сотни для устойчивой геометрии

3. Проекция и единицы измерения

Алгоритмы расстояний в Turf.js работают в геодезических координатах, но параметры (например, maxEdge) зависят от единиц:

  • kilometers
  • miles
  • degrees

Несоответствие единиц приводит к искажению формы.

Построение полигона через кластеризацию

При наличии нескольких групп точек сначала выполняется разбиение на кластеры.

Типовой подход:

  • DBSCAN (внешняя реализация)
  • k-means (для предварительной сегментации)
  • затем convex/concave hull для каждого кластера

Пример цепочки:

const clusterA = turf.featureCollection([...]);
const clusterB = turf.featureCollection([...]);

const polyA = turf.concave(clusterA, { maxEdge: 2, units: "kilometers" });
const polyB = turf.convex(clusterB);

Геометрические ограничения

При построении полигона из точек возникают ограничения:

Самопересечения

Concave hull может создавать:

  • петли
  • разрывы
  • некорректные кольца

В таких случаях требуется постобработка через:

  • упрощение геометрии
  • удаление лишних вершин
  • повторная генерация с другим параметром maxEdge

Ориентация координат

Порядок обхода влияет на:

  • направление полигона (clockwise / counterclockwise)
  • совместимость с GIS-системами

Некоторые системы требуют строгое направление внешнего кольца.

Упрощение полигона после построения

После создания полигона часто применяется упрощение:

const simplified = turf.simplify(polygon, {
  tolerance: 0.01,
  highQuality: true
});

Это уменьшает количество точек без существенной потери формы.

Используется для:

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

Проверка корректности полигона

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

  • наличие замкнутого кольца
  • отсутствие NaN координат
  • отсутствие самопересечений (по возможности)

Пример базовой проверки:

function isValidPolygon(poly) {
  const coords = poly.geometry.coordinates[0];
  const first = coords[0];
  const last = coords[coords.length - 1];

  return first[0] === last[0] && first[1] === last[1];
}

Комбинированный подход построения границы

В практических задачах используется комбинация методов:

  1. построение convex hull как базовой границы
  2. попытка concave hull для уточнения формы
  3. fallback на convex hull при ошибке
  4. последующее упрощение

Логика выбора:

  • мало точек → convex hull
  • средняя плотность → concave hull
  • высокая плотность → concave + smoothing

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

Создание полигонов из точек используется в:

  • анализе GPS-треков
  • построении зон доставки
  • моделировании территорий активности
  • агрегации геоданных IoT-устройств
  • визуализации плотности событий

Каждый сценарий предъявляет разные требования к точности и гладкости границ, что влияет на выбор алгоритма внутри Turf.js.

Оглавление