Geometry Boost List: [geometry] rtree nearest query with custom geometries

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
box.

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
instead.

I think I need to provide an IndexableGetter to my rtree, but according to
https://www.boost.org/doc/libs/1_70_0/libs/geometry/doc/html/geometry/spatial_indexes/creation_and_modification.html
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
useful?

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,
boost::geometry::index::rstar<8>>;

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