Boost geometry rtree find iterator for exact match of box

Question

When inserting a new box into an rtree, I want to first check if an identical box is already in the tree. If it is, I want to just get that value, otherwise I'll need to insert a new value. What is the best (ie most efficient) way to do this?

I can do it by calling nearest(box,1), then checking equality:

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

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

typedef bg::model::point<double, 1, bg::cs::cartesian> TPoint;
typedef bg::model::box<TPoint> TBox;
typedef std::pair<TBox, void*> TPair;
typedef bgi::rtree<TPair, bgi::quadratic<16>> TTree;

TTree::const_query_iterator findExact(const TTree& tree, const TBox& box)
{
    auto it = rtree.qbegin(bgi::nearest(box, 1));
    if(it == rtree.qend() || !bg::equals(it->first, box))
        return rtree.qend();
    return it;
}

Is that really the best (ie most performant) way to do this query?

Answer 1

It is not safe approach. I can easily imagine a situation which may not work:

State of Rtree with 2 boxes before inserting new one:

(0,2) --- (1,2)
  |    b    |
(0,1) --- (1,1)
  |    a    |
(0,0) --- (1,0)

so we have 2 boxes a and b. Now you call nearest prediacte with 1 as the number of results when you try to insert a new input box with the same geometry as a box. distance between input geometry and a is 0, but 0 is also for distance(input,b). nearest is limited to return only one box - which one ? you don't know, if it returns b box, you insert duplicate of a into Rtree.

Safe method can be as follows:

1. get new input box
2. calculate its centroid
3. get ALL boxes from rtree which contain input centroid
4. iterate over returned boxes and call equals function on pair (box from rtee,input box)

To do it you can use contains predicate which uses boost::geometry::within method. As input of contains/within you pass point - centroid, if it is discarded by compiler (i am not sure it can take point), you can extend point-centroid into small box to compile.