Ecuación para probar si un punto está dentro de un círculo

309

Si tiene un círculo con centro (center_x, center_y)y radio radius, ¿cómo prueba si un punto dado con coordenadas (x, y)está dentro del círculo?

jason
fuente
20
Esta pregunta es realmente independiente del lenguaje, estoy usando la misma fórmula en Java, así que vuelve a etiquetar.
Gautam
Parece que solo estás asumiendo coordenadas positivas. Las siguientes soluciones no funcionan con coordenadas firmadas.
cjbarth
La mayoría de las soluciones a continuación hacen trabajo con coordenadas positivas y negativas. Simplemente corrigiendo ese dato para futuros espectadores de esta pregunta.
William Morrison
Estoy votando para cerrar esta pregunta como fuera de tema porque se trata de matemáticas de secundaria en lugar de programación.
n. 'pronombres' m.

Respuestas:

481

En general, xy ydebe satisfacer (x - center_x)^2 + (y - center_y)^2 < radius^2.

Tenga en cuenta que los puntos que satisfacen la ecuación anterior con <reemplazado por ==se consideran los puntos en el círculo, y los puntos que satisfacen la ecuación anterior con <reemplazado por >se consideran fuera del círculo.

jason
fuente
66
Puede ayudar a algunas personas con menos mentalidad matemática ver la operación de raíz cuadrada utilizada para medir la distancia en comparación con el radio. Me doy cuenta de que eso no es óptimo, pero como su respuesta está formateada más como una ecuación que como un código, ¿quizás tenga más sentido? Sólo una sugerencia.
William Morrison
30
Esta es la explicación más comprensible proporcionada en una simple oración y una ecuación inmediatamente utilizable. Bien hecho.
thgc
Es un gran deseo haber encontrado este recurso más rápido. ¿De dónde viene el valor x?
Devin Tripp
2
@DevinTripp 'x' es la coordenada x del punto que se está probando.
Chris
55
Esto puede ser obvio, pero debe indicarse que <=encontrará puntos dentro del círculo o en su borde.
Tyler
131

Matemáticamente, Pitágoras es probablemente un método simple como muchos ya han mencionado.

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

Computacionalmente, hay formas más rápidas. Definir:

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

Si es más probable que un punto esté fuera de este círculo , imagine un cuadrado dibujado a su alrededor de modo que sus lados sean tangentes a este círculo:

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

Ahora imagine un diamante cuadrado dibujado dentro de este círculo de modo que sus vértices toquen este círculo:

if dx + dy <= R then 
    return true.

Ahora hemos cubierto la mayor parte de nuestro espacio y solo queda una pequeña área de este círculo entre nuestro cuadrado y el diamante que se probará. Aquí volvemos a Pitágoras como arriba.

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

Si es más probable que un punto esté dentro de este círculo , invierta el orden de los primeros 3 pasos:

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.

Los métodos alternativos imaginan un cuadrado dentro de este círculo en lugar de un diamante, pero esto requiere un poco más de pruebas y cálculos sin ventaja computacional (el cuadrado interior y los diamantes tienen áreas idénticas):

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

Actualizar:

Para aquellos interesados ​​en el rendimiento, implementé este método en c, y compilé con -O3.

Obtuve tiempos de ejecución por time ./a.out

Implementé este método, un método normal y un método ficticio para determinar la sobrecarga de tiempo.

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

Entonces, parece que este método es más eficiente en esta implementación.

// 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
fuente
55
Esta respuesta es excelente. Nunca me había dado cuenta de algunas de las optimizaciones que sugieres. Bien hecho.
William Morrison
2
¿Tengo curiosidad por saber si ha perfilado estas optimizaciones? Mi intuición es que múltiples condicionales serían más lentos que algunas matemáticas y uno condicional, pero podría estar equivocado.
yoyo
3
@yoyo, no he realizado ningún perfil: esta pregunta es sobre un método para cualquier lenguaje de programación. Si alguien piensa que esto podría mejorar el rendimiento en su aplicación, entonces, como sugiere, debería demostrar que es más rápido en escenarios normales.
philcolbourn
2
En función inCircleN, está utilizando ABS innecesario. Probablemente sin ABS la diferencia entre inCircley inCircleNsería menor.
tzaloga
1
Quitar el ABS mejora el rendimiento inCircleN pero no lo suficiente. Sin embargo, mi método estaba sesgado hacia puntos más probablemente fuera del círculo ya que R = 1. Con un radio aleatorio [0..499], alrededor del 25% de los puntos estaban dentro del círculo e inCircleN es más rápido.
philcolbourn
74

Puede usar Pitágoras para medir la distancia entre su punto y el centro y ver si es más bajo que el radio:

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

EDITAR (punta de sombrero para Paul)

En la práctica, la cuadratura suele ser mucho más barata que sacar la raíz cuadrada y, dado que solo estamos interesados ​​en hacer un pedido, podemos, por supuesto, renunciar a la raíz cuadrada:

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

