Boost logo

Geometry :

Subject: [geometry] [index] rtree iterative queries
From: Adam Wulkiewicz (adam.wulkiewicz_at_[hidden])
Date: 2013-08-28 21:17:00


I've just added query iterators to the rtree. They can be used to
perform iterative queries. Typical use cases:

- pause querying if it takes too long and resume it later,
- stop querying at some point, e.g. when we store bounding boxes of some
   geometries but want to find the nearest geometry, not bounding box.
   The iterative query will iterate through Values which boxes are
   closest to some point. Each iteration we can check if the geometry
   corresponding to the Value is the closest one and break the loop
   when needed.
- do something with only those Values which correspond to geometries
   meeting some predicates, similar to the previous point.
- probably more...

Those iterators may be returned by qbegin() and qend() methods.


Of course there is a catch! The type of iterator returned by those
methods depends on the type of passed Predicates. And to get the end
iterator of the same type as the begin iterator, the predicates must be
passed to the qend().

There is also a no-parameter qend() which return a special
end_query_iterator which may be compared with arbitrary iterator
returned by qbegin() to check if the query has ended. But since it has
different type it can't be used in STL algorithms like std::copy().

But! Additionally in the rtree there is a definition of a type of
type-erased const_query_iterator to which all of the above iterators may
be assigned.

The reason why I just don't return type-erased iterators from qbegin()
and qend() to get rid of qend() taking predicates is that they're
slower. Furthermore the type of the returned iterator may be obtained
using one of C++11 features like decltype or auto or Boost.Typeof library.


// Store the result in the container using std::copy()
// it requires both iterators of the same type

// Store the result in the container using std::copy()
// and type-erased iterators
Rtree::const_query_iterator first = tree.qbegin(bgi::intersects(box));
Rtree::const_query_iterator last = tree.qend();
std::copy(first, last, std::back_inserter(result));

// Boost.Typeof
typedef BOOST_TYPEOF(tree.qbegin(bgi::nearest(pt, 10000))) Iter;
for ( Iter it = tree.qbegin(bgi::nearest(pt, 10000)) ;
       it != tree.qend() ;
       ++it )
     // do something with value
     if ( has_enough_nearest_values() )



Geometry list run by mateusz at