Как перебрать R-дерево наддува?

Question

Я не могу найти эффективный способ перебрать R-дерево наддува ( boost::geometry::index::rtree ) Единственный метод, который я до сих пор придумал, - это выполнить запрос, используя очень большую ограничивающую рамку, чтобы копия всех элементов возвращалась в векторе, однако это, очевидно, не является ни экономичным, ни экономичным по времени. В идеале я просто хотел бы использовать итератор в стиле STL для итерации по дереву обычным способом, но это не представляется возможным?

Answer 1

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

Answer 2

С 1.59.0

begin() а также end() функции-члены определены в bgi::rtree, возвращая const_iterator, Таким образом, можно перебирать все элементы без описанных ниже методов. В C++11:

for(auto const& v: rtree)
    /* do something with v */

До 1.59.0

Как говорили другие, для перебора всех элементов, хранящихся в дереве, вы можете использовать итератор запросов. Однако нет необходимости выполнять фактический пространственный запрос (границы проходов и т. Д.). Вы можете передать фиктивный UnaryPredicate, всегда возвращающийся true завернутый в bgi::satisfies(), В C++11:

std::for_each(rtree.qbegin(bgi::satisfies([](Value const&){ return true; })),
              rtree.qend(),
              [](Value const& v){
                  /* do something with v */
              });

Не итеративные запросы также могут быть использованы для этой цели, но для этого потребуется специальный выходной итератор, например boost::function_output_iterator реализовано в библиотеке Boost.Iterator (см. http://www.boost.org/doc/libs/1_57_0/libs/iterator/doc/function_output_iterator.html). В C++11:

rtree.query(bgi::satisfies([](Value const&){ return true; }),
            boost::make_function_output_iterator([](Value const& v){
                /* do something with v */
            }));

Примечания стороны:

• Для приведенного выше кода требуются заголовки библиотеки Boost.Geometry, упомянутые в документации
• namespace bgi = boost::geometry::index
• Value это тип объектов, хранящихся в bgi::rtree
• boost::function_output_iterator требует #include <boost/function_output_iterator.hpp>
• в C++14 можно использовать общие лямбды, тогда приведенный выше код будет независимым от типа значения