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

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

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

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

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

В экосистеме Turf.js основным инструментом для построения пространственных индексов является библиотека rbush, интегрированная через пакет @turf/rbush.

Что такое R-Tree

В основе @turf/rbush лежит структура данных R-Tree.

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

[minX, minY, maxX, maxY]

Например:

[
  37.50,
  55.70,
  37.55,
  55.75
]

Индекс хранит не сами геометрии в плоском списке, а организует их в древовидную структуру.

Упрощённая схема:

Root
 ├─ Node
 │   ├─ Feature A
 │   ├─ Feature B
 │   └─ Feature C
 │
 └─ Node
     ├─ Feature D
     ├─ Feature E
     └─ Feature F

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

Установка

Пакет устанавливается отдельно:

npm install @turf/rbush

Импорт:

import rbush from "@turf/rbush";

Создание индекса

Пустой индекс создаётся следующим образом:

import rbush from "@turf/rbush";

const tree = rbush();

После создания объект готов к загрузке геометрий.

Подготовка данных

Предположим, имеется набор точек:

import { point, featureCollection } from "@turf/helpers";

const points = featureCollection([
    point([37.61, 55.75], { name: "A" }),
    point([37.63, 55.76], { name: "B" }),
    point([37.67, 55.73], { name: "C" })
]);

Каждый объект GeoJSON может быть помещён в индекс.

Массовая загрузка объектов

Наиболее эффективный способ наполнения дерева — использование метода load().

const tree = rbush();

tree.load(points);

После выполнения:

console.log(tree);

внутри дерева будет построена оптимизированная структура поиска.

Для больших коллекций этот способ значительно быстрее последовательной вставки.

Поэлементная вставка

Отдельные объекты можно добавлять через insert().

tree.insert(
    point([37.70, 55.78], {
        name: "D"
    })
);

Можно добавлять новые объекты даже после построения дерева.

Пример:

const feature = point([37.72, 55.74]);

tree.insert(feature);

Поиск объектов в области

Одна из основных задач индекса — быстрый поиск объектов внутри заданного прямоугольника.

Создадим область поиска:

const bbox = [
    37.60,
    55.74,
    37.65,
    55.77
];

Выполним запрос:

const result = tree.search(bbox);

Результат:

{
    type: "FeatureCollection",
    features: [...]
}

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

Поиск по геометрии

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

Например:

import { bboxPolygon } from "@turf/turf";

const area = bboxPolygon([
    37.60,
    55.74,
    37.65,
    55.77
]);

const result = tree.search(area);

Turf автоматически извлечёт ограничивающий прямоугольник и выполнит поиск.

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

Очень распространённый сценарий:

  1. найти объекты через индекс;
  2. выполнить точную геометрическую проверку.

Допустим, необходимо определить полигоны, содержащие точку.

Без индекса:

for (const polygon of polygons.features) {
    if (booleanPointInPolygon(point, polygon)) {
        // найдено
    }
}

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

С индексом:

const candidates = tree.search(pointFeature);

Далее выполняется точная проверка только для найденных кандидатов:

for (const polygon of candidates.features) {
    if (booleanPointInPolygon(pointFeature, polygon)) {
        console.log("Найден полигон");
    }
}

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

Проверка существования пересечения

Метод collides() позволяет быстро определить наличие пересекающихся объектов.

Пример:

const exists = tree.collides([
    37.60,
    55.74,
    37.65,
    55.77
]);

console.log(exists);

Результат:

true

или

false

Полезно в случаях, когда требуется лишь факт наличия пересечения.

Удаление объектов

Удаление выполняется методом remove().

Пусть существует объект:

const feature = point([37.61, 55.75]);

Удаление:

tree.remove(feature);

После этого объект перестаёт участвовать в поиске.

Очистка индекса

Для полного удаления содержимого применяется метод clear().

tree.clear();

Проверка:

console.log(tree.all());

Результат:

[]

Получение всех объектов

Метод all() возвращает всё содержимое дерева.

const features = tree.all();

Результат:

{
    type: "FeatureCollection",
    features: [...]
}

Это удобно для отладки и проверки состояния индекса.

Индексация полигонов

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

Создадим полигоны:

import { polygon } from "@turf/helpers";

