Determine points within a given radius algorithm

Question

I'm not sure what mathematical concept this is to support my question. ^^

Let's say we have PointA as the reference. The problem is to find the points around PointA within a given radius (Using coordinates). My approach would be to compute the distance of every point (Pythagorean) and then compare with the given radius. I'm sure that this would suck in terms of complexity.

What algorithm may you suggest? A sample code to point things out would be much appreciated. Thanks.

Tifanytiff

You want a function that will return every integer coordinate pair that is less than a certain distance from a given coordinate pair? Or you have a set of objects floating around and you want to know which ones are inside the radius? – Casteel

You might want to look at this SO answer: #1319095 – Casteel

Answer 1

I'd start by creating a box around the circle and first testing if anything falls inside the box. Then you're probably avoiding calculating sqrts and squares all the time. Pick one edge of the box (say the one at the left side) and calculate its x value:

xMin = xOrigin - radius

Then anything that satifies

xTest < xMin

can be ignored. Repeat something similar for all four sides. The moment that a test fails, then stop working on that point. Don't do unnecessary calculations.

This tells you that a point is close but not necessarily within the radius. Next calculate:

abs(sqr(xOrigin - xTest) - sqr(yOrigin - yTest))

if this is less than radius*radius (which you pre-calculate to avoid using square roots) then you have a point within the radius.

That's the best I can figure with first pre-structuring the data.

Firmament

Answer 2

If your points are not indexed, that's actually an optimal algorithm. There are n points, and it'll take O(n) time to search all of them, in the absence of any other index.

The one micro-optimization is to skip the sqrt operation and compare the sum of the squares of the coordinate deltas with the square of the desired radius.

IF you're going to be making multiple queries against the same data set, there are various indexing schemes that you can use that take some time to compute (O(n log n)), but make the lookups faster (O(m + log n), where m is the number of points found.)

kd-trees are probably the place to start there.

Syck

I would like to add that you can only skip the sqrt operation if you are confident the coordinates are all less than sqrt(DBL_MAX)., which is usually the case. The numerically stable way of computing Euclidean distance will not overflow unless the resulting distance overflows. – Killing

@Syck I know this is an old question.. but how would you index these points? Thanks. – Ringler

Answer 3

Your only complexity here is the calculation of distance. Just sieve and simplify that calculation and you are optimal.

If your 'centre' is A(x,y), then for any point B(x1, y1) consider:

1/ If B is within your required distance d of point B, then it follows that both x-x1 < d and y-y1 < d. Check these conditions first to filter any 'low hanging fruit' exclusions.

2/ Rather than calculate the distance, calculate the square of the distance and compare it to the square of the maximum allowed distance (which you should obviously precalculate and reference, rather than recalculate every time). It means not having to compute a square root for each point.

These are quite minor optimisations, but assuming that the points are unsorted and random this is the best you will get.

Astigmia

Answer 4

The best answer would depend on the number of dimensions. I assume you work in 2D or 3D space.

A simple approach would be to make a uniform grid of cell size, say "R". Then pin all points to their respective cells.

Each query point intersects only a handful of cells, say 9. You need to inspect only the intersecting cells, then.

A more efficient approach would be to construct a quadtree or KD-tree (there are plenty of other options but for 2D, quadree or KD-tree would do).

Checking circle-rectangle intersection is necessary with hierarchical structures, but this is described in KD-Tree nearest neighbor algorithm (you only need to modify it slightly).

If you are really concerned about performance, it is possible to construct multiple grids (shifted or rotated) and always select the one with the cell most centered on the point so that the search is limited to the least number of cells.

Acetous