C++ R - thực hiện cây muốn

Question

Có ai biết tốt và đơn giản để sử dụng trong mã sản xuất R-tree triển khai không? (Trên thực tế, bất kỳ hiện thực - R*, R+ hoặc PR-tree sẽ là tuyệt vời)

Nó không quan trọng nếu nó là một mẫu hoặc thư viện thực hiện, nhưng một số hiện thực mà Google tìm thấy trông rất đáng thất vọng ...

Answer 1

Kiểm tra R- cây mã trên http://www.superliminal.com/sources/sources.htm

cũng kiểm tra

http://www.virtualroadside.com/blog/index.php/2008/10/04/r-tree-implementation-for-cpp/

Answer 2

tôi cập nhật việc thực hiện tìm thấy trong http://www.superliminal.com/sources/sources.htm để hỗ trợ nhiều loại dữ liệu hơn.

Bạn có thể tìm thấy phiên bản của tôi trên github: https://github.com/nushoin/RTree

Phiên bản gốc là phạm vi công cộng, như là của tôi.

Answer 3

spatialindex cung cấp một giao diện đẹp để các loại khác nhau của các cấu trúc chỉ số không gian (và không-thời gian) bao gồm R, R *, cây TPR tại http://libspatialindex.github.com/

Answer 4

Bạn cũng có thể kiểm tra rtree biến thể được cung cấp bởi các Boost.Geometry thư viện:

http://www.boost.org/doc/libs/release/libs/geometry/doc/html/geometry/spatial_indexes.html

Boost.Geometry rtree thực hiện cho phép lưu trữ các giá trị kiểu độc đoán trong chỉ mục không gian và thực hiện truy vấn phức tạp. Các tham số như các phần tử nút tối đa có thể được chuyển thành các tham số biên dịch hoặc thời gian chạy. Nó hỗ trợ ngữ nghĩa di chuyển C++ 11 cũng được mô phỏng trên các trình biên dịch trước C++ 11 nhờ vào Boost.Move. Nó cũng hỗ trợ các trình phân bổ trạng thái cho phép, ví dụ: để lưu trữ rtree trong bộ nhớ dùng chung bằng cách sử dụng Boost.Interprocess. Và nó nhanh.

Ở phía dưới, lưu trữ hiện tại vẫn chưa được hỗ trợ vì vậy nếu bạn cần nhiều hơn chỉ mục không gian trong bộ nhớ, bạn có thể nên kiểm tra một trong các thư viện được đề cập khác.

nhanh Ví dụ:

Có lẽ trường hợp sử dụng phổ biến nhất là khi bạn lưu trữ một số đối tượng hình học trong một container và hộp bounding của họ với một số id trong chỉ mục không gian. Trong trường hợp của Boost.Geometry rtree này có thể trông như thế này:

#include <boost/geometry.hpp> 
#include <boost/geometry/index/rtree.hpp> 
#include <vector> 

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

/* The definition of my_object type goes here */ 

int main() 
{ 
    typedef bg::model::point<float, 2, bg::cs::cartesian> point; 
    typedef bg::model::box<point> box; 
    typedef std::pair<box, size_t> value; 

    std::vector<my_object> objects; 

    /* Fill objects */ 

    // create the R* variant of the rtree 
    bgi::rtree< value, bgi::rstar<16> > rtree; 

    // insert some values to the rtree 
    for (size_t i = 0 ; i < objects.size() ; ++i) 
    { 
     // create a box 
     box b = objects[i].calculate_bounding_box(); 
     // insert new value 
     rtree.insert(std::make_pair(b, i)); 
    } 

    // find values intersecting some area defined by a box 
    box query_box(point(0, 0), point(5, 5)); 
    std::vector<value> result_s; 
    rtree.query(bgi::intersects(query_box), std::back_inserter(result_s)); 

    // find 5 nearest values to a point 
    std::vector<value> result_n; 
    rtree.query(bgi::nearest(point(0, 0), 5), std::back_inserter(result_n)); 

    return 0; 
}