How to check if any 2d point in boost r-tree is in a given triangle?

Question

How to check if any 2d point in boost r-tree is in a given rectangle? This is the website I was following to know r-tree in boost.

But I'm confused how to check if any point in r-tree lies within a given rectangle. C++ code would be appreciable.

Answer 1

If I understand correctly you'd like to have a rtree containing points and to check if at least one of them intersects a rectangle or triangle. The code below presents how this can be done using spatial queries (rtree::query()) and query iterators (rtree::qbegin() and rtree::qend()).

See also the documentation (http://www.boost.org/libs/geometry), section Spatial Indexes.

I didn't know which compiler you're using so the code below doesn't use any C++11 feature. For instance in C++11 instead of raw loops you could use algorithms like std::find_if() with lambda expressions.

#include <iostream> // to print the results
#include <vector>   // to store the points and results

// only for convenience
#include <boost/foreach.hpp>

// Boost.Geometry headers
#include <boost/geometry.hpp>
#include <boost/geometry/geometries/geometries.hpp>
#include <boost/geometry/index/rtree.hpp>

// convenient namespaces
namespace bg = boost::geometry;
namespace bgi = boost::geometry::index;
// convenient typedefs
typedef bg::model::point<double, 2, bg::cs::cartesian> point_t;
typedef bg::model::box<point_t> box_t;
typedef bg::model::ring<point_t, true, false> ring_t; // clockwise, open
typedef bgi::rtree<point_t, bgi::linear<16> > rtree_t;

int main()
{
    // prepare a container of points
    std::vector<point_t> points;
    points.push_back(point_t(0, 0));
    points.push_back(point_t(1, 1));
    points.push_back(point_t(2, 2));
    points.push_back(point_t(3, 3));

    // build a rtree
    rtree_t rtree(points.begin(), points.end());

    // prepare a triangle (not intersecting any point)
    ring_t triangle;
    bg::append(triangle, point_t(0.5, 0.6));
    bg::append(triangle, point_t(0.5, 1.5));
    bg::append(triangle, point_t(1.4, 1.5));

    // create axis-aligned bounding box of a triangle
    box_t box = bg::return_envelope<box_t>(triangle);

    // using rtree::query()
    // rather naiive approach since all points intersecting a geometry are returned
    {
        // check if at least 1 point intersecting a box was found
        std::vector<point_t> result;
        rtree.query(bgi::intersects(box), std::back_inserter(result));
        bool test = !result.empty();
        std::cout << test << std::endl;
    }
    {
        // check if at least 1 point intersecting a triangle was found
        std::vector<point_t> result;
        rtree.query(bgi::intersects(triangle), std::back_inserter(result));
        bool test = !result.empty();
        std::cout << test << std::endl;
    }
    {
        // check if at least 1 point intersecting a triangle was found
        // similar to the above but should be faster since during a spatial query
        // a box is checked and triangle only if needed
        std::vector<point_t> result;
        rtree.query(bgi::intersects(box), std::back_inserter(result));
        bool test = false;
        BOOST_FOREACH(point_t const& pt, result)
        {
            if ( bg::intersects(pt, triangle) )
            {
                test = true;
                break;
            }
        }
        std::cout << test << std::endl;
    }

    // using iterative queries - rtree::qbegin() and rtree::qend()
    // the query is stopped when the first point is found
    {
        // check if at least 1 point intersecting a box was found
        bool test = rtree.qbegin(bgi::intersects(box)) != rtree.qend();
        std::cout << test << std::endl;
    }
    {
        // check if at least 1 point intersecting a triangle was found
        bool test = rtree.qbegin(bgi::intersects(triangle)) != rtree.qend();
        std::cout << test << std::endl;
    }
    {
        // check if at least 1 point intersecting a triangle was found
        // this version should be faster than the above because a box is checked
        // during the spatial query and triangle only if needed
        bool test = false;
        // for each Point intersecting a box
        for ( rtree_t::const_query_iterator it = rtree.qbegin(bgi::intersects(box)) ;
              it != rtree.qend() ;
              ++it )
        {
            // check if this Point also intersects a triangle
            if ( bg::intersects(triangle, *it) )
            {
                test = true;
                break;
            }
        }
        std::cout << test << std::endl;
    }
}

Answer 2

R-trees only work on rectangles.

If you are storing non-rectangular data in an r-tree, it will only provide you candidates that you then need to check ("verify", "validate", "refine") in more detail.

The whole R-tree idea is approximating objects with the much simpler (efficient to store and manage) geometry of a bounding box, after all.

Maybe the boost libraries provide some helper functionality for this, but likely outside of the rtree package, in the geometry pacakge itself.