Как использовать Rtree библиотеки Boost в C++?

Question

Мне предлагается написать функцию, которая берет «LatLon» в качестве входа (LatLon - это класс с двумя удвоениями: широта и долгота) и возвращает ID (int) ближайшего пересечения к этой позиции. Мне даны функции, которые возвращают местоположение любого пересечения, а также возвращают расстояние между двумя позициями. Из-за «тестов производительности» мои преподаватели предложили мне сохранить места всех пересечений в R-Tree (из библиотеки ускорения), где было бы быстрее найти ближайший пересечение, а не повторять все пересечения. Тем не менее, я просто изучаю, как работают R-деревья, и у меня возникают проблемы с его созданием.

Проблема в том, что я видел несколько примеров в Интернете, где они создают R-деревья, но меня действительно смущает то, что они используют только два аргумента, а не четыре, в одном из конструкторов. Например, они используют:

bgi :: rtree < value_t, bgi :: квадратный < 16>> rtree_;

где value_t пара коробки и без знака Int, а другой аргумент размера, тем не менее, если я пытаюсь сделать:

BGI :: rtree < точка, BGI :: квадратичной < 16 >> intersectionRTree ;

где точка - это пара беззнаковых int и LatLon, компилятор жалуется, что я не использую соответствующий конструктор и что у него должно быть четыре аргумента вместо двух.

Я прочитал в Интернете, и считаю, что я должен использовать этот конструктор:

rtree (parameters_type сопзИте &, indexable_getter сопзИте &, value_equal сопзИте &, allocator_type сопзИ &)

Однако, я не» t понять описание каждого аргумента, поэтому я не знаю, как использовать этот конструктор. Итак, вы можете помочь мне понять, что делать? И если возможно, не могли бы вы привести мне короткий пример? Большое спасибо.

Это класс 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 максимальное число пересечений, и пересечение - это индекс пересечения.

Компилятор дает мне подробную информацию об ошибке, которая отправляет меня только в другие файлы, но на самом деле никогда не говорила мне, где я ошибаюсь.

Answer 1

Для использования типа Boost.Geometry в качестве одной из поддерживаемых геометрий вам необходимо адаптировать этот тип к одной из концепций Boost.Geometry. Это, как вы говорите, в библиотеке, как он может использовать объекты этого типа, как получить доступ к координатам, которые система координат и типы систем координат используются и т.д.

В случае Point: http://www.boost.org/doc/libs/1_63_0/libs/geometry/doc/html/geometry/reference/concepts/concept_point.html

Для удобный Boost.Геометрия обеспечивает макросы, которые делают это для вас в наиболее типичных случаях: http://www.boost.org/doc/libs/1_63_0/libs/geometry/doc/html/geometry/reference/adapted/register.html

Вы, например, немного проблемны, ваша точка не определяет сеттеры, а только геттеры, поэтому некоторые из операций не будут работать с ней, например. он не может быть сохранен в bg::model::box, требуемом пространственным запросом (например, bgi::intersects()) или запросом knn в некартовной системе координат (bgi::nearest()), поскольку координаты могут быть нормированы внутри. Поэтому, чтобы использовать его напрямую, вам придется делать больше вещей, чем обычно требуется.

Так что, если бы я был вами, я бы просто сохранил Точку типа bg::model::point в R-дереве и конвертировал LatLon в нее перед вставкой, а затем назад после выполнения запроса.

Но если вы действительно хотите использовать LatLon класс с библиотекой вы можете:

• извлечь из него или обернуть его в какой-либо другой тип, осуществлять необходимые операции в этом типе и использовать REGISTER макросъемки (пример ниже) ,
• адаптировать LatLon тип вручную, как это делается здесь, например: https://github.com/boostorg/geometry/blob/develop/include/boost/geometry/geometries/point_xy.hpp#L87

Btw, если вы не хотите, чтобы реализовать свой собственный IndexableGetter (3-й параметр шаблона в rtree) вы должны поставить точку в std::pair как First type. Ниже я предположил, что вы хотите использовать систему координат 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; 
}