Boost R tree for spatial search

Question

I'm trying to create a boost r tree with packing algorithm that will store 2D geometric points. Just to be clear I don't need a kNN search, but what I need is to find points that are in side of a horizon of the point that is a member of the same r tree (horizon would be a radius). What I've found so far were examples for distance search using a random point (not the point that is a r-tree member). I did a distance and index check using bg::index::satisfies by passing a method that checks if the index is different and is distance smaller than radius. Also I use within(box), but I'm not sure that is the correct way to use r tree spatial search for the point that is a member of the same r tree. Because as far as I understand the point in the r-tree knows has the index of boxes in which it is contained, so wouldn't there be a way to query just the point and the distance and still not ending up searching the whole tree!?

this is my code

#include "stdafx.h"
#include <boost/function_output_iterator.hpp>
#include <boost/geometry/index/rtree.hpp>
#include <boost/geometry.hpp>
#include <boost/geometry/geometries/point.hpp>
#include <boost/geometry/geometries/box.hpp>
#include <vector>
#include <iostream>


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

typedef bg::model::point <double, 2, bg::cs::cartesian> point;
typedef std::pair<point, std::size_t> pointI;
typedef bg::model::box<point> box;
typedef std::pair<point, unsigned> value;

bool CheckIndexAndDist(pointI i, pointI j, size_t dist);

std::vector<uint64_t> res;
struct StoreDataCallback
{
    template <typename Value>
    void operator()(Value const& v)
    {
        res.push_back(v.second);
    }
};


int _tmain(int argc, _TCHAR* argv[])
{
    std::vector<point> contourCenters; // has some value
    std::vector<pointI> cloud;

    int horizon = 3;
    double dX = 0;
    double length = 20;
    double width = 20;
    dX = length/10.0;

    for(int i = 0; i < length; i++)
    {
        for(int j = 0; j < width; j++)
        {
            point p;
            p.set<0>((-1.0 * length / 2.0) + dX  + j * dX);
            p.set<1>((-1.0 * width / 2.0) + dX  + i * dX);
            contourCenters.push_back(p);
        }
    }
    size_t id_gen = 0;
    std::transform(
            contourCenters.begin(), contourCenters.end(),
            back_inserter(cloud), 
            [&](point const& p) { return std::make_pair(p, id_gen++); }
        );

     bgi::rtree<pointI, bgi::quadratic<16> > rtree(cloud);

     // spatial search
    box query_box(point(cloud[10].first.get<0>() - 3.2*dX, cloud[10].first.get<1>() - 3.2*dX),point(cloud[10].first.get<0>() + 3.2*dX, cloud[10].first.get<1>() + 3.2*dX));
    StoreDataCallback callback;


    res.clear();
    rtree.query(
    bgi::within(query_box) &&
    bgi::satisfies([&](value const& v) {return CheckIndexAndDist(v, cloud[10],3.015*dX);}),
    boost::make_function_output_iterator(callback));

    return 0;
}

bool CheckIndexAndDist(pointI i, pointI j, size_t dist)
{
    if( i.second != j.second &&  (bg::distance(i.first, j.first) < dist))
        return true;
    else
        return false;
}

Answer 1

Also I use within(box), but I'm not sure that is the correct way

It's correct, i.e. within predicate is a spatial predicate allowing the R-tree to filter-out the points during the query geometrically and satisfies predicate is checked on top of that. If Boost.Geometry had circle/sphere concept you'd be able to pass it directly into the within predicate and satisfies wouldn't be necessary but since this is not the case you have to pass a box around the circle.

The official interface doesn't support the kind of query you want to perform. In order to do something different you'd have to implement your own R-tree visitor and apply it to the R-tree using boost::geometry::index::detail::rtree::utilities::view. Have a look at this directory for more details.

The R-tree doesn't know where in its structure the point can be found. So if you want to pick one arbitrary point and get all points in some radius around it you'd still have to traverse the R-tree to find where it is in the first place and search around it afterwards. So this kind of searching would have sense if you wanted to perform it for some greater than 1 number of elements contained in the R-tree, because then effectively you'd have to traverse a part of the R-tree but then for each element you'd preform the radius searches locally. The edge case would be doing it for all of the points, traversing the whole R-tree top-down and locally going back up in the R-tree structure for each point to get other points around it.