By directedition


2009-01-26 20:07:26 8 Comments

If you have a circle with center (center_x, center_y) and radius radius, how do you test if a given point with coordinates (x, y) is inside the circle?

16 comments

@DEEPAK KUMAR SINGH 2016-07-06 07:31:04

Find the distance between the center of the circle and the points given. If the distance between them is less than the radius then the point is inside the circle. if the distance between them is equal to the radius of the circle then the point is on the circumference of the circle. if the distance is greater than the radius then the point is outside the circle.

int d = r^2 - ((center_x-x)^2 + (center_y-y)^2);

if(d>0)
  print("inside");
else if(d==0)
  print("on the circumference");
else
  print("outside");

@dF. 2009-01-26 20:10:54

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

@Sadee 2019-12-16 14:47:36

PHP

if ((($x - $center_x) ** 2 + ($y - $center_y) ** 2) <=  $radius **2) {
    return true; // Inside
} else {
    return false; // Outside
}

@Cabbage Champion 2019-06-28 18:08:12

The equation below is a expression that tests if a point is within a given circle where xP & yP are the coordinates of the point, xC & yC are the coordinates of the center of the circle and R is the radius of that given circle.

enter image description here

If the above expression is true then the point is within the circle.

Below is a sample implementation in C#:

    public static bool IsWithinCircle(PointF pC, Point pP, Single fRadius){
        return Distance(pC, pP) <= fRadius;
    }

    public static Single Distance(PointF p1, PointF p2){
        Single dX = p1.X - p2.X;
        Single dY = p1.Y - p2.Y;
        Single multi = dX * dX + dY * dY;
        Single dist = (Single)Math.Round((Single)Math.Sqrt(multi), 3);

        return (Single)dist;
    }

@Ketan Ramteke 2018-11-17 16:26:23

Here is the simple java code for solving this problem:

and the math behind it : https://math.stackexchange.com/questions/198764/how-to-know-if-a-point-is-inside-a-circle

boolean insideCircle(int[] point, int[] center, int radius) {
    return (float)Math.sqrt((int)Math.pow(point[0]-center[0],2)+(int)Math.pow(point[1]-center[1],2)) <= radius;
}

@user5747799 2017-11-16 03:11:06

Moving into the world of 3D if you want to check if a 3D point is in a Unit Sphere you end up doing something similar. All that is needed to work in 2D is to use 2D vector operations.

    public static bool Intersects(Vector3 point, Vector3 center, float radius)
    {
        Vector3 displacementToCenter = point - center;

        float radiusSqr = radius * radius;

        bool intersects = displacementToCenter.magnitude < radiusSqr;

        return intersects;
    }

@Adam Cox 2017-01-21 21:21:54

My answer in C# as a complete cut & paste (not optimized) solution:

public static bool PointIsWithinCircle(double circleRadius, double circleCenterPointX, double circleCenterPointY, double pointToCheckX, double pointToCheckY)
{
    return (Math.Pow(pointToCheckX - circleCenterPointX, 2) + Math.Pow(pointToCheckY - circleCenterPointY, 2)) < (Math.Pow(circleRadius, 2));
}

Usage:

if (!PointIsWithinCircle(3, 3, 3, .5, .5)) { }

@Selrac 2016-09-15 12:52:01

As stated previously, to show if the point is in the circle we can use the following

if ((x-center_x)^2 + (y - center_y)^2 < radius^2) {
    in.circle <- "True"
} else {
    in.circle <- "False"
}

To represent it graphically we can use:

plot(x, y, asp = 1, xlim = c(-1, 1), ylim = c(-1, 1), col = ifelse((x-center_x)^2 + (y - center_y)^2 < radius^2,'green','red'))
draw.circle(0, 0, 1, nv = 1000, border = NULL, col = NA, lty = 1, lwd = 1)

@William Morrison 2011-06-10 20:01:06

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.

@Daniel Kvist 2015-06-09 14:35:55

This is the same solution as mentioned by Jason Punyon, but it contains a pseudo-code example and some more details. I saw his answer after writing this, but I didn't want to remove mine.

I think the most easily understandable way is to first calculate the distance between the circle's center and the point. I would use this formula:

d = sqrt((circle_x - x)^2 + (circle_y - y)^2)

Then, simply compare the result of that formula, the distance (d), with the radius. If the distance (d) is less than or equal to the radius (r), the point is inside the circle (on the edge of the circle if d and r are equal).

Here is a pseudo-code example which can easily be converted to any programming language:

function is_in_circle(circle_x, circle_y, r, x, y)
{
    d = sqrt((circle_x - x)^2 + (circle_y - y)^2);
    return d <= r;
}

Where circle_x and circle_y is the center coordinates of the circle, r is the radius of the circle, and x and y is the coordinates of the point.

@user5560892 2015-11-14 23:37:36

I used the code below for beginners like me :).

public class incirkel {

public static void main(String[] args) {
    int x; 
    int y; 
    int middelx; 
    int middely; 
    int straal; {

// Adjust the coordinates of x and y 
x = -1;
y = -2;

// Adjust the coordinates of the circle
middelx = 9; 
middely = 9;
straal =  10;

{
    //When x,y is within the circle the message below will be printed
    if ((((middelx - x) * (middelx - x)) 
                    + ((middely - y) * (middely - y))) 
                    < (straal * straal)) {
                        System.out.println("coordinaten x,y vallen binnen cirkel");
    //When x,y is NOT within the circle the error message below will be printed
    } else {
        System.err.println("x,y coordinaten vallen helaas buiten de cirkel");
    } 
}



    }
}}

