Boost logo

Geometry :

Subject: [geometry] rtree nearest query with custom geometries
From: Andrea Beconcini (andrea.beconcini_at_[hidden])
Date: 2019-04-16 10:05:42

Hi everybody,

I am trying to use an rtree as an index to a set of triangles to perform
some spatial queries.
The rtree stores std::pair<box, triangles> where box is the boost geometry

The problem occurs with the nearest query and, in particular, when two or
more elements have equivalent boxes,
 and I look for just one element, the result may be wrong.

Look at the code below; the problem is that the two triangles have
equivalent bounding boxes, and since
the query returns just one element, the result is the one I inserted first.
Even though the bounding boxes
are the same, the two elements are not, I'd like the query to returns t2

I think I need to provide an IndexableGetter to my rtree, but according to
the returned value has to be one of the Indexable concepts (Point, Box, or
Segment) and none of them seems to satisfy
my requirements.

Do I need to make my triangle Indexable? I could not find any reference on
how to do that and what methods are required
for a type to be indexable; can anyone provide any resources that may be

Thanks, Andrea.

#include <boost/geometry.hpp>
#include <boost/geometry/index/rtree.hpp>
#include <boost/geometry/geometries/box.hpp>
#include <boost/geometry/geometries/point.hpp>

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

using point = typename bg::model::point<double, 2, bg::cs::cartesian>;
using box = typename bg::model::box<point>;

bool operator==(point const &a, point const &b)
    using bg::get;
    return get<0>(a) == get<0>(b) && get<1>(a) == get<1>(b);

struct triangle
    point a;
    point b;
    point c;

    bool operator==(triangle const &other) const
        return a == other.a && b == other.b && c == other.c;

int main()
    using indexed_t = typename std::pair<box, triangle>;
    using RTree = boost::geometry::index::rtree<indexed_t,

    triangle t1{point{0, 0}, point{1, 0}, point{1, 1}};
    box b1{point{0, 0}, point{1, 1}};

    triangle t2{point{0, 0}, point{1, 1}, point{0, 1}};
    box b2{point{0, 0}, point{1, 1}};

    RTree rtree;
    rtree.insert({b1, t1});
    rtree.insert({b2, t2});

    auto it = rtree.qbegin(bgi::nearest(point(-1, 0.5), 1));

    assert(it->second == t2); // this fails
    return 0;

Geometry list run by mateusz at