Équation pour tester si un point est à l'intérieur d'un cercle

Si vous avez un cercle avec centre (center_x, center_y)et rayon radius, comment testez-vous si un point donné avec des coordonnées se (x, y)trouve à l'intérieur du cercle?

En général, xet ydoit satisfaire (x - center_x)^2 + (y - center_y)^2 < radius^2.

Veuillez noter que les points qui satisfont l'équation ci-dessus avec <remplacé par ==sont considérés comme les points sur le cercle, et les points qui satisfont l'équation ci-dessus avec <remplacé par >sont considérés comme l' extérieur du cercle.

Mathématiquement, Pythagore est probablement une méthode simple comme beaucoup l'ont déjà mentionné.

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

Sur le plan informatique, il existe des moyens plus rapides. Définir:

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

Si un point est plus susceptible d'être en dehors de ce cercle, imaginez un carré tracé autour de lui de telle sorte que ses côtés soient tangents à ce cercle:

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

Imaginez maintenant un diamant carré dessiné à l'intérieur de ce cercle de telle sorte que ses sommets touchent ce cercle:

if dx + dy <= R then 
    return true.

Nous avons maintenant couvert la majeure partie de notre espace et il ne reste qu'une petite zone de ce cercle entre notre carré et le diamant à tester. Ici, nous revenons à Pythagore comme ci-dessus.

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

Si un point est plus susceptible d'être à l' intérieur de ce cercle, inversez l'ordre des 3 premières étapes:

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.

D'autres méthodes imaginent un carré à l'intérieur de ce cercle au lieu d'un diamant, mais cela nécessite un peu plus de tests et de calculs sans avantage de calcul (le carré intérieur et les diamants ont des zones identiques):

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

Mettre à jour:

Pour ceux qui s'intéressent aux performances, j'ai implémenté cette méthode en c et compilé avec -O3.

J'ai obtenu les temps d'exécution par time ./a.out

J'ai implémenté cette méthode, une méthode normale et une méthode fictive pour déterminer le temps système.

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

Il semble donc que cette méthode soit plus efficace dans cette implémentation.

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

Vous pouvez utiliser Pythagore pour mesurer la distance entre votre point et le centre et voir si elle est inférieure au rayon:

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 (pointe du chapeau à Paul)

En pratique, la quadrature est souvent beaucoup moins chère que de prendre la racine carrée et comme nous ne sommes intéressés que par une commande, nous pouvons bien sûr renoncer à prendre la racine carrée:

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

En outre, Jason a noté que cela <=devrait être remplacé par <et, selon l'utilisation, cela pourrait avoir du sensmême si je crois que ce n'est pas vrai au sens mathématique strict. Je me suis trompé.

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

C'est plus efficace et plus lisible. Il évite l'opération coûteuse de racine carrée. J'ai également ajouté une vérification pour déterminer si le point se trouve dans le rectangle englobant du cercle.

La vérification du rectangle n'est pas nécessaire, sauf avec de nombreux points ou de nombreux cercles. Si la plupart des points se trouvent à l'intérieur des cercles, la vérification du rectangle englobant ralentira les choses!

Comme toujours, assurez-vous de considérer votre cas d'utilisation.

Calculez la distance

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

c'est en C # ... convertir pour une utilisation en python ...

Vous devez vérifier si la distance entre le centre du cercle et le point est inférieure au rayon, c.-à-d.

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

Comme indiqué ci-dessus - utilisez la distance euclidienne.

from math import hypot

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

Trouvez la distance entre le centre du cercle et les points donnés. Si la distance entre eux est inférieure au rayon, le point se trouve à l'intérieur du cercle. si la distance entre eux est égale au rayon du cercle, alors le point est sur la circonférence du cercle. si la distance est supérieure au rayon, le point est en dehors du cercle.

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

L'équation ci-dessous est une expression qui teste si un point se trouve dans un cercle donné où xP & yP sont les coordonnées du point, xC & yC sont les coordonnées du centre du cercle et R est le rayon de ce cercle donné.

Si l'expression ci-dessus est vraie, le point se trouve dans le cercle.

Voici un exemple d'implémentation en 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;
    }

Il s'agit de la même solution que celle mentionnée par Jason Punyon , mais elle contient un exemple de pseudo-code et quelques détails supplémentaires. J'ai vu sa réponse après avoir écrit ceci, mais je ne voulais pas supprimer la mienne.

Je pense que le moyen le plus facilement compréhensible est de calculer d'abord la distance entre le centre du cercle et le point. J'utiliserais cette formule:

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

Ensuite, comparez simplement le résultat de cette formule, la distance ( d), avec le radius. Si la distance ( d) est inférieure ou égale au rayon ( r), le point est à l'intérieur du cercle (sur le bord du cercle si det rsont égaux).

Voici un exemple de pseudo-code qui peut facilement être converti en n'importe quel langage de programmation:

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

Où circle_xet circle_yest les coordonnées centrales du cercle, rest le rayon du cercle et xet yest les coordonnées du point.

Ma réponse en C # comme solution complète de copier-coller (non optimisé):

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

Comme indiqué précédemment, pour montrer si le point est dans le cercle, nous pouvons utiliser ce qui suit

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

Pour le représenter graphiquement, nous pouvons utiliser:

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)

J'ai utilisé le code ci-dessous pour des débutants comme moi :).

classe publique 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");
    } 
}



    }
}}

Entrer dans le monde de la 3D si vous voulez vérifier si un point 3D se trouve dans une sphère d'unité vous finissez par faire quelque chose de similaire. Pour travailler en 2D, il suffit d'utiliser des opérations vectorielles 2D.

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

Je sais que c'est à quelques années de la meilleure réponse votée, mais j'ai réussi à réduire le temps de calcul de 4.

Il vous suffit de calculer les pixels à partir du 1/4 du cercle, puis de multiplier par 4.

Voici la solution que j'ai trouvée:

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

int x, y, r;
int mx, c, t;
int dx, dy;
int p;

int main() {
    for (r = 1; r < 128; r++){

        clock_t t; 
        t = clock();

        p = calculatePixels(r);

        t = clock() - t; 
        double time_taken = ((double)t)/CLOCKS_PER_SEC; // in seconds 

        printf( "%d of pixels inside circle with radius %d, took %f seconds to execute \n", p, r, time_taken);
    }
}

int calculatePixels(int r){
    mx = 2 * r;
    c = (mx+1)*(mx+1);
    t = r * r;
    int a = 0;
    for (x = 0; x < r; x++){
      for (y = 0; y < r; y++){
          dx = x-r;
          dy = y-r;
          if ((dx*dx + dy*dy) > t)
              a++;
          else 
              y = r;
      }
    }
    return (c - (a * 4));
}

Voici le code java simple pour résoudre ce problème:

et les mathématiques derrière: /math/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;
}

PHP

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