Clustering стратегии

Google Maps JavaScript API поддерживает отображение больших наборов географических объектов, однако при росте числа маркеров прямая отрисовка приводит к деградации производительности и визуальному шуму. Clustering решает задачу агрегации точек в зависимости от масштаба карты, обеспечивая одновременно читаемость и масштабируемость интерфейса.

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

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

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

В рамках экосистемы Google Maps чаще всего применяется подход:

  • grid-based clustering (сеточная кластеризация)
  • distance-based clustering (по радиусу)

MarkerClusterer как стандартный инструмент

Наиболее распространённая реализация — библиотека @googlemaps/markerclusterer.

Базовый пример:

import { MarkerClusterer } from "@googlemaps/markerclusterer";

const map = new google.maps.Map(document.getElementById("map"), {
  center: { lat: 48.0, lng: 66.9 },
  zoom: 5,
});

const markers = locations.map((location) => {
  return new google.maps.Marker({
    position: location,
  });
});

const clusterer = new MarkerClusterer({
  map,
  markers,
});

Особенность подхода:

  • работает на клиенте
  • не требует серверной логики
  • автоматически пересчитывает кластеры при zoom/pan

Ограничение:

  • при десятках тысяч точек становится узким местом производительность JavaScript-цикла и перерисовки DOM/Canvas

Grid-based стратегия

Grid clustering делит карту на виртуальную сетку. Все маркеры внутри одной ячейки объединяются.

Алгоритмически:

  1. перевод координат в пиксельное пространство
  2. деление на размер клетки (например, 60x60 px)
  3. группировка по индексу клетки

Преимущества:

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

Недостатки:

  • визуальные артефакты на границах сетки
  • не учитывает реальную географическую плотность

Distance-based clustering

Альтернатива grid-подходу — объединение по радиусу.

Логика:

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

Упрощённая модель расстояния:

genui{“math_block_widget_always_prefetch_v2”:{“content”:“d = ”}}

На практике используются геодезические расстояния (Haversine), а не евклидовы координаты.

Преимущества:

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

Недостатки:

  • дороже вычислительно (O(n²) без оптимизаций)

Haversine-расстояние для кластеризации

Для географических координат применяется формула:

a = ^2() + _1 _2 ^2()

и итоговое расстояние:

c = 2 (, )

где:

  • φ — широта
  • λ — долгота

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

Supercluster: высокопроизводительная стратегия

Библиотека supercluster (Mapbox-экосистема) применяется как более быстрый альтернативный алгоритм.

Принцип:

  • использование пространственного индекса (R-tree / KD-tree)
  • предрасчёт кластеров по уровням зума

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

  • O(n log n) при построении
  • O(1)–O(log n) при запросах

Пример:

import Supercluster from "supercluster";

const index = new Supercluster({
  radius: 60,
  maxZoom: 16,
});

index.load(
  points.map(p => ({
    geometry: { coordinates: [p.lng, p.lat] },
  }))
);

const clusters = index.getClusters([-180, -85, 180, 85], 5);

Преимущество:

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

Вектор кластеризации по зум-уровням

Ключевая концепция: кластеризация зависит от zoom level.

Типовая модель:

  • zoom 0–5: крупные кластеры (страны/регионы)
  • zoom 6–10: города
  • zoom 11–15: районы
  • zoom 16+: отдельные точки

Это реализуется через:

  • дискретизацию координат
  • разные радиусы кластеров на каждом уровне

Виртуализация и отрисовка

При больших данных важна не только кластеризация, но и способ рендера.

Подходы:

  • DOM-based markers (медленно при >2000 элементов)
  • Canvas overlay (быстрее)
  • WebGL rendering (максимальная производительность)

Canvas-стратегия:

  • все маркеры рисуются в одном canvas слое
  • перерисовка происходит при событиях map idle

Server-side clustering

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

Схема:

  1. клиент запрашивает bounding box + zoom
  2. сервер выполняет агрегацию
  3. возвращает уже сгруппированные точки

Преимущества:

  • разгрузка клиента
  • возможность использовать сложные геоиндексы (PostGIS, H3)

Недостатки:

  • задержка сети
  • необходимость кеширования

Геопространственные индексы

Для оптимизации используются:

  • H3 (hexagonal grid indexing)
  • QuadTree
  • GeoHash

H3 особенно эффективен:

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

Динамическая кластеризация при взаимодействии карты

Ключевые события:

  • zoom_changed
  • dragend
  • idle

Типовой debounce-паттерн:

let timeout;

map.addListener("bounds_changed", () => {
  clearTimeout(timeout);

  timeout = setTimeout(() => {
    updateClusters();
  }, 150);
});

Это предотвращает:

  • избыточные пересчёты
  • лаги при перетаскивании

Индивидуализация кластеров

Кластеры часто кастомизируются:

  • размер круга зависит от количества точек
  • цвет зависит от плотности
  • текст показывает число маркеров

Пример логики:

const renderer = {
  render: ({ count }) => {
    return new google.maps.Marker({
      label: String(count),
    });
  },
};

Spiderfying как альтернатива кластеру

При малом количестве точек вместо кластера используется “раскладывание” маркеров по окружности.

Принцип:

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

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

  • cluster size ≤ threshold (например, 8–10 элементов)

Гибридные стратегии

В реальных системах применяется комбинация:

  • grid clustering на высоких zoom
  • supercluster на средних
  • direct rendering на максимальном zoom
  • server-side preclustering для больших данных

Такая архитектура обеспечивает:

  • баланс между точностью и скоростью
  • устойчивость к нагрузке
  • предсказуемое поведение UI
Оглавление