Boost R-tree：计算满足查询的元素

Question

到目前为止，当我想统计我的R树中有多少元素满足特定的空间查询时，归结为运行查询，收集匹配项然后统计它们，大致如下:

std::vector<my_type> results;
rtree_ptr->query(bgi::intersects(query_box), std::back_inserter(results));
int nbElements = results.size();

有没有更好的方法，即直接计数而不检索实际元素的方法？我还没有找到任何可以做到的，但谁知道呢。（我正在用打包算法构建我的树，以防它有任何相关性。）

我的动机是我注意到我的查询速度取决于匹配的数量。如果有 0 个匹配项，则查询或多或少是瞬时的；如果有 10 000 个匹配项，则需要几秒钟。由于可以非常快地确定是否存在任何匹配项，因此遍历树似乎非常快（至少在我制作的索引中）；它正在收集所有结果，如果有很多匹配项，这些结果会使查询变慢。由于我对收集不感兴趣，只是简单地计数（至少对于某些查询），所以如果我可以跳过收集就太棒了。

Answer 1

您可以使用函数输出迭代器：

size_t cardinality = 0; // number of matches in set
auto count_only = boost::make_function_output_iterator([&cardinality] (Tree::value_type const&) { ++cardinality; });

这样使用：

C++11 使用 lambda

Live On Coliru

#include <boost/function_output_iterator.hpp>
#include <boost/geometry/geometries/box.hpp>
#include <boost/geometry/geometries/point_xy.hpp>
#include <boost/geometry/core/cs.hpp>
#include <boost/geometry/index/rtree.hpp>

namespace bgi = boost::geometry::index;
using point = boost::geometry::model::d2::point_xy<int, boost::geometry::cs::cartesian>;
using box = boost::geometry::model::box<point>;

int main()
{
    using Tree = bgi::rtree<box, bgi::rstar<32> >;
    Tree tree;

    size_t cardinality = 0; // number of matches in set
    auto count_only = boost::make_function_output_iterator([&cardinality] (Tree::value_type const&) { ++cardinality; });

    box query_box;
    tree.query(bgi::intersects(query_box), count_only);

    int nbElements = cardinality;

    return nbElements;
}

C++03 使用函数对象

对于 C++，您可以用（多态！）函数对象替换 lambda：

struct count_only_f {
    count_only_f(size_t& card) : _cardinality(&card) { }

    template <typename X>
    void operator()(X) const {
        ++(*_cardinality);
    }

  private:
    size_t *_cardinality;
};

// .... later:
boost::function_output_iterator<count_only_f> count_only(cardinality);

C++03 使用 Boost Phoenix

我认为这是使用 Boost Phoenix 的好地方：

#include <boost/phoenix.hpp>
// ...

size_t cardinality = 0; // number of matches in set
tree.query(bgi::intersects(query_box), boost::make_function_output_iterator(++boost::phoenix::ref(cardinality)));

或者，更典型的是使用命名空间别名：

#include <boost/phoenix.hpp>
// ...

size_t cardinality = 0; // number of matches in set
tree.query(bgi::intersects(query_box), make_function_output_iterator(++phx::ref(cardinality)));

Answer 2

我脑电波迟到了。甚至比使用 function_output_iterator 更好的方法是使用 boost::geometry::index query_iterators.

原则上，它会导致完全相同的行为，代码稍微简单一些：

box query_box;
auto r = boost::make_iterator_range(bgi::qbegin(tree, bgi::intersects(query_box)), {});
// in c++03, spell out the end iterator: bgi::qend(tree)

size_t nbElements = boost::distance(r);

NOTE: size() is not available because the query_const_iterators are not of the random-access category.

不过结合起来可能会稍微舒服一些。比如说，如果您想对每个项目进行额外检查，您可以使用标准库算法，例如：

size_t matching = std::count_if(r.begin(), r.end(), some_predicate);

我认为基于范围的解决方案更灵活一些（相同的代码可用于实现其他算法，如 partial_sort_copy or std::transform which would be hard to fit into the output-iterator idiom from my ）。

Boost R-tree：计算满足查询的元素

Boost R-tree : counting elements satisfying a query

c++

boost

r-tree

boost-geometry

C++11 使用 lambda

C++03 使用函数对象

C++03 使用 Boost Phoenix