C ++ R - implementazione albero ha voluto [chiusa]

Question

Qualcuno sa una buona e semplice da usare per l'attuazione R-tree codice di produzione? (In realtà, qualsiasi implementazioni - R*, R+ o PR-tree sarebbe grande)

Non importa se si tratta di un modello o di attuazione biblioteca, ma alcune implementazioni che Google ha trovato aspetto molto deludente ...

Answer 1

Codice di controllo R-alberi su http://www.superliminal.com/sources/sources. htm

anche controllare

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

Answer 2

Si può anche controllare il R-tree varianti fornito dalla libreria Boost.Geometry:

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

R-tree attuazione Boost.Geometry consente di memorizzare valori di tipo arbitrario nell'indice spaziale e l'esecuzione di query complesse. Parametri come elementi di nodo massimo possono essere passati come parametri di compilazione o run-time. Supporta C ++ 11 semantica move emulati anche su 11 compilatori grazie a Boost.Move pre-C ++. Supporta anche allocatori con stato che consente ad esempio per memorizzare la R-tree in una memoria condivisa utilizzando Boost.Interprocess. Ed è veloce.

Sul rovescio della medaglia, attualmente memoria persistente non è ancora supportato quindi se avete bisogno di più di in-memory indice spaziale probabilmente si dovrebbe verificare una delle altre librerie citate.

Esempio rapida:

Probabilmente il più caso d'uso comune è quando si memorizzano alcuni oggetti geometrici in un contenitore e le loro scatole di delimitazione con alcuni ids nell'indice spaziale. In caso di Boost.Geometry R-tree questa potrebbe essere la seguente:

#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

ho aggiornato l'implementazione trovata in http://www.superliminal.com/sources/sources.htm per supportare una gamma più ampia di tipi di dati.

Si possono trovare la mia versione su github: https://github.com/nushoin/RTree

La versione originale è di dominio pubblico, come è mio.

Answer 4

spatialindex fornisce un'interfaccia piacevole per diversi tipi di strutture di indice spaziale (e spazio-temporali) tra cui R, R *, alberi TPR a http://libspatialindex.github.com/