C++ R - implementación del árbol deseada

Question

¿Alguien sabe una buena y simple de usar en el código de producción R-tree implementación? (En realidad, cualquier implementación - R*, R+ o PR-tree serían grandes)

No importa si se trata de una aplicación de plantilla o en la biblioteca, pero algunas implementaciones que Google ha encontrado un aspecto muy decepcionante ...

Answer 1

Comprobar R- código de árboles en http://www.superliminal.com/sources/sources.htm

también comprobar

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

Answer 2

he actualizado la aplicació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 es la mía.

Answer 3

spatialindex proporciona una interfaz agradable a los diferentes tipos de estructuras de indexación espacial (y espacio-temporal) incluyendo R, R *, árboles TPR en http://libspatialindex.github.com/

Answer 4

También puede revisar la rtree variantes proporcionada por el Boost.Geometry de biblioteca:

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

aplicación Boost.Geometry RTree permite el almacenamiento de valores de tipo arbitrario en el índice espacial y la realización de consultas complejas. Los parámetros como los elementos de nodo máximo se pueden pasar como parámetros de compilación o tiempo de ejecución. Es compatible con la semántica de movimiento C++ 11 también emulada en compiladores anteriores a C++ 11 gracias a Boost.Move. También es compatible con asignadores con estado que permiten, p. para almacenar el rtree en una memoria compartida usando Boost.Interprocess. Y es rápido.

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

Ejemplo rápido:

Probablemente el caso de uso más común es cuando vaya a guardar algunos objetos geométricos en un recipiente y sus cuadros delimitadores con algunos ids en el índice espacial. En caso de Boost.Geometry rtree esto podría tener este aspecto:

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