c++ - 具有适配 std::pair 点类型的 R-Tree 查询

Question

我正在使用以下 (Rcpp) 代码执行编译时断言。此代码将 10^6 个随机点插入到一个 vector 中，从该 vector 构建 r 树，然后查询落在由 (1/3, 1/3) 和 (2/3, 2/3) 包围的框内的点.

// [[Rcpp::depends(BH)]]
// [[Rcpp::plugins(cpp11)]]

#include <Rcpp.h>
#include <vector>
#include <boost/geometry.hpp>
#include <boost/geometry/geometries/register/box.hpp>
#include <boost/geometry/geometries/register/point.hpp>

namespace bg = boost::geometry;
namespace bgi = boost::geometry::index;

using key_type = std::pair<double, double>;
using box_type = std::pair<key_type, key_type>;
using range_type = std::vector<key_type>;

BOOST_GEOMETRY_REGISTER_POINT_2D(key_type, double,
                                 bg::cs::cartesian,
                                 first, second);

BOOST_GEOMETRY_REGISTER_BOX(box_type, key_type, first, second);

// [[Rcpp::export]]
void test_it()
{
  range_type data;

  for (int i = 0; i != 1e6; ++i)
    data.emplace_back(R::runif(0, 1), R::runif(0, 1));

  using rtree_type = bgi::rtree<key_type, bgi::linear<16>>;

  rtree_type rt(data);

  key_type p1 = std::make_pair(0.33, 0.33),
    p2 = std::make_pair(0.66, 0.66);

  box_type roi = std::make_pair(p1, p2);

  range_type res;

  rt.query(bgi::contains(roi), std::back_inserter(res));

}

没有最后一个查询行也能正常编译。编译器输出为:

In file included from geom_test.cpp:7:
In file included from /usr/local/include/boost/geometry.hpp:17:
In file included from /usr/local/include/boost/geometry/geometry.hpp:50:
In file included from /usr/local/include/boost/geometry/strategies/strategies.hpp:33:
In file included from /usr/local/include/boost/geometry/strategies/disjoint.hpp:24:
In file included from /usr/local/include/boost/geometry/strategies/relate.hpp:23:
/usr/local/include/boost/geometry/strategies/within.hpp:80:5: error: no matching function for call to 'assertion_failed'
    BOOST_MPL_ASSERT_MSG
    ^~~~~~~~~~~~~~~~~~~~
/usr/local/include/boost/mpl/assert.hpp:435:48: note: expanded from macro 'BOOST_MPL_ASSERT_MSG'
#define BOOST_MPL_ASSERT_MSG( c, msg, types_ ) \
                                               ^
/usr/local/include/boost/mpl/assert.hpp:429:9: note: expanded from macro '\
BOOST_MPL_ASSERT_MSG_IMPL'
        boost::mpl::assertion_failed<(c)>( BOOST_PP_CAT(mpl_assert_arg,counter)::assert_arg() ) \
        ^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
/usr/local/include/boost/mpl/assert.hpp:60:58: note: expanded from macro '\
BOOST_MPL_AUX_ASSERT_CONSTANT'
#   define BOOST_MPL_AUX_ASSERT_CONSTANT(T, expr) enum { expr }
                                                         ^~~~

Answer 1

你说

then queries for points falling with a box bounded by (1/3, 1/3) and (2/3, 2/3)

然而您的代码正在寻找“包含”一个框的点。

你的意思可能是:

rt.query(bgi::within(roi), std::back_inserter(res));

演示

Live On Coliru

#include <boost/geometry.hpp>
#include <boost/geometry/geometries/register/box.hpp>
#include <boost/geometry/geometries/register/point.hpp>
#include <vector>
#include <random>
#include <iostream>

namespace bg = boost::geometry;
namespace bgi = boost::geometry::index;

using key_type = std::pair<double, double>;
using box_type = std::pair<key_type, key_type>;
using range_type = std::vector<key_type>;

BOOST_GEOMETRY_REGISTER_POINT_2D(key_type, double, bg::cs::cartesian, first, second)
BOOST_GEOMETRY_REGISTER_BOX(box_type, key_type, first, second)

int main() {
    std::mt19937 engine { std::random_device{}() };
    std::uniform_real_distribution<double> dist(0,1.0);

    range_type data;

    for (int i = 0; i != 1e6; ++i)
        data.emplace_back(dist(engine), dist(engine));

    using rtree_type = bgi::rtree<key_type, bgi::linear<16> >;

    rtree_type rt(data);

    box_type const roi {{0.33, 0.33}, {0.66,0.66}};

    range_type res;
    rt.query(bgi::within(roi), std::back_inserter(res));

    std::cout << res.size() << " results\n";
}

打印类似的东西

109073 results