cómo construir un RTree usando los puntos de datos dados

Question

Necesito construir un árbol R usando puntos de datos dados.He buscado la implementación del árbol R.Toda la implementación encontré construir el árbol r cuando me dieron coordenadas de rectángulo como entrada .Necesito construir r tree cuando se le dan puntos de datos en sí (puede ser de 1 dimensión). El código debe encargarse de crear rectángulos que encierren estos puntos de datos y construyan r tree.

Answer 1

Usa los MBR (Minimum bounding rectangle) con min = max = coordenada. Todos lo hacen de esta manera. Sin embargo, las buenas implementaciones almacenarán datos de puntos con aproximadamente el doble de la capacidad en las hojas que en los nodos de directorio.

Answer 2

Supongo que usar un Rtree para almacenar puntos parece un mal uso. Aunque este tipo de estructura está indicada para almacenar datos espaciales, después de algunas investigaciones descubrí que es la más adecuada para almacenar regiones de área distinta de cero (ya que la R del nombre es para Región o Rectángulo). Crear una tabla simple con un buen índice debería ofrecer un mejor rendimiento, ya sea para actualizar y buscar datos. Considero que mi ejemplo a continuación:

CREATE TABLE locations (id, latitude, longitude); 
CREATE INDEX idx_locations ON locations (latitude, longitude); 

es preferible sobre

CREATE VIRTUAL TABLE locations USING rtree(id, minLatitude, maxLatitude, minLongitude, maxLongitude); 

si la intención es repetir minLatitude sobre maxLatitude y minLongitude sobre maxLongitude para cada fila como para representar puntos y no rectángulos. Aunque este último enfoque funcionará como se espera, los Rtrees son adecuados para indexar áreas rectangulares y usarlas para almacenar puntos es un mal uso con el peor rendimiento. Prefiere un índice compuesto como el anterior.

Más información: http://www.deepdyve.com/lp/acm/r-trees-a-dynamic-index-structure-for-spatial-searching-ZH0iLI4kb0?key=acm

Answer 3

Si usted está buscando una aplicación C++, la contenida en Boost.Geometry actualmente (. Boost 1.57) es capaz de almacenar puntos, Cajas y segmentos. La ventaja obvia es que los datos en las hojas del árbol no se duplique lo que significa que se utiliza menos memoria, el almacenamiento en caché es mejor, etc. El uso es el siguiente:

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

#include <vector> 

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

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

    // a container of points 
    std::vector<point> points; 

    // create the rtree 
    bgi::rtree< point, bgi::linear<16> > rtree(points.begin(), points.end()); 

    // insert some additional points 
    rtree.insert(point(/*...*/)); 
    rtree.insert(point(/*...*/)); 

    // find points intersecting a box 
    std::vector<point> query_result; 
    rtree.query(bgi::intersects(box(/*...*/)), std::back_inserter(query_result)); 

    // do something with the result 
}