Template parameters

R-дерево имеет 5 параметров, но требуется только 2:

rtree<Value,
      Parameters,
      IndexableGetter = index::indexable<Value>,
      EqualTo = index::equal_to<Value>,
      Allocator = std::allocator<Value> >

Values and Indexables

R-дерево может хранить<Value>s любого типа, пока объекты пройденной функции знают, как интерпретировать те<Value>s, то есть извлекать<Indexable>, которые R-дерево может обрабатывать и сравнивать<Value>s.<Indexable>- это тип, адаптированный к концепции точки, коробки или сегмента. Примеры деревьев, хранящих<Value>, переводимых на различные<Indexable>, представлены ниже.

Объекты<index::indexable<Value>>и<index::equal_to<Value>>по умолчанию определены для некоторых типично используемых типов<Value>, которые могут храниться без определения каких-либо дополнительных классов. По умолчанию дерево может хранить чистые<Indexable>с, пары и кортежи. В случае этих двух типов сборки<Indexable>должен быть первым типом хранения.

По умолчанию<boost::tuple<...>>поддерживается на всех компиляторах. Если компилятор поддерживает кортежи C++11 и вариадные шаблоны, то<std::tuple<...>>также может использоваться «из коробки».

Примеры типов по умолчанию<Value>:

geometry::model::point<...>
geometry::model::point_xy<...>
geometry::model::box<...>
geometry::model::segment<...>
std::pair<geometry::model::box<...>, unsigned>
boost::tuple<geometry::model::point<...>, int, float>

<index::indexable<Value>>,<index::indexable<Value>>,<Indexable>,<Value>,<Indexable>,<Value>.

	Important
	Перевод выполняется довольно часто внутри контейнера — каждый раз, когда он нужен.

Предопределенный<index::equal_to<Value>>:

Balancing algorithms compile-time parameters

<Value>может быть вставлен в R-дерево многими различными способами. Окончательная внутренняя структура R-дерева зависит от алгоритмов, используемых в процессе вставки и параметров. Наиболее важным является алгоритм балансировки узлов. В настоящее время могут быть созданы три известных типа R-деревьев.

Линейное — классическое R-дерево с использованием алгоритма балансировки линейной сложности

index::rtree< Value, index::linear<16> > rt;

Квадратное — классическое R-дерево с использованием алгоритма балансировки квадратичной сложности

index::rtree< Value, index::quadratic<16> > rt;

R*-дерево - алгоритм балансировки, минимизирующий перекрытие узлов с принудительной реинсертацией

index::rtree< Value, index::rstar<16> > rt;

Balancing algorithms run-time parameters

Параметры алгоритма балансировки могут быть переданы R-дереву во время выполнения. Для использования версий R-дерева можно пройти параметры, названия которых начинаются с<dynamic_>.

// linear
index::rtree<Value, index::dynamic_linear> rt(index::dynamic_linear(16));
// quadratic
index::rtree<Value, index::dynamic_quadratic> rt(index::dynamic_quadratic(16));
// rstar
index::rtree<Value, index::dynamic_rstar> rt(index::dynamic_rstar(16));

Очевидным недостатком является немного более медленное R-дерево.

Non-default parameters

Параметры R-дерево без по умолчанию описаны в ссылке.

Copying, moving and swapping

R-дерево является копируемым и подвижным контейнером. Семантика движения реализуется с помощью Boost. Переместите библиотеку, чтобы можно было перемещать контейнер на компиляторах без поддержки ссылок на значение.

// default constructor
index::rtree< Value, index::rstar<8> > rt1;
// copy constructor
index::rtree< Value, index::rstar<8> > rt2(r1);
// copy assignment
rt2 = r1;
// move constructor
index::rtree< Value, index::rstar<8> > rt3(boost::move(rt1));
// move assignment
rt3 = boost::move(rt2);
// swap
rt3.swap(rt2);

Inserting and removing Values

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

using namespace boost::geometry;
typedef std::pair<Box, int> Value;
index::rtree< Value, index::quadratic<16> > rt;

Для вставки или удаления «Ценности» по вызову способа можно использовать следующий код.

Value v = std::make_pair(Box(...), 0);
rt.insert(v);
rt.remove(v);

Чтобы вставить или удалить «Ценность» по вызову функции, можно использовать следующий код.

Value v = std::make_pair(Box(...), 0);
index::insert(rt, v);
index::remove(rt, v);

Как правило, вы выполняете эти операции в цикле, чтобы, например, вставить некоторое количество<Value>s, соответствующее геометрическим объектам (например,<Polygons>), хранящимся в другом контейнере.

Additional interface

R-дерево позволяет создавать, вставлять и удалять значения из диапазона. Диапазон может быть пройден как<[first,last)>пара итераторов или как Диапазон, адаптированный к одному из Усилителей. Концепции диапазона.

namespace bgi = boost::geometry::index;
typedef std::pair<Box, int> Value;
typedef bgi::rtree< Value, bgi::linear<32> > RTree;
std::vector<Value> values;
/* vector filling code, here */
// create R-tree with default constructor and insert values with insert(Value const&)
RTree rt1;
BOOST_FOREACH(Value const& v, values)
   rt1.insert(v);
// create R-tree with default constructor and insert values with insert(Iter, Iter)
RTree rt2;
rt2.insert(values.begin(), values.end());
// create R-tree with default constructor and insert values with insert(Range)
RTree rt3;
rt3.insert(values_range);
// create R-tree with constructor taking Iterators
RTree rt4(values.begin(), values.end());
// create R-tree with constructor taking Range
RTree rt5(values_range);
// remove values with remove(Value const&)
BOOST_FOREACH(Value const& v, values)
   rt1.remove(v);
// remove values with remove(Iter, Iter)
rt2.remove(values.begin(), values.end());
// remove values with remove(Range)
rt3.remove(values_range);

Кроме того, можно пройти диапазон, адаптированный одним из Boost. Адаптеры диапазона в rtree (более полный пример можно найти в)Примерыраздела.

// create Rtree containing `std::pair<Box, int>` from a container of Boxes on the fly.
RTree rt6(boxes | boost::adaptors::indexed()
                | boost::adaptors::transformed(pair_maker()));

Insert iterator

Есть такие функции, как<std::copy()>, или запросы R-дерева, которые копируют значения в итератор вывода. Для того, чтобы вставить значения в контейнер в этом виде функции, могут использоваться итераторы вставки. Геометрия. Индекс предоставляет свой собственный<bgi::insert_iterator<Container>>, который генерируется<bgi::inserter()>функцией.

namespace bgi = boost::geometry::index;
typedef std::pair<Box, int> Value;
typedef bgi::rtree< Value, bgi::linear<32> > RTree;
std::vector<Value> values;
/* vector filling code, here */
// create R-tree and insert values from the vector
RTree rt1;
std::copy(values.begin(), values.end(), bgi::inserter(rt1));
// create R-tree and insert values returned by a query
RTree rt2;
rt1.spatial_query(Box(/*...*/), bgi::inserter(rt2));