Finding all the points within a circle in 2D space

Question

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?

Answer 1

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.

Answer 2

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).

Answer 3

You can get speed ups by computing as much outside of the loops as possible. Also there's no need to do the Pythagoras Theorem square root... just keep everything squared. One final speed-up can be made by only doing the math for one quarter of the circle (because it's symmetrical)... when a match is found you just replicate it for the other three quarters.

radiusSquared = radius*radius;
rightEdge = centerX+radius;
bottomEdge = centerY+radius;
for(x = centerX; x <= rightEdge; x++){
    xSquared = x*x;
    for(y = centerY; y <= bottomEdge; y++){
        ySquared = y*y;
        distSquared = xSquared+ySquared;
        if(distSquared <= radiusSquared){
            // Get positions for the other quadrants.
            otherX = centerX-(x-centerX);
            otherY = centerY-(y-centerY);
            // Do something for all four quadrants.
            doSomething(x, y);
            doSomething(x, otherY);
            doSomething(otherX, y);
            doSomething(otherX, otherY);
        }
    }
}

Answer 4

For getting a list of all points within a circle you should use:

var radius = 100, r2 = radius * radius;
var circle = [];
for (var dx = -radius; dx <= radius; dx++) {
  var h = Math.sqrt(r2 - dx * dx) | 0;
  for (var dy = -h; dy <= h; dy++) {
    circle.push([dx, dy])
  }
}

See http://jsperf.com/circles/2 for profiling against the other solutions here.

Answer 5

If the following is true:

( ( xPos - centreX)^2 + (yPos - centreY)^2 ) <= radius^2

where xPos and yPos are the coordinates of a point you're checking, then the point is inside your circle.

Answer 6

seems correct. you can make it slightly faster by finding minY and then doing DoSomething from -rangeY to +rangeY for the current X.

for(dx=0;dx<rad; dx++)
{
  rangeY = 0;
  while (!inside(x, rangeY)) //inside == check if x*x + y*y <r*r
    rangeY++;

  for(y=center-rangeY;y<center+rangeY;y++) 
  {
    DoSomething(centerX - dx, y);
    DoSomething(centerX + dx, y);      }
}

Answer 7

I know this question has an accepted answer, but I have a far easier solution. The other answers confused me, as I did not know what center, xcenter, ycenter were, and the math behind the functions were left unexplained and I trekked out to discover a mathematical solution of my own.

My equation is very simple:

cx is the x point in the center of the circle

cy is the y point in the center of the circle

rad is the radius of the circle

What my equation/function does is calculate the points by calculating each possible point given the radius and it adds and subtracts the offset of cx and cy.

//Creates an array filled with numbers
function range(begin, end) {
    for (var i = begin, arr = []; i < end; i++) {
      arr.push(i);
    }

    return arr;
}

function calculateAllPointsInCircle(cx, cy, rad) {

   var rang = range(-rad, rad + 1);
   var px = [];
   var py = [];
   var xy = [];

   for (var i = 0; i < rang.length; i++) {
     var x = cx + rang[i];
     px.push(x);

     for (var l - rang.length - 1; l > 0; l--) {
        var y = cy + rang[l];
        if (!py.indexOf(y)===-1) { py.push(y); }

        xy.push(x+','+y);
     }
   }

   return {
     x: x,
     y: y,
     xy: xy
   }
}

The performance is much higher than the other answers: http://jsperf.com/point-in-circle/4 You can check my equation with math, using the equation that will validate if a given point is inside a circle x*x + y*y <= r*r OR x^2 + y^2 <= r^2

Edit- Super compressed ES6 version:

function range(begin, end) {
  for (let i = begin; i < end; ++i) {
    yield i;
  }
}

function calculateAllPointsInCircle(cx, cy, rad) {
    return {
        x: [cx + i for (i of range(-rad, rad + 1))],
        y: [cy + i for (i of range(-rad, rad + 1))]
    };
}