sistemas - C++ R-Se desea la implementación del árbol

sistema de recomendacion tesis

Question

¿Alguien sabe algo bueno y simple de usar en la implementación del código de producción R-tree ? (en realidad, cualquier implementación - R*, R+ o PR-tree sería genial)

No importa si es una implementación de plantilla o biblioteca, pero algunas implementaciones que Google encontró parecen muy decepcionantes ...

Answer 1

Actualicé la implementación que se encuentra en http://www.superliminal.com/sources/sources.htm para admitir una gama más amplia de tipos de datos.

Puede encontrar mi versión en github: https://github.com/nushoin/RTree

La versión original es de dominio público, como la mía.

Answer 2

También puede consultar las variantes de rtree proporcionadas por la biblioteca Boost.Geometry:

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

La implementación de Boost.Geometry rtree permite almacenar valores de tipo arbitrario en el índice espacial y realizar consultas complejas. Parámetros como elementos de nodo máximo pueden pasarse como parámetros de compilación o tiempo de ejecución. Es compatible con la semántica de movimientos de C ++ 11 que también se emula en compiladores anteriores a C ++ 11 gracias a Boost.Move. También es compatible con asignadores de estado que permiten, por ejemplo, almacenar el rtree en una memoria compartida utilizando Boost.Interprocess. Y es rapido

En el lado negativo, el almacenamiento actualmente persistente aún no es compatible, por lo que si necesita más que un índice espacial en memoria, probablemente debería revisar una de las otras bibliotecas mencionadas.

Ejemplo rápido:

Probablemente el caso de uso más común es cuando almacena algunos objetos geométricos en un contenedor y sus cuadros delimitadores con algunos identificadores en el índice espacial. En el caso de Boost.Geometry rtree esto podría verse así:

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

Answer 3

Verifique el código de R-Trees en http://www.superliminal.com/sources/sources.htm

tambien cheque

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

Answer 4

spatialindex proporciona una interfaz agradable para diferentes tipos de estructuras de índices espaciales (y espacio-temporales) que incluyen los árboles R, R *, TPR en http://libspatialindex.github.com/