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?
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:
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.