Equation for testing if a point is inside a circle

Solution 1:

In general, x and y must satisfy (x - center_x)² + (y - center_y)² < radius².

Please note that points that satisfy the above equation with < replaced by == are considered the points on the circle, and the points that satisfy the above equation with < replaced by > are considered the outside the circle.

Solution 2:

Mathematically, Pythagoras is probably a simple method as many have already mentioned.

(x-center_x)^2 + (y - center_y)^2 < radius^2

Computationally, there are quicker ways. Define:

dx = abs(x-center_x)
dy = abs(y-center_y)
R = radius

If a point is more likely to be outside this circle then imagine a square drawn around it such that it's sides are tangents to this circle:

if dx>R then 
    return false.
if dy>R then 
    return false.

Now imagine a square diamond drawn inside this circle such that it's vertices touch this circle:

if dx + dy <= R then 
    return true.

Now we have covered most of our space and only a small area of this circle remains in between our square and diamond to be tested. Here we revert to Pythagoras as above.

if dx^2 + dy^2 <= R^2 then 
    return true
else 
    return false.

If a point is more likely to be inside this circle then reverse order of first 3 steps:

if dx + dy <= R then 
    return true.
if dx > R then 
    return false.
if dy > R 
    then return false.
if dx^2 + dy^2 <= R^2 then 
    return true
else
    return false.

Alternate methods imagine a square inside this circle instead of a diamond but this requires slightly more tests and calculations with no computational advantage (inner square and diamonds have identical areas):

k = R/sqrt(2)
if dx <= k and dy <= k then 
    return true.

Update:

For those interested in performance I implemented this method in c, and compiled with -O3.

I obtained execution times by time ./a.out

I implemented this method, a normal method and a dummy method to determine timing overhead.

Normal: 21.3s This: 19.1s Overhead: 16.5s

So, it seems this method is more efficient in this implementation.

// compile gcc -O3 <filename>.c
// run: time ./a.out

#include <stdio.h>
#include <stdlib.h>

#define TRUE  (0==0)
#define FALSE (0==1)

#define ABS(x) (((x)<0)?(0-(x)):(x))

int xo, yo, R;

int inline inCircle( int x, int y ){  // 19.1, 19.1, 19.1
  int dx = ABS(x-xo);
  if (    dx >  R ) return FALSE;
  int dy = ABS(y-yo);
  if (    dy >  R ) return FALSE;
  if ( dx+dy <= R ) return TRUE;
  return ( dx*dx + dy*dy <= R*R );
}

int inline inCircleN( int x, int y ){  // 21.3, 21.1, 21.5
  int dx = ABS(x-xo);
  int dy = ABS(y-yo);
  return ( dx*dx + dy*dy <= R*R );
}

int inline dummy( int x, int y ){  // 16.6, 16.5, 16.4
  int dx = ABS(x-xo);
  int dy = ABS(y-yo);
  return FALSE;
}

#define N 1000000000

int main(){
  int x, y;
  xo = rand()%1000; yo = rand()%1000; R = 1;
  int n = 0;
  int c;
  for (c=0; c<N; c++){
    x = rand()%1000; y = rand()%1000;
//    if ( inCircle(x,y)  ){
    if ( inCircleN(x,y) ){
//    if ( dummy(x,y) ){
      n++;
    }
  }
  printf( "%d of %d inside circle\n", n, N);
}

Solution 3:

You can use Pythagoras to measure the distance between your point and the centre and see if it's lower than the radius:

def in_circle(center_x, center_y, radius, x, y):
    dist = math.sqrt((center_x - x) ** 2 + (center_y - y) ** 2)
    return dist <= radius

EDIT (hat tip to Paul)

In practice, squaring is often much cheaper than taking the square root and since we're only interested in an ordering, we can of course forego taking the square root:

def in_circle(center_x, center_y, radius, x, y):
    square_dist = (center_x - x) ** 2 + (center_y - y) ** 2
    return square_dist <= radius ** 2

Also, Jason noted that <= should be replaced by < and depending on usage this may actually make sense even though I believe that it's not true in the strict mathematical sense. I stand corrected.

Solution 4:

boolean isInRectangle(double centerX, double centerY, double radius, 
    double x, double y)
{
        return x >= centerX - radius && x <= centerX + radius && 
            y >= centerY - radius && y <= centerY + radius;
}    

//test if coordinate (x, y) is within a radius from coordinate (center_x, center_y)
public boolean isPointInCircle(double centerX, double centerY, 
    double radius, double x, double y)
{
    if(isInRectangle(centerX, centerY, radius, x, y))
    {
        double dx = centerX - x;
        double dy = centerY - y;
        dx *= dx;
        dy *= dy;
        double distanceSquared = dx + dy;
        double radiusSquared = radius * radius;
        return distanceSquared <= radiusSquared;
    }
    return false;
}

This is more efficient, and readable. It avoids the costly square root operation. I also added a check to determine if the point is within the bounding rectangle of the circle.

The rectangle check is unnecessary except with many points or many circles. If most points are inside circles, the bounding rectangle check will actually make things slower!

As always, be sure to consider your use case.

Solution 5:

You should check whether the distance from the center of the circle to the point is smaller than the radius

using Python

if (x-center_x)**2 + (y-center_y)**2 <= radius**2:
    # inside circle