Boost logo

Boost Users :

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.

> 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, 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:
disjoint == !intersects


Boost-users list run by williamkempf at, kalb at, bjorn.karlsson at, gregod at, wekempf at