如何迭代一个提升R树？

Question

我似乎无法找到一种有效的方法来迭代boost R-tree (boost::geometry::index::rtree)。到目前为止，我提出的唯一方法是使用非常大的边界框执行查询，以便在向量中返回所有元素的副本，但这显然既不节省空间也不节省时间。理想情况下，我只是想使用STL样式的迭代器以通常的方式迭代树，但这似乎不可能？

Answer 1

如果您的查询包含要迭代的所有元素，则不必执行查询将其全部放入向量中，但可以使用qbegin和qend直接迭代元素。捕获所有元素的必要界限可以从bounds获得。

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之前

正如其他人所说，迭代存储在rtree中的所有元素，您可以使用查询迭代器。但是，不需要执行实际的空间查询（传递边界等）。你可以传递一个虚拟的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个通用lambdas，然后上面的代码将是Value-type agnostic