Hello

 

I am a research student, and I am using the RTree by geometry boost.

 

I am looking for a way to count the number of RTree nodes visited by a query.

For example, assume a short RTree consisting only of a root and leaf nodes. Given a query q, the RTree visits the root, and the n children nodes that intersect with q. Hence, the query should return 1+n.

Can someone suggest a way to do so?

 

In addition, can we separately count the intermediate and leaf nodes visited? So, in the previous example instead of n it would return: 1 intermediate node and n leaf nodes.

There are 4 (2*2) different kinds of queries. So spatial and distance/knn query performed after calling query() member function and iterative spatial and distance/knn query performed by incrementing an iterator returned by qbegin() member function.

I'll show you a quick and dirty way how you could count the nodes during the non-iterative query performed by query() function. To do that you could create some global variables in your code, then include Boost.Geometry and Rtree and increment these variables when a node is traversed. So:

size_t internal_nodes_count, leafs_count;

#include <boost/geomery.hpp>
#include <boost/geomery/index/rtree.hpp>

int main()
{
    // create rtree

    internal_nodes_count = 0;
    leafs_count = 0;
    rtree.query(...);
}

For this to work with spatial query you have to modify your version of Boost.Geometry and increment internal_nodes_count here:
https://github.com/boostorg/geometry/blob/boost-1.76.0/include/boost/geometry/index/detail/rtree/visitors/spatial_query.hpp#L46
and leafs_count here:
https://github.com/boostorg/geometry/blob/boost-1.76.0/include/boost/geometry/index/detail/rtree/visitors/spatial_query.hpp#L67
In case of knn query the places are:
https://github.com/boostorg/geometry/blob/boost-1.76.0/include/boost/geometry/index/detail/rtree/visitors/distance_query.hpp#L139
and
https://github.com/boostorg/geometry/blob/boost-1.76.0/include/boost/geometry/index/detail/rtree/visitors/distance_query.hpp#L233

Have in mind that the number of visited nodes might change in Boost 1.77 and 1.78 because I'm currently modifying the queries.

Adam