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.

Answer 1

You might want to look at this SO answer: http://stackoverflow.com/questions/1318595/which-data-structure-is-appropriate-to-query-all-points-within-distance-d-from-p

Answer 2

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 it's 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.

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.