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

Назначение пространственной индексации

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

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

Ключевая идея заключается в переходе от линейного перебора:

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

Основные структуры пространственных индексов

R-tree (R-дерево)

R-tree — базовая структура, используемая для индексирования прямоугольных областей (bounding box).

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

[minX, minY, maxX, maxY]

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

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

RBush

В OpenLayers применяется реализация R-tree на базе библиотеки RBush.

RBush оптимизирован под:

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

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

QuadTree (в отдельных сценариях)

Хотя основная реализация базируется на R-tree, концептуально иногда используется разбиение пространства на квадранты:

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

QuadTree чаще применяется в пользовательских оптимизациях или кастомных источниках.

Пространственный индекс в Vector Source

Векторный источник OpenLayers использует пространственный индекс для хранения feature-объектов.

Ключевая структура:

  • feature → geometry → extent → индекс

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

  1. вычисляется extent геометрии
  2. объект вставляется в RBush
  3. индекс обновляется для быстрых запросов

Пример внутренней логики

Упрощённая схема добавления объекта:

const extent = geometry.getExtent();

index.insert({
  minX: extent[0],
  minY: extent[1],
  maxX: extent[2],
  maxY: extent[3],
  feature: feature
});

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

При каждом рендере карты происходит выборка объектов, попадающих в текущий экстент видимой области.

Процесс включает:

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

Пример запроса по экстенту

const extent = map.getView().calculateExtent(map.getSize());

const features = vectorSource.getFeaturesInExtent(extent);

Внутри метода происходит обращение к RBush:

  • поиск пересечений bbox
  • возврат только потенциально видимых объектов

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

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

O(n)

С использованием R-tree:

O(log n + k)

где:

  • n — общее количество объектов
  • k — количество найденных элементов

На практике это критично при:

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

Индексация геометрий разных типов

Точки

Для точечных объектов bounding box вырождается в точку:

[minX, minY, maxX, maxY] = [x, y, x, y]

Индекс работает максимально эффективно.

Линии

Для линий используется общий bounding box всех вершин.

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

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

Полигон

Для полигонов используется внешний контур:

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

Пространственный индекс и кластеры

При использовании кластеризации (Cluster Source) индекс применяется дважды:

  1. группировка точек в кластеры
  2. индексация уже кластеров как новых объектов

Схема:

  • точки → индекс → ближайшие соседи
  • кластеры → индекс → отображение на карте

Обновление индекса

При изменении геометрии объекта индекс требует синхронизации:

  • удаление старого bbox
  • вставка нового bbox

Типичный сценарий:

feature.setGeometry(newGeometry);
vectorSource.changed();

Внутри происходит:

  • пересчёт extent
  • обновление RBush
  • перерасчёт видимых объектов

Lazy-индексация и оптимизации

OpenLayers применяет отложенную индексацию:

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

Это снижает стоимость операций при загрузке больших GeoJSON.

Связь с разрешением и тайловой системой

Пространственный индекс взаимодействует с тайловой логикой:

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

TileGrid ограничивает область поиска, уменьшая нагрузку на индекс:

  • сначала выбираются тайлы
  • затем внутри тайлов выполняется spatial query

Выборка объектов при клике

При обработке событий pointer используется индекс:

  1. координата клика преобразуется в extent (точечный bbox)
  2. выполняется поиск кандидатов
  3. проводится точная проверка геометрии

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

const pixel = map.getEventPixel(event);
const coord = map.getCoordinateFromPixel(pixel);

const extent = [
  coord[0], coord[1],
  coord[0], coord[1]
];

const features = vectorSource.getFeaturesInExtent(extent);

Ограничения пространственной индексации

Несмотря на высокую эффективность, индекс имеет особенности:

  • bbox-представление не учитывает сложную геометрию
  • возможны ложные срабатывания (false positives)
  • точная проверка всегда выполняется дополнительно

Влияние на рендеринг WebGL и Canvas

В Canvas-рендерере индекс используется для:

  • отбора объектов для отрисовки
  • исключения невидимых элементов
  • оптимизации label decluttering

В WebGL:

  • индекс уменьшает набор передаваемых в GPU данных
  • снижает стоимость пересчёта буферов

Динамические данные и потоковые источники

При работе с потоковыми данными (например, real-time геоданные):

  • индекс обновляется непрерывно
  • используется инкрементальная вставка
  • удаление устаревших объектов выполняется по TTL-логике

Геометрические операции поверх индекса

После первичного отбора через R-tree применяются точные операции:

  • intersects
  • contains
  • within
  • distance

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

Масштабирование и большие наборы данных

При работе с сотнями тысяч объектов эффективность индекса проявляется особенно сильно:

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

Структура R-tree обеспечивает логарифмическую деградацию производительности, а не линейную.

Оглавление