Re: [Boost-users] [geometry] Get points within certain radius?

Subject: Re: [Boost-users] [geometry] Get points within certain radius?
From: Adam Wulkiewicz (adam.wulkiewicz_at_[hidden])
Date: 2017-10-03 20:00:46

Hi Florian,

Florian Lindner Via Boost-users wrote:
> Hello,
>
> first of all thanks for the repliest to my previous geometry question!
>
> What is the best, especially fastest way to get all points within a certain radius of a point?

Since you want all points in some region this is a spatial query, not 
knn query.

> Using the iterator method with nearest(pt, X) highly depends on X. Since I don't know this number, I have to guess it
> rather high.
>
>        for (auto it = rtree.qbegin(bgi::nearest(point, results)) ; it != rtree.qend() ; ++it) {
>          std::ignore = it;
>          break;
>        }
>
> results = 10 => time =    3.0s
> results = 100 => time =  22.6s
> results = 200 => time =  71.4s
> results = 300 => time = 153.2s
>
> though I always use just one result. The loop is inside another loop, not depending on results, so of course, the times
> are multiples of the actual times for that query.
>
> But clearly, choosing high numbers for results is not feasible.

If you only passed the nearest predicate into qbegin (example above) the 
iterator would iterate through all K (results) elements of the rtree. So 
inside this loop you'd have to check if the distance to the current 
element from point is lesser than the radius and break if it was. This 
way you could pass some very big results (e.g. rtree.size()) and get all 
points inside the circle at the end. But this would be emulating spatial 
query with knn query and knn query is slower.

> Another idea is to use the within() query with a circle of a radius. But bg seems to have no circle or sphere model.

There is one in the extensions, so not officially released.
https://github.com/boostorg/geometry/tree/develop/include/boost/geometry/extensions/nsphere

> A workaround would be to use a box instead of a sphere. That means I have to test the results again, whether they are
> actually contained in th sphere.
>
> Alternatively, I could use the satisfies predicate. But wouldn't I give up all spatial information? This predicate needs
> to compare all vertices, don't it? It does include the knowledge, that when one point is discarded, all other points
> with a greater distance will discarded too.
>
> According to https://stackoverflow.com/questions/22909171/boostgeometry-nearest-neighbors-using-a-circle, the way to go
> seems to be to combine within(boundingBox) and satisfies().

Yes, within && satisfies would do the trick and should be faster than 
knn iterative query with distance check and break (mentioned above).

> Any other ideas?

When e.g. bgi::intersects() predicate is passed into the query 
bg::intersects() is called internally for bounding boxes of nodes of the 
rtree and indexables of values stored in the rtree. So you could also 
implement your circle/sphere class and then overload bg::intersects(Box, 
Sphere) and bg::intersects(Point, Sphere) if needed (if you store Points 
in the rtree). This way during the query your overloads would be called.

See e.g. how disjoint() is implemented for NSphere in the extensions: 
https://github.com/boostorg/geometry/blob/develop/include/boost/geometry/extensions/nsphere/algorithms/disjoint.hpp
disjoint == !intersects

Adam