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

Выпуклая оболочка (convex hull) множества точек на плоскости — это наименьший выпуклый многоугольник, который содержит все исходные точки. Геометрически она может быть представлена как «резиновая оболочка», натянутая вокруг набора точек: после отпускания она принимает форму выпуклого контура, охватывающего крайние элементы множества.

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

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

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

Основные свойства выпуклой оболочки:

  • все исходные точки либо лежат на границе, либо внутри оболочки
  • никакая вершина оболочки не может быть «внутренней» точкой исходного множества
  • оболочка минимальна по включению среди всех выпуклых множеств, содержащих исходные точки

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

Алгоритмические основы

Построение выпуклой оболочки — классическая задача вычислительной геометрии. Наиболее распространённые алгоритмы:

  • алгоритм Грэхема (Graham scan) — сортировка точек по полярному углу и построение оболочки через стек
  • алгоритм Джарвиса (gift wrapping) — последовательное «оборачивание» точек
  • алгоритм монотонной цепи (Andrew’s monotone chain) — эффективная сортировка и построение верхней и нижней цепи

Сложность оптимальных решений обычно составляет O(n log n) из-за необходимости сортировки.

Реализация в Turf.js: turf.convex

В библиотеке Turf.js построение выпуклой оболочки реализуется через функцию turf.convex, работающую с GeoJSON-структурами.

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

Основная сигнатура:

turf.convex(featureCollection, options)

Особенности реализации

  • вход строго в формате GeoJSON FeatureCollection
  • поддерживаются Point, MultiPoint и коллекции точек
  • результат возвращается как Polygon (или null, если оболочка не может быть построена)
  • алгоритмически используется оптимизированная реализация выпуклой оболочки

Формат входных данных GeoJSON

Входные данные для turf.convex должны соответствовать спецификации GeoJSON.

Пример структуры:

{
  "type": "FeatureCollection",
  "features": [
    {
      "type": "Feature",
      "geometry": {
        "type": "Point",
        "coordinates": [10.0, 50.0]
      },
      "properties": {}
    },
    {
      "type": "Feature",
      "geometry": {
        "type": "Point",
        "coordinates": [12.0, 52.0]
      },
      "properties": {}
    }
  ]
}

Координаты интерпретируются как [longitude, latitude], что критично для корректных географических вычислений.

Пример построения выпуклой оболочки

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

const points = turf.featureCollection([
  turf.point([0, 0]),
  turf.point([2, 0]),
  turf.point([1, 2]),
  turf.point([1, 1]),
  turf.point([0.5, 0.5])
]);

const hull = turf.convex(points);

console.log(JSON.stringify(hull, null, 2));

Результатом будет GeoJSON Polygon, охватывающий крайние точки множества.

Влияние плотности и распределения точек

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

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

Настройки и параметры

Функция turf.convex поддерживает дополнительные параметры:

turf.convex(points, {
  concavity: 2
});

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

В стандартной версии Turf.js основной параметр — входной набор точек.

Обработка особых случаев

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

Менее трёх точек

  • 0 точек → результат отсутствует
  • 1 точка → оболочка вырождается в точку
  • 2 точки → оболочка представляет собой отрезок

Коллинеарные точки

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

Дубликаты координат

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

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

Основные характеристики производительности turf.convex:

  • временная сложность: O(n log n)
  • память: O(n)
  • узким местом является сортировка координат и построение оболочки

На практике производительность зависит от:

  • количества точек
  • степени их упорядоченности
  • наличия дубликатов
  • географического распределения

При работе с большими наборами данных (десятки тысяч точек) рекомендуется предварительная фильтрация или кластеризация.

Использование в геоинформационных задачах

Выпуклая оболочка в Turf.js применяется для:

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

В задачах пространственного анализа она часто используется как первый шаг перед более точными методами, такими как concave hull или кластеризация DBSCAN.

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

Выпуклая оболочка имеет ряд ограничений:

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

Несмотря на это, вычислительная простота делает её удобной для предварительного анализа и визуализации.

Связь с другими геометрическими операциями Turf.js

В экосистеме Turf.js выпуклая оболочка часто используется вместе с:

  • turf.buffer — расширение границ после построения оболочки
  • turf.dissolve — объединение геометрий перед вычислением оболочки
  • turf.center — определение центра массы точек внутри оболочки
  • turf.bbox — вычисление ограничивающего прямоугольника

Эти операции позволяют формировать комплексные геопространственные пайплайны обработки данных.

Оглавление