如何在 C++ 中使用 Boost 库的 Rtree？

Question

我被要求编写一个函数，该函数将 "LatLon" 作为输入（LatLon 是一个 class，具有 2 个双精度值：纬度和经度）并且 return 是 ID (int) 到该位置最近的交叉点。我得到的函数是 return 任何交叉点的位置，以及 return 两个位置之间的距离。由于 "performance tests"，我的导师建议我将所有交叉点的位置存储在 R 树中（来自 boost 库），这样可以更快地找到最近的交叉点，而不是遍历所有交叉点.然而，我只是在学习 R-Trees 是如何工作的，我在如何创建 R-Trees 方面遇到了麻烦。

问题是我在网上看到了几个创建 R 树的例子，但真正让我感到困惑的是，他们在其中一个构造函数中只使用了两个参数，而不是四个。例如，他们使用：

bgi::rtree< value_t, bgi::quadratic<16> > rtree_;

其中 value_t 是一对 box 和 unsigned int，另一个参数是大小，但是如果我尝试制作：

bgi::rtree<点，bgi::quadratic<16>>交集RTree；

其中 point 是一对 unsigned int 和 LatLon，编译器抱怨我没有使用正确的构造函数，它应该有四个参数而不是两个。

我在网上看了，发现我应该使用这个构造函数：

rtree(parameters_type const &, indexable_getter const &, value_equal const &, allocator_type const &)

但是，我不明白每个参数的描述，所以我不知道如何使用这个构造函数。那么，你能帮我理解该怎么做吗？如果可能的话，你能给我举个简短的例子吗？非常感谢。

这是 LatLon class。它是只读的，所以我不能修改它：

class LatLon{

public:
LatLon(){}
explicit LatLon(float lat_, float lon_) : m_lat(lat_),m_lon(lon_){}

double lat() const { return m_lat; }
double lon() const { return m_lon; }

private:
float m_lat = std::numeric_limits<float>::quiet_NaN();
float m_lon = std::numeric_limits<float>::quiet_NaN();

friend class boost::serialization::access;
template<class Archive>void serialize(Archive& ar, unsigned int)
    { ar & m_lat & m_lon; }
};

std::ostream& operator<<(std::ostream& os,LatLon);
std::array<LatLon,4> bounds_to_corners(std::pair<LatLon,LatLon> bounds);

这就是我尝试做的原因：

#include "LatLon.h"
#include <string>
#include <vector>
#include <cmath>
#include <boost/geometry.hpp>
#include <boost/geometry/index/rtree.hpp>
#include <algorithm>

namespace bg = boost::geometry;
namespace bgi = boost::geometry::index;
using namespace std;
typedef pair<unsigned,LatLon> point;

bgi::rtree<point, bgi::quadratic<16>> intersectionRTree;

for (unsigned intersection = 0; intersection < intersectionNumber; intersection++) 
{point intP = make_pair(intersection,getIntersectionPosition(intersection));
intersectionRTree.insert(intP);}

函数getIntersectionPosition return一个LatLon，intersectionNumber是最大的路口数，intersection是一个路口的索引。

编译器给我错误的详细信息，只将我发送到另一个文件，但实际上从来没有告诉我哪里错了。

Answer 1

为了将 Boost.Geometry 中的类型用作受支持的几何图形之一，您必须使该类型适应 Boost.Geometry 概念之一。这就是您告诉库如何使用这种类型的对象、如何访问坐标、使用哪种坐标系和坐标类型等的方式。

以点为例：http://www.boost.org/doc/libs/1_63_0/libs/geometry/doc/html/geometry/reference/concepts/concept_point.html

为方便起见，Boost.Geometry 提供了在大多数典型情况下为您执行此操作的宏：http://www.boost.org/doc/libs/1_63_0/libs/geometry/doc/html/geometry/reference/adapted/register.html

你的例子有点问题，你的 Point 没有定义 setter，只有 getter，所以有些操作不能用它，例如它不能存储在空间查询（例如bgi::intersects()）或non-cartesian坐标系（bgi::nearest()）中的knn查询所需的bg::model::box中，因为坐标可能在内部被归一化。因此，为了直接使用它，您必须做比通常需要的更多的事情。

所以如果我是你，我会简单地将 bg::model::point 类型的点存储在 R-tree 中，并在插入之前将 LatLon 转换成它，然后在执行查询后返回。

但是如果你真的想在库中使用 LatLon class 你可以：

从它派生或将其包装在其他类型中，在此类型中实现必要的操作并使用 REGISTER 宏（下面的示例）。
适应 LatLon 手动输入，例如：https://github.com/boostorg/geometry/blob/develop/include/boost/geometry/geometries/point_xy.hpp#L87

顺便说一句，如果您不想实现自己的 IndexableGetter（rtree 的第三个模板参数），您必须将 std::pair 中的 Point 作为 First类型。下面我假设你想使用 spherical_equatorial 坐标系。我还假设坐标类型是 float 因为这是您在示例中实际存储在 LatLon 中的内容。

#include <boost/geometry.hpp>
#include <boost/geometry/geometries/register/point.hpp>
#include <boost/geometry/index/rtree.hpp>
#include <iostream>
#include <limits>
#include <vector>

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

class LatLon
{
public:
    LatLon(){}
    explicit LatLon(float lat_, float lon_) : m_lat(lat_),m_lon(lon_){}

    float lat() const { return m_lat; }
    float lon() const { return m_lon; }

private:
    float m_lat = std::numeric_limits<float>::quiet_NaN();
    float m_lon = std::numeric_limits<float>::quiet_NaN();
};

struct MyLatLon
{
    MyLatLon() {}
    MyLatLon(float lat_, float lon_) : ll(lat_, lon_){}

    float get_lat() const { return ll.lat(); }
    float get_lon() const { return ll.lon(); }
    void set_lat(float v) { ll = LatLon(v, ll.lon()); }
    void set_lon(float v) { ll = LatLon(ll.lat(), v); }

    LatLon ll;
};

BOOST_GEOMETRY_REGISTER_POINT_2D_GET_SET(MyLatLon, float,
                                         bg::cs::spherical_equatorial<bg::degree>,
                                         get_lon, get_lat, set_lon, set_lat)

int main()
{
    typedef std::pair<MyLatLon, unsigned> point_pair;

    bgi::rtree<point_pair, bgi::quadratic<16>> intersectionRTree;

    intersectionRTree.insert(std::make_pair(MyLatLon(0, 0), 0));
    intersectionRTree.insert(std::make_pair(MyLatLon(2, 2), 1));

    bg::model::box<MyLatLon> b(MyLatLon(1, 1), MyLatLon(3, 3));
    std::vector<point_pair> result1;
    intersectionRTree.query(bgi::intersects(b), std::back_inserter(result1));
    if (! result1.empty())
        std::cout << bg::wkt(result1[0].first) << std::endl;

    std::vector<point_pair> result2;
    intersectionRTree.query(bgi::nearest(MyLatLon(0, 1), 1), std::back_inserter(result2));
    if (! result2.empty())
        std::cout << bg::wkt(result2[0].first) << std::endl;
}

如何在 C++ 中使用 Boost 库的 Rtree？

How can I use the Rtree of the Boost Library in C++?

c++

database

boost

r-tree

boost-geometry