Equação para testar se um ponto está dentro de um círculo

309

Se você possui um círculo com centro (center_x, center_y)e raio radius, como testar se um determinado ponto com coordenadas (x, y)está dentro do círculo?

Jason
fonte
20
Esta questão é realmente independente da linguagem, eu estou usando a mesma fórmula em java, então re-tagging.
Gautam
Parece que você está assumindo apenas coordenadas positivas. As soluções abaixo não funcionam com coordenadas assinadas.
cjbarth
A maioria das soluções a seguir fazer o trabalho com coordenadas positivas e negativas. Apenas corrigindo esse boato para futuros espectadores desta questão.
William Morrison
Estou votando para encerrar esta questão como fora de tópico, porque se trata de matemática do ensino médio e não de programação.
n. 'pronomes' m.

Respostas:

481

Em geral, xe ydeve satisfazer (x - center_x)^2 + (y - center_y)^2 < radius^2.

Por favor, note que os pontos que satisfazem a equação acima, com <substituído por ==são considerados os pontos sobre o círculo, e os pontos que satisfazem a equação acima, com <substituído por >são considerados o lado de fora do círculo.

Jason
fonte
6
Isso pode ajudar algumas pessoas menos preocupadas com matemática a ver a operação de raiz quadrada usada para medir a distância em comparação com o raio. Sei que não é o ideal, mas como sua resposta é formatada mais como uma equação do que código, talvez faça mais sentido? Apenas uma sugestão.
William Morrison
30
Esta é a explicação mais compreensível fornecida em apenas uma frase simples e uma equação imediatamente utilizável. Bem feito.
Thgc # 16/13
este é um grande desejo que eu encontraria este recurso mais rapidamente. De onde vem o valor x?
Devin Tripp
2
@DevinTripp 'x' é a coordenada x do ponto que está sendo testado.
Chris
5
Isso pode ser óbvio, mas deve-se afirmar que <=encontrará pontos dentro do círculo ou em sua borda.
Tyler
131

Matematicamente, Pitágoras é provavelmente um método simples, como muitos já mencionaram.

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

Computacionalmente, existem maneiras mais rápidas. Definir:

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

Se é mais provável que um ponto esteja fora deste círculo , imagine um quadrado desenhado em torno dele, de modo que seus lados sejam tangentes a este círculo:

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

Agora imagine um diamante quadrado desenhado dentro deste círculo, de modo que seus vértices toquem neste círculo:

if dx + dy <= R then 
    return true.

Agora, cobrimos a maior parte do nosso espaço e apenas uma pequena área desse círculo permanece entre o quadrado e o diamante a serem testados. Aqui voltamos a Pitágoras como acima.

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

Se é mais provável que um ponto esteja dentro deste círculo , inverta a ordem dos 3 primeiros passos:

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.

Métodos alternativos imaginam um quadrado dentro deste círculo em vez de um diamante, mas isso requer um pouco mais de testes e cálculos sem vantagem computacional (o quadrado interno e os diamantes têm áreas idênticas):

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

Atualizar:

Para os interessados ​​em desempenho, implementei esse método em ce compilei com -O3.

Eu obtive tempos de execução por time ./a.out

Eu implementei esse método, um método normal e um método fictício para determinar a sobrecarga de tempo.

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

Portanto, parece que esse método é mais eficiente nessa implementação.

// 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
fonte
5
Esta resposta é excelente. Eu nunca tinha percebido algumas das otimizações que você sugere. Bem feito.
William Morrison
2
Estou curioso para saber se você definiu o perfil dessas otimizações? Meu pressentimento é que vários condicionais seriam mais lentos que alguns de matemática e um condicional, mas eu poderia estar errado.
yoyo
3
@ yoyo, eu não fiz nenhum perfil - esta questão é sobre um método para qualquer linguagem de programação. Se alguém acha que isso pode melhorar o desempenho em seu aplicativo, deve, como você sugere, demonstrar que é mais rápido em cenários normais.
philcolbourn
2
Na função, inCircleNvocê está usando ABS desnecessário. Provavelmente sem ABS diferença entre inCirclee inCircleNseria menor.
tzaloga
1
A remoção do ABS melhora o desempenho do inCircleN, mas não o suficiente. No entanto, meu método foi direcionado para pontos mais prováveis ​​fora do círculo desde R = 1. Com raio aleatório [0..499], cerca de 25% dos pontos estavam dentro do círculo e o inCircleN é mais rápido.
philcolbourn
74

Você pode usar Pitágoras para medir a distância entre o ponto e o centro e ver se é menor que o raio:

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 (gorjeta de chapéu para Paul)

Na prática, o quadrado geralmente é muito mais barato do que pegar a raiz quadrada e, como estamos interessados ​​apenas em uma ordem, é claro que podemos deixar de pegar a raiz quadrada:

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

