RBush для оптимизации

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

Основой ускорения служит пространственный индекс. В экосистеме JavaScript де-факто стандартом для 2D-индексации является RBush — реализация R-tree с оптимизированной вставкой и быстрым поиском по bounding box.

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

OpenLayers внутри использует геометрические операции через ol/extent и ol/geom. Однако без индекса каждая операция выбора или отрисовки вынуждена проверять все фичи.

R-tree решает проблему за счёт иерархического разбиения пространства:

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

Сложность поиска уменьшается до порядка (O(n)) в среднем случае.

RBush: структура и принцип работы

RBush строит сбалансированное дерево, где каждый узел хранит bounding box:

[minX, minY, maxX, maxY]

Каждый объект либо является листом, либо агрегатом других узлов.

Ключевые операции:

  • ins ert(item) — добавление элемента
  • search(bbox) — поиск пересечений
  • remove(item) — удаление
  • clear() — очистка индекса

Особенность реализации — bulk-loading, позволяющая быстро построить индекс из массива без поэлементной вставки.

Интеграция RBush с OpenLayers через кастомный индекс

В OpenLayers векторные источники позволяют подключать собственные стратегии индексации через ol/source/Vector и обработку геометрий.

Типовая схема:

  1. Извлечение extent у каждой геометрии
  2. Построение RBush-индекса
  3. Использование индекса при выборке объектов

Пример базовой интеграции:

import RBush from 'rbush';
import VectorSource from 'ol/source/Vector';

const index = new RBush();

function featureToItem(feature) {
  const extent = feature.getGeometry().getExtent();
  return {
    minX: extent[0],
    minY: extent[1],
    maxX: extent[2],
    maxY: extent[3],
    feature
  };
}

const source = new VectorSource({
  features: []
});

function rebuildIndex(features) {
  index.clear();
  const items = features.map(featureToItem);
  index.load(items);
}

Ускорение hit-detection и select interactions

Интерактивные операции (click, hover) в больших слоях являются наиболее чувствительными к производительности.

Без индекса:

  • перебор всех feature
  • проверка containsCoordinate для каждой геометрии

С RBush:

  • сначала поиск кандидатов по bbox
  • затем точная проверка только для найденных элементов
function getFeaturesAtCoordinate(coord) {
  const searchExtent = [
    coord[0], coord[1],
    coord[0], coord[1]
  ];

  const candidates = index.search({
    minX: searchExtent[0],
    minY: searchExtent[1],
    maxX: searchExtent[2],
    maxY: searchExtent[3]
  });

  return candidates
    .map(c => c.feature)
    .filter(f => f.getGeometry().intersectsCoordinate(coord));
}

Такой подход радикально снижает число геометрических проверок.

Индексация при динамических данных

При изменении данных ключевой проблемой становится синхронизация индекса.

Стратегии:

Полная перестройка

Подходит для:

  • статических данных
  • пакетных обновлений

Минус — дорогостоящая операция при больших наборах.

Инкрементальные обновления

Используется при потоковых данных:

function addFeature(feature) {
  const item = featureToItem(feature);
  index.insert(item);
}

function removeFeature(item) {
  index.remove(item);
}

Важно поддерживать ссылку на объект RBush-узла для удаления.

Гибридный подход

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

Оптимизация кластеризации через RBush

Кластеризация точечных данных часто реализуется через пространственные индексы.

Алгоритм:

  1. поиск соседей через bbox
  2. агрегация в кластер
  3. рекурсивное объединение
function cluster(extent) {
  const neighbors = index.search(extent);

  const clusterCenter = neighbors.reduce(
    (acc, item) => {
      const c = item.feature.getGeometry().getCoordinates();
      acc.x += c[0];
      acc.y += c[1];
      return acc;
    },
    { x: 0, y: 0 }
  );

  clusterCenter.x /= neighbors.length;
  clusterCenter.y /= neighbors.length;

  return {
    center: [clusterCenter.x, clusterCenter.y],
    size: neighbors.length
  };
}

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

Производительность при большом количестве объектов

Ключевые факторы эффективности RBush:

Балансировка дерева

RBush использует оптимизированный bulk-loading алгоритм, минимизирующий перекос структуры.

Минимизация bbox

Чем точнее bounding box соответствует геометрии, тем меньше ложных попаданий.

Снижение числа вставок

Частые вставки ухудшают баланс дерева. Приоритет отдаётся пакетной загрузке.

Пространственное разрежение

Для плотных данных имеет смысл:

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

Использование RBush в кастомных источниках OpenLayers

При создании собственного ol/source/Source индекс может стать внутренним механизмом хранения:

class IndexedSource {
  constructor() {
    this.index = new RBush();
    this.features = [];
  }

  addFeature(feature) {
    this.features.push(feature);
    this.index.insert(featureToItem(feature));
  }

  getInExtent(extent) {
    return this.index.search({
      minX: extent[0],
      minY: extent[1],
      maxX: extent[2],
      maxY: extent[3]
    }).map(i => i.feature);
  }
}

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

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

RBush эффективен в сценариях:

  • поиск по bbox
  • статические или полу-динамические наборы
  • 2D геометрия без сложных топологических запросов

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

  • отсутствие поддержки сложных пространственных запросов (within, intersects polygon)
  • необходимость точной пост-фильтрации
  • деградация при частых мелких изменениях

Сравнение с альтернативами

Подход Производительность Гибкость
линейный поиск низкая высокая
RBush высокая средняя
GeoJSON full scan очень низкая высокая
серверный индекс максимальная зависит от API

RBush занимает промежуточную позицию между простотой и скоростью, оставаясь полностью клиентским решением.

Практическая модель применения в OpenLayers

Типичная архитектура:

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

Схема потока:

  1. изменение данных → обновление RBush
  2. изменение вида карты → extent запрос
  3. выборка кандидатов из RBush
  4. фильтрация геометрией
  5. рендер или hit-test

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

Оглавление