Запросы возвращают Ценность , что соответствует некоторым предикатам. В настоящее время поддерживаются три типа предикатов:

Например, запросы могут использоваться для извлечения значений:

Performing a query

Существуют различные способы выполнения запроса. Они представлены ниже. Все они возвращают Values, пересекающие некоторую область, определенную как Box.

Функция участника вызова

std::vector<Value> returned_values;
Box box_region(...);
rt.query(bgi::intersects(box_region), std::back_inserter(returned_values));

Бесплатный вызов функции

std::vector<Value> returned_values;
Box box_region(...);
bgi::query(rt, bgi::intersects(box_region), std::back_inserter(returned_values));

Диапазон, генерируемый оператором |

Box box_region(...);
BOOST_FOREACH(Value & v, rt | bgi::adaptors::queried(bgi::intersects(box_region)))
  ; // do something with v

Итераторы запросов, возвращаемые функциями членов

std::vector<Value> returned_values;
Box box_region(...);
std::copy(rt.qbegin(bgi::intersects(box_region)), rt.qend(), std::back_inserter(returned_values));

Итераторы запросов, возвращаемые свободными функциями

std::vector<Value> returned_values;
Box box_region(...);
std::copy(bgi::qbegin(rt, bgi::intersects(box_region)), bgi::qend(rt), std::back_inserter(returned_values));

Spatial predicates

Запросы с использованием пространственных предикатов возвращают Ценность, которые так или иначе связаны с некоторой геометрией - коробкой, многоугольником и т.д. Имена пространственных предикатов соответствуют именам Бооста. Геометрические алгоритмы (булевые операции). Примеры некоторых основных запросов можно найти в таблицах ниже. Область запроса и результат Ценность являются оранжевыми.

Пространственные предикаты генерируются функциями, определенными в boost::geometry::index namespace.

rt.query(index::contains(box), std::back_inserter(result));
rt.query(index::covered_by(box), std::back_inserter(result));
rt.query(index::covers(box), std::back_inserter(result));
rt.query(index::disjont(box), std::back_inserter(result));
rt.query(index::intersects(box), std::back_inserter(result));
rt.query(index::overlaps(box), std::back_inserter(result));
rt.query(index::within(box), std::back_inserter(result));

Все пространственные предикаты могут быть отрицаемы, например:

rt.query(!index::intersects(box), std::back_inserter(result));
// the same as
rt.query(index::disjoint(box), std::back_inserter(result));

Nearest neighbours queries

Запросы ближайших соседей возвращают Ценность, которые наиболее близки к некоторой геометрии. Примеры запросов k-NN представлены ниже. 5 Ценность , ближайшая к геометрии, оранжевая.

Для выполнения запроса knn необходимо пройти ближайший предикат, генерируемый функцией nearest(), определенной в boost::geometry::index namespace. Для неточечных Indexable наименьшее расстояние вычисляется с помощью функции bg::comparable_distance(). Следующий запрос возвращает k Ценность ближе всего к некоторой точке в пространстве.

std::vector<Value> returned_values;
Point pt(/*...*/);
rt.query(bgi::nearest(pt, k), std::back_inserter(returned_values));

Таким же образом можно использовать различные геометрии запросов:

Box box(/*...*/);
rt.query(bgi::nearest(box, k), std::back_inserter(returned_values));
Segment seg(/*...*/);
rt.query(bgi::nearest(seg, k), std::back_inserter(returned_values));

User-defined unary predicate

Пользователь может передать UnaryPredicate - функцию, объект функции или лямбда-выражение, берущее обратную отсылку к Значению и возвращающему бул. Этот объект может быть передан запросу, чтобы проверить, должна ли Ценность быть возвращена запросом. Для этого можно использовать функцию index::satisfies(), как в примере ниже:

bool is_red(Value const& v)
{
  return v.is_red();
}
struct is_red_o
{
  template <typename Value>
  bool operator()(Value const& v)
  {
    return v.is_red();
  }
}
// ...
rt.query(index::intersects(box) && index::satisfies(is_red),
         std::back_inserter(result));
rt.query(index::intersects(box) && index::satisfies(is_red_o()),
         std::back_inserter(result));
#ifndef BOOST_NO_CXX11_LAMBDAS
rt.query(index::intersects(box) && index::satisfies([](Value const& v) { return v.is_red(); }),
         std::back_inserter(result));
#endif

satisfies() может быть отрицательным, например:

bool is_red(Value const& v) { return v.is_red(); }
bool is_not_red(Value const& v) { return !v.is_red(); }
// ...
rt.query(index::intersects(box) && index::satisfies(is_red),
         std::back_inserter(result));
// the same as
rt.query(index::intersects(box) && !index::satisfies(is_not_red),
         std::back_inserter(result));

Passing a set of predicates

Можно использовать некоторое количество предикатов в одном запросе, соединив их с оператором&& например, Pred1 &&Pred2&& && .

Эти предикаты связаны логическим И. Прохождение всех предикатов вместе не только позволяет создавать расширенные запросы, но и быстрее, чем отдельные вызовы, потому что дерево проходит только один раз. Трэверсинг продолжается и Ценность возвращается только при условии выполнения всех предикатов. Предикаты проверяются слева направо, поэтому размещение большинства ограничительных предикатов в первую очередь должно ускорить поиск.

rt.query(index::intersects(box1) && !index::within(box2),
         std::back_inserter(result));
rt.query(index::intersects(box1) && !index::within(box2) && index::overlaps(box3),
         std::back_inserter(result));

Конечно, можно соединить различные типы предикатов вместе.

index::query(rt, index::nearest(pt, k) && index::within(b), std::back_inserter(returned_values));
BOOST_FOREACH(Value & v, rt | index::adaptors::queried(index::nearest(pt, k) && index::covered_by(b)))
  ; // do something with v

Iterative queries

Запрос, выполняемый с использованием итераторов запросов, может быть приостановлен и возобновлен при необходимости, например, когда запрос занимает слишком много времени, или может быть остановлен в какой-то момент, когда были собраны все интересные значения. Итератор запросов возвращается посредством функции qbegin(), которая требует прохождения предикатов, таких как функция члена query().

for ( Rtree::const_query_iterator it = tree.qbegin(bgi::nearest(pt, 10000)) ;
      it != tree.qend() ; ++it )
{
    // do something with value
    if ( has_enough_nearest_values() )
        break;
}

	Note
	В случае итеративных запросов k-NN он гарантированно повторяется над ближайшим значением .

	Warning
	Модификация rtree, например вставка или удаление Values, может привести к недействию итераторов.

Inserting query results into the other R-tree

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

namespace bgi = boost::geometry::index;
typedef std::pair<Box, int> Value;
typedef bgi::rtree< Value, bgi::linear<32, 8> > RTree;
RTree rt1;
/* some inserting into the tree */
std::vector<Value> result;
rt1.query(bgi::intersects(Box(/*...*/)), std::back_inserter(result));
RTree rt2(result.begin(), result.end());

Однако есть и лучшие способы. Один из этих методов упоминается в разделе «Создание и модификация». Итератор вставки может быть передан непосредственно в запрос.

RTree rt3;
rt1.query(bgi::intersects(Box(/*...*/))), bgi::inserter(rt3));

Если вы пользователь Boost. Диапазон вы оцените третий вариант. Вы можете передать диапазон результатов непосредственно в конструктор или вставить () функцию члена.

RTree rt4(rt1 | bgi::adaptors::queried(bgi::intersects(Box(/*...*/)))));