Além disso, Jason observou que <=deve ser substituído <e, dependendo do uso, isso pode realmente fazer sentidoembora eu acredite que isso não seja verdade no sentido matemático estrito. Eu estou corrigido.

Konrad Rudolph
fonte
1
Substitua dist <= raio por dist <raio para testar o ponto que está dentro do círculo.
jason
16
sqrt é caro. Evite-o, se possível - compare x ^ 2 + y ^ y com r ^ 2.
22620 Paul Tomblin
Jason: nossas definições podem discordar, mas para mim, um ponto que está na circunferência do círculo é enfaticamente também no círculo e tenho certeza de que as minhas estão de acordo com a definição formal e matemática.
219 Konrad Rudolph
3
A definição matemática formal do interior de um círculo é a que dei no meu post. Da Wikipedia: Em geral, o interior de algo se refere ao espaço ou parte dentro dele, excluindo qualquer tipo de parede ou limite em torno de seu exterior. pt.wikipedia.org/wiki/Interior_(topology)
jason
1
Em pascal, delphi e FPC, tanto power quanto sqrt são muito caros , e não há um operador de energia EG: **ou ^. A maneira mais rápida de fazê-lo quando você só precisa x ^ 2 ou x ^ 3 é fazê-lo "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;
}

Isso é mais eficiente e legível. Evita a operação cara de raiz quadrada. Também adicionei uma verificação para determinar se o ponto está dentro do retângulo delimitador do círculo.

A verificação do retângulo é desnecessária, exceto com muitos pontos ou muitos círculos. Se a maioria dos pontos estiver dentro de círculos, a verificação do retângulo delimitador tornará as coisas mais lentas!

Como sempre, considere seu caso de uso.

William Morrison
fonte
12

Calcular a distância

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

que está em C # ... converte para uso em python ...

Jason Punyon
fonte
11
Você pode evitar duas chamadas caras do Sqrt comparando o quadrado D com o quadrado do raio.
Paul Tomblin
10

Você deve verificar se a distância do centro do círculo ao ponto é menor que o raio, ou seja,

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

Como dito acima - use a distância 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

fonte
4

Encontre a distância entre o centro do círculo e os pontos dados. Se a distância entre eles for menor que o raio, o ponto estará dentro do círculo. se a distância entre eles é igual ao raio do círculo, então o ponto está na circunferência do círculo. se a distância for maior que o raio, o ponto estará fora do 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
fonte
4

A equação seguinte é uma expressão que testa se um ponto está dentro de um círculo dado onde xP & yP são as coordenadas do ponto, xC & yC são as coordenadas do centro do círculo e R é o raio do círculo que dada.

insira a descrição da imagem aqui

Se a expressão acima for verdadeira, o ponto estará dentro do círculo.

Abaixo está uma implementação de exemplo em 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ão do repolho
fonte
2

Essa é a mesma solução mencionada por Jason Punyon , mas contém um exemplo de pseudo-código e mais alguns detalhes. Vi sua resposta depois de escrever isso, mas não queria remover a minha.

Eu acho que a maneira mais fácil de entender é primeiro calcular a distância entre o centro do círculo e o ponto. Eu usaria esta fórmula:

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

Em seguida, basta comparar o resultado dessa fórmula, a distância ( d), com o radius. Se a distância ( d) for menor ou igual ao raio ( r), o ponto estará dentro do círculo (na borda do círculo, se der for igual).

Aqui está um exemplo de pseudo-código que pode ser facilmente convertido em qualquer linguagem de programação:

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

Onde circle_xe circle_ysão as coordenadas centrais do círculo, ré o raio do círculo e xe ysão as coordenadas do ponto.

Daniel Kvist
fonte
2

Minha resposta em C # como uma solução completa de cortar e colar (não otimizada):

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
fonte
1

Como afirmado anteriormente, para mostrar se o ponto está no círculo, podemos usar o seguinte

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

Para representá-lo graficamente, 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
fonte
0

Eu usei o código abaixo para iniciantes como eu :).

classe pública 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");
    } 
}



    }
}}

fonte
0

Movendo-se para o mundo do 3D, se você deseja verificar se um ponto 3D está em uma esfera de unidade, você acaba fazendo algo semelhante. Tudo o que é necessário para trabalhar em 2D é usar operações de vetor 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;
    }

fonte
0

Eu sei que há alguns anos a partir da resposta mais votada, mas consegui reduzir o tempo de cálculo em 4.

Você só precisa calcular os pixels de 1/4 do círculo e multiplicar por 4.

Esta é a solução que cheguei:

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

Aqui está o código java simples para resolver esse problema:

e a matemática por trás disso: /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
fonte
0

PHP

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