how to construct a RTree using given data points

Question

I need to construct a R tree using given data points.I have searched for implementation of R tree.All the implementation i found construct r tree when given coordinates of rectangle as input.I need to construct r tree when given data points itself(it can be 1 dimensional).The code should take care of creating rectangles which encloses these data points and construct r tree.

Answer 1

Use MBRs (Minimum bounding rectangle) with min = max = coordinate. They all do it this way. Good implementations will however store point data with approximately twice the capacity in the leaves than in directory nodes.

Answer 2

If you're looking for a C++ implementation, the one contained in Boost.Geometry currently (Boost. 1.57) is able to store Points, Boxes and Segments. The obvious advantage is that the data in leafs of the tree is not duplicated which means that less memory is used, caching is better, etc. The usage looks like this:

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