Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

Finding all the points within a circle in 2D space

I am representing my 2D space (consider a window), where each pixel is shown as a cell in a 2D array. i.e. a 100x100 window is represented by the array of same dimensions.

Now given a point in the window, if I draw a circle of radius r, I want to find all the points lying in that circle.

I was thinking I'd check for the each point in the square region around the radius, with side = 2*r, if it lies in the circle or not. I'll use the normal distance formula maybe?

Hence, maybe the following:

for (x=center-radius ; x<center+radius ; x++){
    for (y=center-radius ; y<center+radius; y++) {
        if (inside) {
            // Do something
        }
    }
}

Will it serve my purpose? Can I make it faster?

like image 404
Kraken Avatar asked Apr 06 '13 21:04

Kraken


People also ask

How do you find all points in a circle?

Distance Formula for a Point and the Center of a Circle: d=√(x−h)2+(y−k)2 d = ( x − h ) 2 + ( y − k ) 2 , where (x, y) is the point and (h,k) is the center of the circle. This formula is derived from the Pythagorean Theorem.

How do you find the 2d of a circle?

Suppose a circle has a radius 'r' then the area of circle = πr2 or πd2/4 in square units, where π = 22/7 or 3.14, and d is the diameter. Area of a circle can be calculated by using the formulas: Area = π × r2, where 'r' is the radius. Area = (π/4) × d2, where 'd' is the diameter.

How do you find if a point lies inside a circle?

If the distance is greater than the radius, the point lies outside. If it's equal to the radius, the point lies on the circle. And if it's less than the radius, you guessed it right, the point will lie inside the circle. As simple as that!


2 Answers

Will it serve my purpose?

For your 100x100, yes.

Can I make it faster?

Yes. For example, you can:

  • Check only 1 quadrant and get other points because of symmetry.
  • Skip the square root when calculating the distance.

Code:

for (x = xCenter - radius ; x <= xCenter; x++)
{
    for (y = yCenter - radius ; y <= yCenter; y++)
    {
        // we don't have to take the square root, it's slow
        if ((x - xCenter)*(x - xCenter) + (y - yCenter)*(y - yCenter) <= r*r) 
        {
            xSym = xCenter - (x - xCenter);
            ySym = yCenter - (y - yCenter);
            // (x, y), (x, ySym), (xSym , y), (xSym, ySym) are in the circle
        }
    }
}

That's about 4x speed up.

JS tests for solutions presented here. Symmetry is the fastest on my computer. Trigonometry presented by Niet the Dark Absol is very clever, but it involves expensive mathematical functions like sin and acos, which have a negative impact on performance.

like image 138
Adam Stelmaszczyk Avatar answered Oct 02 '22 20:10

Adam Stelmaszczyk


You can bypass the need for a conditional check:

for(x=center-radius; x<center+radius; x++) {
    yspan = radius*sin(acos((center-x)/radius));
    for(y=center-yspan; y<center+yspan; y++) {
        // (x,y) is inside the circle
    }
}

If needed, you can round(yspan).

like image 33
Niet the Dark Absol Avatar answered Oct 02 '22 20:10

Niet the Dark Absol