Además, Jason señaló que <= debería reemplazarse <y, dependiendo del uso, esto podría tener sentidoaunque creo que no es cierto en el sentido matemático estricto. Estoy corregido.

Konrad Rudolph
fuente
1
Reemplace dist <= radio por dist <radio para probar el punto que está dentro del círculo.
Jason
16
sqrt es caro. Si es posible, evítelo: compare x ^ 2 + y ^ y con r ^ 2.
Paul Tomblin el
Jason: nuestras definiciones pueden estar en desacuerdo, pero para mí, un punto que está en la circunferencia del círculo también está más enfáticamente en el círculo y estoy bastante seguro de que el mío está de acuerdo con la definición matemática formal.
Konrad Rudolph el
3
La definición matemática formal del interior de un círculo es la que di en mi publicación. De Wikipedia: En general, el interior de algo se refiere al espacio o parte dentro de él, excluyendo cualquier tipo de muro o límite alrededor de su exterior. en.wikipedia.org/wiki/Interior_(topology)
jason
1
En pascal, delphi y FPC, tanto power como sqrt son demasiado caros , y no hay un operador de energía EG: **o ^. La forma más rápida de hacerlo cuando sólo se necesita x ^ 2 o x ^ 3 es hacerlo "manualmente": 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;
}

Esto es más eficiente y legible. Evita la costosa operación de raíz cuadrada. También agregué un cheque para determinar si el punto está dentro del rectángulo delimitador del círculo.

La verificación del rectángulo es innecesaria, excepto con muchos puntos o muchos círculos. Si la mayoría de los puntos están dentro de los círculos, la verificación del rectángulo delimitador hará que las cosas sean más lentas.

Como siempre, asegúrese de considerar su caso de uso.

William Morrison
fuente
12

Calcular la distancia

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

eso está en C # ... convertir para usar en python ...

Jason Punyon
fuente
11
Puede evitar dos costosas llamadas Sqrt comparando D cuadrado con radio cuadrado.
Paul Tomblin el
10

Debe verificar si la distancia desde el centro del círculo hasta el punto es menor que el radio, es decir

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

Como se dijo anteriormente, use la distancia euclidiana.

from math import hypot

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

fuente
4

Encuentra la distancia entre el centro del círculo y los puntos dados. Si la distancia entre ellos es menor que el radio, entonces el punto está dentro del círculo. Si la distancia entre ellos es igual al radio del círculo, entonces el punto está en la circunferencia del círculo. Si la distancia es mayor que el radio, entonces el punto está fuera del círculo.

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
fuente
4

La siguiente ecuación es una expresión que prueba si un punto está dentro de un círculo dado donde xP e yP son las coordenadas del punto, xC e yC son las coordenadas del centro del círculo y R es el radio de ese círculo dado.

ingrese la descripción de la imagen aquí

Si la expresión anterior es verdadera, entonces el punto está dentro del círculo.

A continuación se muestra una implementación de muestra 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;
    }
Campeón de col
fuente
2

Esta es la misma solución mencionada por Jason Punyon , pero contiene un ejemplo de pseudocódigo y algunos detalles más. Vi su respuesta después de escribir esto, pero no quise eliminar la mía.

Creo que la forma más fácil de entender es calcular primero la distancia entre el centro del círculo y el punto. Yo usaría esta fórmula:

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

Luego, simplemente compare el resultado de esa fórmula, la distancia ( d), con el radius. Si la distancia ( d) es menor o igual que el radio ( r), el punto está dentro del círculo (en el borde del círculo si dyr son iguales).

Aquí hay un ejemplo de pseudocódigo que se puede convertir fácilmente a cualquier lenguaje de programación:

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

Donde circle_xy circle_yes las coordenadas del centro del círculo, res el radio del círculo, y xy yson las coordenadas del punto.

Daniel Kvist
fuente
2

Mi respuesta en C # como una solución completa de cortar y pegar (no optimizada):

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

Uso:

if (!PointIsWithinCircle(3, 3, 3, .5, .5)) { }
Adam Cox
fuente
1

Como se indicó anteriormente, para mostrar si el punto está en el círculo, podemos usar lo siguiente

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

Para representarlo gráficamente podemos usar:

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
fuente
0

Usé el siguiente código para principiantes como yo :).

incirkel de clase pública {

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



    }
}}

fuente
0

Entrando en el mundo de 3D si quieres comprobar si un punto 3D está en una Esfera de Unidad, terminas haciendo algo similar. Todo lo que se necesita para trabajar en 2D es usar operaciones de vectores 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;
    }

fuente
0

Sé que faltan algunos años desde la respuesta mejor votada, pero he logrado reducir el tiempo de cálculo en 4.

Solo necesita calcular los píxeles a partir de 1/4 del círculo, luego multiplicar por 4.

Esta es la solución a la que he llegado:

#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
fuente
0

Aquí está el código simple de Java para resolver este problema:

y las matemáticas detrás de esto: /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
fuente
0

PHP

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