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

Subject: [Boost-users] [geometry] Get points within certain radius?
From: Florian Lindner (mailinglists_at_[hidden])
Date: 2017-10-03 05:07:41

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?

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.

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

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().

Any other ideas?

Thanks,
Florian