Геометрическое представление множества точек в пространстве координат часто требует выделения минимальной выпуклой области, содержащей все элементы набора. Такая область определяется как выпуклый многоугольник, внутри которого лежат все исходные точки, а любые отрезки между точками множества не выходят за его границы. В геоинформационных системах это используется для оценки пространственного охвата объектов, анализа кластеров, построения зон влияния и упрощённого визуального представления распределения данных.
В контексте веб-картографии на основе MapLibre GL JS подобная геометрия применяется при обработке GeoJSON-источников, когда требуется получить обобщённую границу набора точек и отобразить её поверх карты в виде полигонального слоя.
Множество точек на плоскости может иметь сложную форму распределения. При визуализации отдельных объектов на карте их совокупная структура часто неочевидна без дополнительной геометрической обработки. Выпуклая оболочка представляет собой минимальный выпуклый многоугольник, содержащий все точки множества.
Формально оболочка определяется как пересечение всех выпуклых множеств, содержащих исходные точки. Геометрически результат соответствует натянутой резиновой ленте, охватывающей крайние элементы набора.
Такая структура используется для:
Построение выпуклой оболочки относится к классическим задачам вычислительной геометрии. Основные алгоритмы:
Алгоритм Джарвиса (Jarvis March) Итеративно обходит точки, выбирая следующую крайнюю точку по углу поворота. Эффективен при малом числе точек оболочки, но имеет сложность O(nh), где n — количество точек, h — количество точек на оболочке.
Алгоритм Грэхема (Graham Scan) Сортирует точки по полярному углу относительно опорной точки и строит оболочку с использованием стека. Имеет сложность O(n log n).
Quickhull Использует стратегию «разделяй и властвуй», аналогичную quicksort. Практически эффективен на случайных данных и часто применяется в библиотечных реализациях.
В веб-картографии обычно используются готовые реализации, скрывающие внутреннюю сложность вычислений.
В экосистеме MapLibre GL JS часто применяется библиотека Turf.js,
предоставляющая функции геопространственного анализа. Для построения
выпуклой оболочки используется функция turf.convex.
import maplibregl from "maplibre-gl";
import * as turf from "@turf/turf";
const map = new maplibregl.Map({
container: "map",
style: "https://demotiles.maplibre.org/style.json",
center: [30.3, 59.9],
zoom: 10
});
const points = turf.featureCollection([
turf.point([30.25, 59.94]),
turf.point([30.28, 59.92]),
turf.point([30.33, 59.91]),
turf.point([30.31, 59.96]),
turf.point([30.27, 59.97])
]);
const hull = turf.convex(points);Функция принимает FeatureCollection<Point> и
возвращает Polygon, представляющий выпуклую оболочку.
Если набор точек вырожден (например, содержит менее трёх уникальных
координат), результат может быть null, что требует
обработки на уровне логики приложения.
После вычисления геометрии результат добавляется в качестве
GeoJSON-источника. MapLibre GL JS отображает его через слои
fill и line.
map.on("load", () => {
map.addSource("points", {
type: "geojson",
data: points
});
map.addSource("hull", {
type: "geojson",
data: hull
});
map.addLayer({
id: "hull-fill",
type: "fill",
source: "hull",
paint: {
"fill-color": "#3b82f6",
"fill-opacity": 0.25
}
});
map.addLayer({
id: "hull-outline",
type: "line",
source: "hull",
paint: {
"line-color": "#1d4ed8",
"line-width": 2
}
});
map.addLayer({
id: "points-layer",
type: "circle",
source: "points",
paint: {
"circle-radius": 5,
"circle-color": "#ef4444"
}
});
});Структура источников разделяет исходные данные и производную геометрию. Это позволяет независимо обновлять точки и пересчитывать оболочку.
При изменении набора точек требуется пересчёт геометрии и обновление источника.
function updateHull(newFeatures) {
const fc = turf.featureCollection(newFeatures);
const newHull = turf.convex(fc);
const hullSource = map.getSource("hull");
hullSource.setData(newHull);
}При потоковом добавлении данных вычисление оболочки может выполняться периодически, чтобы снизить нагрузку на основной поток исполнения.
Для интерактивных приложений часто применяется стратегия дебаунсинга:
let timeout;
function scheduleUpdate(features) {
clearTimeout(timeout);
timeout = setTimeout(() => {
const fc = turf.featureCollection(features);
const newHull = turf.convex(fc);
if (newHull) {
map.getSource("hull").setData(newHull);
}
}, 200);
}При увеличении количества точек вычисление оболочки становится затратным. Основные факторы производительности:
Оптимизация включает:
cluster: true в GeoJSON
source);MapLibre GL JS поддерживает кластеризацию на уровне источника:
map.addSource("points", {
type: "geojson",
data: points,
cluster: true,
clusterMaxZoom: 14,
clusterRadius: 50
});Кластеры могут использоваться как входные данные для упрощённой оболочки, снижая количество точек до нескольких десятков вместо тысяч.
Выпуклая оболочка не отражает внутреннюю структуру распределения. При наличии вогнутых форм область может значительно превышать фактическую плотность данных.
Типичные особенности:
При обработке GeoJSON важно учитывать корректность координатной системы. MapLibre GL JS использует EPSG:4326 для GeoJSON и EPSG:3857 для рендеринга, преобразование выполняется автоматически.
Интерактивные сценарии часто предполагают добавление точек по клику на карту и немедленное обновление оболочки.
const dynamicPoints = [];
map.on("click", (e) => {
const point = turf.point([e.lngLat.lng, e.lngLat.lat]);
dynamicPoints.push(point);
const fc = turf.featureCollection(dynamicPoints);
const hull = turf.convex(fc);
map.getSource("points").setData(fc);
if (hull) {
map.getSource("hull").setData(hull);
}
});При использовании инструментов рисования, совместимых с MapLibre GL
JS (например, @mapbox/mapbox-gl-draw), источником данных
могут служить редактируемые слои, из которых извлекаются координаты для
пересчёта геометрии.
В прикладных задачах выпуклая оболочка используется для:
В системах аналитики геоданных оболочка часто служит первым уровнем агрегации перед более сложными операциями, такими как построение кластерных полигонов или плотностных изолиний.
Использование выпуклой оболочки в клиентских приложениях связано с рядом ограничений:
В сценариях с высокой частотой обновлений данных предпочтительнее частичная аппроксимация или серверная агрегация.
Геометрия оболочки остаётся базовым инструментом пространственного анализа в MapLibre GL JS, обеспечивая быстрый способ перехода от дискретных точек к непрерывному полигональному представлению, интегрируемому в рендеринговый pipeline веб-карты.