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

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.