Вогнутая оболочка

Геометрическая основа задачи

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

В Turf.js вогнутая оболочка реализуется через алгоритмы, основанные на построении триангуляции Делоне и последующем отсечении длинных рёбер, что позволяет получить более «естественную» форму области распределения точек.

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

Вогнутая оболочка отличается рядом характеристик:

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

Ключевым фактором является параметр, определяющий допустимую длину рёбер, формирующих контур. Именно он управляет степенью «вогнутости» результата.

Алгоритмическая модель

В Turf.js используется подход, основанный на триангуляции Делоне:

  1. строится триангуляция множества точек;
  2. извлекаются рёбра треугольников;
  3. рёбра, превышающие заданную длину, удаляются;
  4. оставшиеся рёбра формируют граф связности;
  5. из графа восстанавливается замкнутый полигон.

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

Функция concave в Turf.js

Основной инструмент построения вогнутой оболочки — функция turf.concave.

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

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

const options = {
  maxEdge: 2,
  units: "kilometers"
};

const hull = turf.concave(points, options);

Параметры функции

points Набор точек в формате FeatureCollection<Point>. Минимально требуется три точки, однако устойчивые результаты формируются при большем количестве элементов.

options.maxEdge Максимально допустимая длина ребра, включаемого в оболочку. Этот параметр управляет детализацией:

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

options.units Единицы измерения длины. Поддерживаются километры, мили и другие геодезические единицы, используемые в Turf.js.

Поведение при изменении параметра maxEdge

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

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

Эта зависимость делает параметр ключевым инструментом настройки геометрической точности.

Сравнение с выпуклой оболочкой

В Turf.js выпуклая оболочка строится через turf.convex.

const convexHull = turf.convex(points);

Различия между подходами:

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

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

Практическая структура данных

Входные данные для построения оболочки должны соответствовать GeoJSON-структуре:

{
  type: "FeatureCollection",
  features: [
    {
      type: "Feature",
      geometry: {
        type: "Point",
        coordinates: [lng, lat]
      }
    }
  ]
}

Выходная структура представляет собой полигон:

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

Обработка выбросов

Алгоритм чувствителен к точкам, находящимся далеко от основной массы данных. Такие точки могут:

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

Для стабилизации результата применяется предварительная фильтрация данных:

  • удаление статистических выбросов;
  • кластеризация точек;
  • ограничение области анализа.

Геодезические особенности

При работе с координатами в Turf.js важно учитывать, что расстояния вычисляются на сфере. Это приводит к следующим особенностям:

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

Использование параметра units обеспечивает корректное масштабирование расстояний.

Комбинирование с другими операциями Turf.js

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

  • turf.buffer для расширения границ области;
  • turf.booleanPointInPolygon для проверки принадлежности;
  • turf.clusters для предварительной группировки;
  • turf.truncate для нормализации координат.

Пример комбинированного анализа:

const clustered = turf.clustersDbscan(points, 1, { units: "kilometers" });
const clusterPoints = clustered.features.filter(f => f.properties.cluster === 1);

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

Ограничения алгоритма

Существуют системные ограничения, характерные для реализации:

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

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

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

Основной фактор производительности — триангуляция Делоне. Её сложность в среднем составляет O(n log n), однако дополнительные операции фильтрации рёбер увеличивают фактическое время выполнения.

Оптимизации:

  • предварительное уменьшение количества точек;
  • пространственная индексация;
  • разбиение набора на кластеры;
  • ограничение области анализа bounding box-ом.

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

Вогнутая оболочка не является точным геометрическим объектом в строгом математическом смысле. Это приближённая структура, описывающая плотность распределения точек. Она используется как инструмент анализа формы, а не как абсолютная граница.

На практике результат интерпретируется как:

  • зона распространения объектов;
  • контур плотности данных;
  • приближённая географическая область;
  • форма кластера в пространстве координат.
Оглавление