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

Ответ 1

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

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

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

Ответ 2

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

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

Функция Boost.Geometry rtree позволяет хранить значения произвольного типа в пространственном индексе и выполнять сложные запросы. Параметры, такие как максимальные элементы node, могут передаваться как параметры компиляции или времени выполнения. Он поддерживает семантику перемещения С++ 11, также эмулируемую на компиляторах pre-С++ 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;
}

Ответ 3

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

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

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

Ответ 4

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