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

В настоящее время реализован только один пространственный индекс - R-tree.

R-tree

R-дерево - это структура данных деревьев, используемая для пространственного поиска. Он был предложен Антонином Гуттманом в 1984 году ^[1] как расширение B-дерева для многомерных данных. Он может использоваться для хранения точек или объемных данных для выполнения пространственного запроса. Этот запрос может, например, вернуть объекты, которые находятся внутри какой-либо области или близки к какой-то точке в пространстве ^[2]. Можно вставить новые объекты или удалить уже сохраненные.

Структура R-дерево представлена на изображении ниже. Каждый узел R-дерева хранит коробку, описывающую пространство, занимаемое его детскими узлами. В нижней части структуры есть листовые ноды, которые содержат значения (геометрические изображения объектов).

R-tree - это самобалансированная структура данных. Ключевой частью алгоритма балансирования является алгоритм разделения узлов ^{[3] [4]}. Каждый алгоритм производит различные разделения, поэтому внутренняя структура дерева может быть различной для каждого из них. В целом, более сложные алгоритмы лучше анализируют элементы и производят меньше перекрывающихся узлов. В процессе поиска меньше узлов должно быть пройдено, чтобы найти нужные объекты. С другой стороны, более сложный анализ занимает больше времени. В целом более быстрая вставка приведет к более медленному поиску и наоборот. Эффективность R-дерева зависит от алгоритма балансировки, параметров и данных, вставленных в контейнер.

Кроме того, существуют алгоритмы создания R-дерева, содержащего некоторые, количество объектов. Этот метод называется массовой загрузкой и выполняется с использованием алгоритма упаковки ^{[5] [6]}. Этот метод быстрее и приводит к появлению R-деревьев с лучшей внутренней структурой. Это означает, что производительность запроса увеличивается.

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

Конфигурация машины, используемой для тестирования, была: Intel(R) Core(TM) i7 870 @ 2.93GHz, 8GB RAM, MS Windows 7 x64. Код был составлен с оптимизацией скорости (O2).

Производительность R-дерева для различных значений параметра Max и Min=0,5*Max представлена в таблице ниже. В двух верхних фигурах вы можете увидеть производительность R-дерева, хранящего случайные, относительно небольшие, не перекрывающиеся, 2d коробки. В нижних производительность R-дерева также хранит случайные, 2d-боксы, но на этот раз довольно большие и, возможно, перекрывающиеся. Как вы можете видеть, производительность R-дерево отличается в обоих случаях.

Implementation details

Ключевые особенности этой реализации R-дерево:

Dependencies

R-дерево зависит от Boost. Контейнер, Boost.Core, Boost.Move, Boost.MPL, Boost. Ранж, буст.

Contributors

Пространственный индекс был первоначально запущен Federico J. Fernandez во время программы Google Summer of Code 2008, наученной Хартмутом Кайзером.

Spatial thanks

Я хотел бы поблагодарить Баренда Герельса, Бруно Лаланде, Матеуш и #321;oskot, Lucanus J. Simonson за их поддержку и идеи.