C++ R - Baumimplementierung gesucht

Question

Kennt jemand eine gute und einfache in Produktionscode R-tree Implementierung zu verwenden? (Eigentlich alle Implementierungen - R*, R+ oder PR-tree wäre toll)

Es spielt keine Rolle, ob es sich um eine Vorlage oder Bibliothek Implementierung ist, aber einige Implementierungen, die Google sehen sehr enttäuschend ...

Answer 1

prüfen R- Bäume Code auf http://www.superliminal.com/sources/sources.htm

überprüfen auch

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

Answer 2

ich die Umsetzung ingefunden aktualisiert 210 um eine breitere Palette von Datentypen zu unterstützen. https://github.com/nushoin/RTree

Die ursprüngliche Version ist public domain, wie meins:

Sie können meine Version auf GitHub finden.

Answer 3

spatialindex bietet eine schöne Oberfläche, um verschiedene Arten von räumlichen (und räumlich-zeitlichen) Indexstrukturen einschließlich R, R *, TPR Bäume bei http://libspatialindex.github.com/

Answer 4

Sie auch die RTREE Check-out von der Boost.Geometry vorgesehen Varianten Bibliothek:

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

Boost.Geometry RTREE Implementierung erlaubt Werten beliebigen Typs in den räumlichen Index und Durchführen einer komplexen Abfragen speichert. Parameter wie maximale Knotenelemente können als Kompilier- oder Laufzeitparameter übergeben werden. Es unterstützt C++ 11 move-Semantiken, die dank Boost.Move auch auf Pre-C++ 11-Compilern emuliert werden. Es unterstützt auch Stateful Allokatoren, die z.B. um den Baum in einem gemeinsamen Speicher mit Boost.Interprocess zu speichern. Und es ist schnell.

Auf der anderen Seite wird momentan persistenter Speicher noch nicht unterstützt. Wenn Sie also mehr als den spatialen In-Memory-Index benötigen, sollten Sie wahrscheinlich eine der anderen erwähnten Bibliotheken überprüfen.

Schnell Beispiel:

Der wohl häufigste Anwendungsfall ist, wenn Sie einige geometrischen Objekte in einem Container speichern und ihre Begrenzungskästen mit einigen ids im räumlichen Index. Im Falle von Boost.Geometry RTREE könnte dies wie folgt aussehen:

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