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