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

Question

我被要求编写一个函数，该函数接受“LatLon”作为输入（LatLon 是一个具有 2 个双精度数的类：纬度和经度）并返回距离该位置最近的交叉点的 ID（int）。我得到的函数可以返回任何交叉点的位置，也可以返回两个位置之间的距离。由于“性能测试”，我的导师建议我将所有交叉点的位置存储在 R 树中（来自 boost 库），这样可以更快地找到最近的交叉点，而不是迭代所有交叉点。然而，我刚刚学习 R 树是如何工作的，并且在如何创建 R 树方面遇到了困难。

问题是我在网上看到了几个他们创建 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 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 返回一个 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，所以一些操作无法使用它，例如它不能存储在非笛卡尔坐标系中bg::model::box的空间查询（例如）或knn查询所需的位置bgi::intersects()( bgi::nearest()) 因为坐标可以在内部标准化。因此，为了直接使用它，您必须做比通常需要的更多的事情。

因此，如果我是你，我只会将 Point 类型存储bg::model::point在 R 树中，并LatLon在插入之前转换为它，然后在执行查询后返回。

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

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

顺便说一句，如果您不想实现自己的 IndexableGetter （ 的第三个模板参数rtree），则必须将 Point 作为std::pair类型放入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;
}