C++ R - требуется реализация дерева

Question

Кто-нибудь знает, хороший и простой в использовании в производственном коде R-tree реализации? (На самом деле, любые реализации - R*, R+ или PR-tree было бы здорово)

Это не имеет значения, если это реализация шаблона или библиотеки, но некоторые реализации, которые Google нашли выглядят очень разочаровывает ...

Answer 1

Проверить R- Деревья код на http://www.superliminal.com/sources/sources.htm

также проверить

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

Answer 2

Я обновил реализацию найденную в http://www.superliminal.com/sources/sources.htm для поддержки более широкого диапазона типов данных.

Вы можете найти свою версию на GitHub: https://github.com/nushoin/RTree

Оригинальная версия является общественным достоянием, как и моя.

Answer 3

spatialindex обеспечивает хороший интерфейс для различных типов пространственных (и пространственно-временных) индексных структур, включая R, R *, TPR деревьев на http://libspatialindex.github.com/

Answer 4

Вы можете также проверить на rtree варианты, представленную Boost.Geometry библиотека:

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

реализация Boost.Geometry rtree позволяет хранить значения произвольного типа в пространственном индексе и выполнение сложных запросов. Параметры, такие как максимальные элементы узла, могут передаваться как параметры компиляции или времени выполнения. Он поддерживает семантику перемещения C++ 11, также эмулируемую на компиляторах pre-C++ 11 благодаря Boost.Move. Он также поддерживает устройства для выделения состояний, которые позволяют, например, для хранения rtree в общей памяти с использованием Boost.Interprocess. И это быстро.

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

Быстрый пример:

Пожалуй, наиболее распространенный случай использования при сохранении некоторых геометрических объектов в контейнере и их ограничительные коробки с некоторыми идентификаторами в пространственном индексе. В случае Boost.Geometry rtree это может выглядеть следующим образом:

#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; 
}