How to build RTree using data point data

Question

I need to build an R tree using data point data. I was looking for an implementation of the R. I need to create an r-tree when the data itself will be displayed (it can be 1-dimensional). The code should take care of creating rectangles that enclose these data points and build an r-tree.

Answer 1

Use the MBR ( Minimum Bounding Rectangle ) with min = max = coordinate. Everyone does it like that. However, good implementations store point data about two times higher than in directory nodes.

Answer 2

If you are looking for an implementation in C ++, then Boost.Geometry currently (Boost 1.57) can store points, Boxes and segments. The obvious advantage is that the data in the leaves of the tree is not duplicated, which means that less memory is used, better caching, etc. Usage is as follows:

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

Answer 3

I assume that using Rtree to store points seems wrong. Although such a structure is indicated for storing spatial data, after some research, which I just found out, it is best suited for storing nonzero regions of a region (since R refers to a region or rectangle on behalf of). Creating a simple table with a good index should provide better performance for updating and retrieving data. Consider my example below:

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

preferable

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

if you only plan on repeating minLatitude over maxLatitude and minLongitude over maxLongitude for each row to represent points, not rectangles. Although the latter approach will work as expected, Rtrees are suitable for areas of the index rectangle, and using them to store points is a misuse with worse performance. Prefer the index of the connection, as described above.

Further reading: http://www.deepdyve.com/lp/acm/r-trees-a-dynamic-index-structure-for-spatial-searching-ZH0iLI4kb0?key=acm