CODEWITHSUNDEEP
c++algorithmvisual-c++
Cyprus106
Cyprus106

Reputation: 5780

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

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!

Upvotes: 2

Views: 2697

Answers (5)

Francisco Canedo
Francisco Canedo

Reputation: 2010

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.

Upvotes: 4

Eclipse
Eclipse

Reputation: 45493

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
}

Upvotes: 5

JonBWalsh
JonBWalsh

Reputation: 321

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

Upvotes: 2

Ateş G&#246;ral
Ateş G&#246;ral

Reputation: 140050

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.

Upvotes: 12

strager
strager

Reputation: 90012

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.

Upvotes: 1

Related Questions