@philcolbourn 2011-08-29 07:00:05

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);
}

@William Morrison 2013-07-21 09:26:11

This answer is excellent. I'd never realized some of the optimizations you suggest. Well done.

@yoyo 2014-06-11 17:04:28

I'm curious to know if you have profiled these optimizations? My gut feeling is that multiple conditionals would be slower than some math and one conditional, but I could be wrong.

@philcolbourn 2014-06-12 06:21:13

@yoyo, I have preformed no profiling - this question is about a method for any programming language. If someone thinks this might improve performance in their application then they should, as you suggest, demonstrate it is faster in normal scenarios.

@tzaloga 2016-06-20 10:58:34

In function inCircleN you're using unnecessary ABS. Probably without ABS difference between inCircle and inCircleN would be smaller.

@NemoStein 2016-08-14 16:31:18

@tzaloga is right... Squared values are always positive.

@philcolbourn 2016-08-18 05:53:11

Removing ABS does improve inCircleN performance but not enough. However, my method was biased towards points more likely outside of circle since R=1. With random radius [0..499], about 25% points were inside circle and inCircleN is faster.

@Jan 2017-03-30 08:53:33

Small optimization: when you need to check multiple points in a certain circle of radius r, r*r is constant and can be calculated outside the loop.

@m4s0 2017-06-09 14:43:40

Excellent answer!

@jason 2009-01-26 20:09:56

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

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.

@William Morrison 2013-03-05 18:13:54

It may help some less math minded folks to see the square root operation used to measure distance compared against the radius. I realize that's not optimal, but as your answer is formatted more like an equation than code perhaps it makes more sense? Just a suggestion.

@thgc 2013-10-16 13:09:23

This is the most comprehensible explanation provided in just a simple sentence and a immediately useable equation. Well done.

@Devin Tripp 2015-04-01 08:07:31

this is great wish i would of found this resource quicker. Where does the value x come from?

@Chris 2015-09-09 15:39:11

@DevinTripp 'x' is the x coordinate of the point being tested.

@Tyler 2017-05-09 23:16:02

This may be obvious, but it should be stated that <= will find points inside the circle or on its edge.

@Alesana 2018-03-18 23:20:43

@makinbacon I found it obvious, but the fact that it wasn't mentioned made me wonder if there was something I wasn't thinking of.

@i0cus 2009-01-28 14:45:08

As said above -- use Euclidean distance.

from math import hypot

def in_radius(c_x, c_y, r, x, y):
    return math.hypot(c_x-x, c_y-y) <= r

@Konrad Rudolph 2009-01-26 20:10:33

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.

@jason 2009-01-26 20:17:31

Replace dist <= radius by dist < radius to test for the point being inside the circle.

@Paul Tomblin 2009-01-26 20:20:16

sqrt is expensive. Avoid it if possible - compare the x^2+y^y to r^2.

@Konrad Rudolph 2009-01-26 20:20:37

Jason: our definitions may disagree but for me, a point that is on the circle's circumference is most emphatically also in the circle and I am pretty sure that mine is in agreement with the formal, mathematical definition.

@Konrad Rudolph 2009-01-26 20:22:28

@Paul: That's correct in practice but I wanted to illustrate Pythagoras. Other answers have included this optimization.

@jason 2009-01-26 20:29:18

The formal mathematical definition of the interior of a circle is that which I gave in my post. From Wikipedia: In general, the interior of something refers to the space or part inside of it, excluding any kind of wall or boundary around its outside. en.wikipedia.org/wiki/Interior_(topology)

@JHolta 2013-03-21 03:34:08

In pascal, delphi and FPC, both power, and sqrt is to expensive, and there's no power-operator EG: ** or ^. The fastest way to do it when you just need x^2 or x^3 is to do it "manually": x*x.

@TLama 2013-07-10 08:35:11

@JHolta, why do you think that Delphi's (or FPC's on x86) Sqr power function is expensive ? Sqrt might be, but that's what Konrad mentioned in his update suggested by Paul's comment...

@JHolta 2013-07-10 09:14:34

@TLama i only said that power, and Sqrt is expensive. I did not mention Sqr at all. But I do believe that there is some overhead if you use Sqr, maybe the compiler is smart and solves it (replaces it with x*x to remove the functioncall).

@TLama 2013-07-10 09:22:20

@JHolta, there is no overhead; both Sqr and x*x results to imul instruction ;-)

@Jason Punyon 2009-01-26 20:10:10

Calculate the Distance

D = Math.Sqrt(Math.Pow(center_x - x, 2) + Math.Pow(center_y - y, 2))
return D <= radius

that's in C#...convert for use in python...

@Paul Tomblin 2009-01-26 20:18:52

You can avoid two expensive Sqrt calls by comparing D-squared to radius-squared.

Related Questions

Sponsored Content

30 Answered Questions

[SOLVED] Is floating point math broken?

48 Answered Questions

23 Answered Questions

[SOLVED] Image Processing: Algorithm Improvement for 'Coca-Cola Can' Recognition

27 Answered Questions

[SOLVED] Circle line-segment collision detection algorithm?

7 Answered Questions

[SOLVED] Ukkonen's suffix tree algorithm in plain English

21 Answered Questions

[SOLVED] Generate a random point within a circle (uniformly)

4 Answered Questions

[SOLVED] How do I calculate a point on a circle’s circumference?

5 Answered Questions

[SOLVED] Circle-circle intersection points

14 Answered Questions

[SOLVED] What is the optimal algorithm for the game 2048?

Sponsored Content