Geometry Boost List: Re: [geometry] Getting the number of nodes intersecting a query

From: Adam Wulkiewicz (adam.wulkiewicz_at_[hidden])
Date: 2021-07-28 09:38:09

Hi Panos,

W dniu 28.07.2021 o 10:19, Panagiotis SIMATIS via Geometry pisze:
>
> 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