const districts = [
    polygon([[
        [37.60, 55.70],
        [37.65, 55.70],
        [37.65, 55.75],
        [37.60, 55.75],
        [37.60, 55.70]
    ]]),
    polygon([[
        [37.66, 55.70],
        [37.71, 55.70],
        [37.71, 55.75],
        [37.66, 55.75],
        [37.66, 55.70]
    ]])
];

Загрузка:

tree.load({
    type: "FeatureCollection",
    features: districts
});

После этого полигоны участвуют в пространственном поиске так же, как точки.

Индексация линий

Линии также поддерживаются.

import { lineString } from "@turf/helpers";

const road = lineString([
    [37.60, 55.75],
    [37.80, 55.80]
]);

tree.insert(road);

Поиск:

const roads = tree.search([
    37.65,
    55.74,
    37.75,
    55.81
]);

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

Использование индекса при поиске ближайших объектов

Предположим, имеется коллекция из 100 000 точек.

Наивный поиск ближайшего объекта:

for (const feature of points.features) {
    // вычисление расстояния
}

Более эффективный вариант:

const nearby = tree.search([
    x - 0.01,
    y - 0.01,
    x + 0.01,
    y + 0.01
]);

После этого вычисление расстояния выполняется только для небольшой группы кандидатов.

Комбинация индекса и функций:

distance()
nearestPoint()

позволяет существенно повысить производительность геоприложений.

Работа с большим набором данных

Рассмотрим коллекцию из 50 000 объектов.

Плохой вариант:

for (const area of searchAreas) {
    for (const feature of features) {
        // проверка пересечения
    }
}

Сложность:

O(n²)

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

const tree = rbush();

tree.load(features);

Для каждой области:

const candidates = tree.search(area);

Сложность снижается до приблизительно:

O(log n)

для большинства операций поиска.

Именно поэтому пространственные индексы являются обязательным компонентом профессиональных GIS-систем.

Экспорт индекса

Содержимое дерева можно сериализовать.

const data = tree.toJSON();

Полученный объект:

{
    children: [...],
    height: 3,
    leaf: false,
    ...
}

Его можно сохранить:

localStorage.setItem(
    "spatialIndex",
    JSON.stringify(data)
);

Восстановление индекса

После загрузки данных:

const data = JSON.parse(
    localStorage.getItem("spatialIndex")
);

Создание дерева:

const tree = rbush();

tree.fromJSON(data);

Повторное построение индекса не потребуется.

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

Практический пример: поиск объектов в видимой области карты

Частая задача картографических приложений — отображение только тех объектов, которые попадают в текущий экран.

Границы карты:

const viewport = [
    west,
    south,
    east,
    north
];

Запрос:

const visibleFeatures =
    tree.search(viewport);

Полученные объекты передаются на рендеринг:

drawFeatures(
    visibleFeatures.features
);

При перемещении карты:

map.on("moveend", () => {
    const bbox = getMapBBox();

    const visible =
        tree.search(bbox);

    render(visible.features);
});

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

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

Необходимо учитывать особенности работы индекса.

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

Например:

Поисковый прямоугольник
      ↓

+------------------+
|                  |
|     Polygon      |
|                  |
+------------------+

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

Поэтому часто применяется двухэтапная схема:

  1. Быстрый поиск кандидатов через rbush.

  2. Точная проверка через:

    • booleanIntersects();
    • booleanContains();
    • booleanWithin();
    • booleanPointInPolygon();
    • другие геометрические функции Turf.js.

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

Рекомендации по использованию

Использовать load() вместо множества insert(), если все данные доступны заранее.

Хранить индекс отдельно от исходной коллекции, чтобы избежать повторного построения.

Применять индекс перед сложными пространственными операциями, особенно при работе с десятками тысяч объектов.

Сериализовать дерево через toJSON(), если построение индекса занимает значительное время.

Комбинировать search() с функциями семейства boolean*, поскольку поиск по BBox является лишь предварительным этапом отбора геометрий.

Создавать индекс для статических данных один раз, а затем переиспользовать его во всём приложении.

Благодаря использованию @turf/rbush Turf.js получает эффективный механизм пространственного поиска, который позволяет масштабировать геоаналитику от небольших коллекций объектов до наборов данных, содержащих сотни тысяч и миллионы геометрий.

Оглавление