(C++) Need to figure out all points within a radius using reg. 2D windows coord. system

Question

Sorry in advance, I'm struggling a bit with how to explain this... :)

Essentially, I've got a typical windows coordinate system (the Top, Left is 0,0). If anybody's familiar with the haversine query, like in SQL, it can get all points in a radius based on latitude and longitude coordinates.

I need something much simpler, but my math skills ain't all up to par! Basically, I've got random points scattered throughout about a 600x400 space. I have a need to, for any X,Y point on the map, run a query to determine how many other points are within a given radius of that one.

If that's not descriptive enough, just let me know!

Answer 1

Use Pythagoras:

distance = sqrt(xDifference^2 + yDifference^2)

Note that '^' in this example means "to the power of" and not C's bitwise XOR operator. In other words the idea is to square both differences.

Answer 2

Straightforward approach:

You can calculate the distance between to points using the Pythagorean theorem:

deltaX = x1 - x2
deltaY = y1 - y2
distance = square root of (deltaX * deltaX + deltaY * deltaY)

Given point x1,y1, do this for every other point (x2,y2) to see if the calculated distance is within (less than or equal to) your radius.

If you want to make it speedier, calculate and store the square of the radius and just compare against (deltaX * deltaX + deltaY * deltaY), avoiding the square root.

Answer 3

Using the equation for a circle:

radius ** 2 = (x - centerX) ** 2 + (y - centerY) ** 2

We want to find if a point (x, y) is inside of the circle. We perform the test using this equation:

radius ** 2 < (x - centerX) ** 2 + (y - centerY) ** 2

// (Or use <= if you want the circumference of the circle to be included as well)

Simply substitute your values into that equation. If it works (the inequality is true), the point is inside of the circle. Otherwise, it isn't.

Answer 4

Before doing the Pythagoras, you could also quickly eliminate any point that falls outside of the square that can fully contain the target circle.

// Is (x1, y1) in the circle defined by center (x,y) and radius r
bool IsPointInCircle(x1, y1, x, y, r)
{
    if (x1 < x-r || x1 > x+r)
       return false;
    if (y1 < y-r || y1 > y+r)
       return false;
    return (x1-x)*(x1-x) + (y1-y)*(y1-y) <= r*r
}

Answer 5

If you only care about relative distance you shouldn't use square root you can do something like:

 rSquared = radius * radius #square the radius
 foreach x, y in Points do
   dX = (x - centerX) * (x - centerX) #delta X
   dY = (y - centerY) * (y - centerY) #delta Y
   if ( dX + dY <= rSquared ) then
     #Point is within Circle
   end
 end