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

309

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?

Jason
la source
20
Cette question est vraiment indépendante du langage, j'utilise la même formule en java, donc le ré-étiquetage.
Gautam
Il semble que vous supposiez uniquement des coordonnées positives. Les solutions ci-dessous ne fonctionnent pas avec des coordonnées signées.
cjbarth
La plupart des solutions ci - dessous fonctionnent avec des coordonnées positives et négatives. Juste corriger cette friandise pour les futurs téléspectateurs de cette question.
William Morrison
Je vote pour clore cette question comme hors sujet car elle concerne les mathématiques au collège plutôt que la programmation.
n. «pronoms» m.

Réponses:

481

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.

Jason
la source
6
Cela peut aider des gens moins soucieux des mathématiques à voir l'opération de racine carrée utilisée pour mesurer la distance par rapport au rayon. Je me rends compte que ce n'est pas optimal, mais comme votre réponse est plus formatée comme une équation que du code, cela a peut-être plus de sens? Juste une suggestion.
William Morrison
30
C'est l'explication la plus compréhensible fournie en une simple phrase et une équation immédiatement utilisable. Bien joué.
thgc
c'est un grand souhait que j'aurais trouvé cette ressource plus rapidement. D'où vient la valeur x?
Devin Tripp
2
@DevinTripp 'x' est la coordonnée x du point testé.
Chris
5
Cela peut être évident, mais il convient de préciser qu'il <=trouvera des points à l'intérieur du cercle ou sur son bord.
Tyler
131

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);
}
philcolbourn
la source
5
Cette réponse est excellente. Je n'avais jamais réalisé certaines des optimisations que vous proposez. Bien joué.
William Morrison
2
Je suis curieux de savoir si vous avez profilé ces optimisations? Mon intuition est que plusieurs conditionnelles seraient plus lentes que certaines mathématiques et une conditionnelle, mais je peux me tromper.
yoyo
3
@yoyo, je n'ai effectué aucun profilage - cette question concerne une méthode pour n'importe quel langage de programmation. Si quelqu'un pense que cela pourrait améliorer les performances de son application, il devrait, comme vous le suggérez, démontrer que c'est plus rapide dans les scénarios normaux.
philcolbourn
2
En fonction, inCircleNvous utilisez un ABS inutile. Probablement sans différence ABS entre inCircleet inCircleNserait plus petit.
tzaloga
1
La suppression de l'ABS améliore les performances inCircleN mais pas suffisamment. Cependant, ma méthode était biaisée vers des points plus probables en dehors du cercle depuis R = 1. Avec un rayon aléatoire [0..499], environ 25% des points étaient à l'intérieur du cercle et inCircleN est plus rapide.
philcolbourn
74

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

Konrad Rudolph
la source
1
Remplacez dist <= radius par dist <radius pour tester si le point se trouve à l'intérieur du cercle.
jason
16
sqrt est cher. Évitez-le si possible - comparez les x ^ 2 + y ^ y à r ^ 2.
Paul Tomblin
Jason: nos définitions peuvent être en désaccord, mais pour moi, un point qui se trouve sur la circonférence du cercle se trouve le plus fortement dans le cercle et je suis presque sûr que la mienne est d'accord avec la définition formelle et mathématique.
Konrad Rudolph
3
La définition mathématique formelle de l'intérieur d'un cercle est celle que j'ai donnée dans mon message. De Wikipedia: En général, l'intérieur de quelque chose se réfère à l'espace ou à une partie à l'intérieur de celui-ci, à l'exclusion de tout type de mur ou de limite autour de son extérieur. en.wikipedia.org/wiki/Interior_(topology)
jason
1
En pascal, delphi et FPC, la puissance et sqrt sont trop chers , et il n'y a pas d'opérateur électrique EG: **ou ^. Le meilleur moyen de le faire lorsque vous avez juste besoin x ^ 2 ou x ^ 3 est de le faire « manuellement »: x*x.
JHolta
37
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.

William Morrison
la source
12

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

Jason Punyon
la source
11
Vous pouvez éviter deux appels Sqrt coûteux en comparant le carré D au rayon carré.
Paul Tomblin
10

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
dF.
la source
5

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

la source
4

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");
DEEPAK KUMAR SINGH
la source
4

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

entrez la description de l'image ici

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;
    }
Champion du chou
la source
2

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

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

Daniel Kvist
la source
2

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)) { }
Adam Cox
la source
1

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)
Selrac
la source
0

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



    }
}}

la source
0

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

la source
0

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));
}
graffitiMSX
la source
0

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;
}
Ketan Ramteke
la source
0

PHP

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