점이 원 안에 있는지 테스트하기위한 방정식

점이 원 안에 있는지 테스트하기위한 방정식

---

중심 (center_x, center_y)과 반지름 이있는 원이 radius있다면 좌표 (x, y)가 있는 주어진 점이 원 안에 있는지 어떻게 테스트 합니까?

---

일반적으로, x그리고 y만족해야한다 (x - center_x)^2 + (y - center_y)^2 < radius^2.

주세요 참고로, 상기 수학 식을 만족하는 포인트 <가 대체 ==포인트 고려 에 원과 함께 상기 식을 만족하는 점 <에 의해 대체 >고려되어 외부 원을.

---

수학적으로 피타고라스는 많은 사람들이 이미 언급 한 것처럼 간단한 방법 일 것입니다.

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

계산적으로 더 빠른 방법이 있습니다. 밝히다:

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

점이이 원의 바깥에 있을 가능성이 높다 면, 그 점이이 원의 접선이되도록 주위에 그려진 사각형을 상상하십시오.

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

이제이 원 안에 정사각형 다이아몬드가 그려져 정점이이 원에 닿도록 상상해보십시오.

if dx + dy <= R then 
    return true.

이제 우리는 대부분의 공간을 커버했으며이 원의 작은 영역 만 테스트 할 사각형과 다이아몬드 사이에 남아 있습니다. 여기서 우리는 위와 같이 피타고라스로 돌아갑니다.

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

점이이 원 안에 있을 가능성이 높은 경우 처음 3 단계의 순서를 반대로하십시오.

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.

---

다른 방법은 다이아몬드 대신이 원 안에 사각형을 상상하지만 계산 이점이없는 약간 더 많은 테스트와 계산이 필요합니다 (내부 사각형과 다이아몬드는 동일한 영역을 가짐).

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

최신 정보:

성능에 관심이있는 사람들을 위해이 방법을 c로 구현하고 -O3으로 컴파일했습니다.

에 의해 실행 시간을 얻었다 time ./a.out

타이밍 오버 헤드를 결정하기 위해이 방법, 일반 방법 및 더미 방법을 구현했습니다.

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

따라서이 방법 이이 구현에서 더 효율적인 것 같습니다.

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

---

피타고라스를 사용하여 점과 중심 사이의 거리를 측정하고 반경보다 낮은 지 확인할 수 있습니다.

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

편집 (폴에게 팁)

실제로, 제곱은 제곱근을 복용하는 것보다 훨씬 저렴하며 주문에만 관심이 있기 때문에 물론 제곱근을 복용하는 것을 잊을 수 있습니다.

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

또한 Jason은 사용법에 따라 <=교체해야하며 <실제로는 이치에 맞습니다비록 엄격한 수학적 의미에서는 사실이 아니라고 생각하지만. 나는 정정되었다.

---

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

이것은 더 효율적이고 읽기 쉽습니다. 값 비싼 제곱근 연산을 피합니다. 또한 점이 원의 경계 사각형 내에 있는지 확인하는 검사를 추가했습니다.

많은 점이나 많은 원을 제외하고 사각형 검사는 필요하지 않습니다. 대부분의 점이 원 안에 있으면 경계 사각형 검사로 인해 실제로 속도가 느려집니다!

항상 그렇듯이 사용 사례를 고려해야합니다.

---

거리 계산

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

그것은 C #에 있습니다 ... 파이썬에서 사용하기 위해 변환하십시오 ...

---

원의 중심에서 점까지의 거리가 반경보다 작은 지 확인해야합니다. 즉

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

---

위에서 말했듯이 유클리드 거리를 사용하십시오.

from math import hypot

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

---

원의 중심과 주어진 점 사이의 거리를 찾으십시오. 그들 사이의 거리가 반경보다 작 으면 점은 원 안에 있습니다. 그들 사이의 거리가 원의 반경과 같으면 점은 원의 원주에 있습니다. 거리가 반경보다 크면 점이 원 밖에 있습니다.

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

---

이것은 Jason Punyon이 언급 한 것과 동일한 솔루션 이지만 의사 코드 예제와 자세한 내용이 포함되어 있습니다. 이 글을 쓴 후 그의 대답을 보았지만 내 것을 제거하고 싶지 않았습니다.

가장 쉽게 이해할 수있는 방법은 먼저 원의 중심과 점 사이의 거리를 계산하는 것입니다. 이 공식을 사용합니다.

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

그런 다음 해당 수식의 결과 인 거리 ( d) 를와 비교 하십시오 radius. 거리 (경우 d) 미만이거나 반경 (동일 r), 점은 원 내부에 (만약 원형의 가장자리 d와 r동일하다).

다음은 모든 프로그래밍 언어로 쉽게 변환 할 수있는 의사 코드 예제입니다.

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_x과 circle_y원의 중심 좌표이며, r원의 반지름이고, x및 y시점의 좌표이다.

---

완벽한 컷 앤 페이스트 (최적화되지 않은) 솔루션으로 C #에서 내 대답 :

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

용법:

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

---

앞에서 언급했듯이 점이 원 안에 있는지 보여주기 위해 다음을 사용할 수 있습니다.

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

그래픽으로 표현하기 위해 다음을 사용할 수 있습니다.

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)

---

아래 방정식은 점이 주어진 원 안에 있는지 여부를 테스트하는 표현식입니다. 여기서 xP & yP 는 점의 좌표이고, xC & yC 는 원 중심의 좌표이고 R 은 해당 원의 반지름입니다.

위의 표현이 참이면 점이 원 안에있는 것입니다.

아래는 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;
    }

---

나는 나와 같은 초보자를 위해 아래 코드를 사용했습니다 :).

공개 수업 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");
    } 
}



    }
}}

---

3D 포인트가 Unit Sphere에 있는지 확인하려면 3D 세계로 이동하면 비슷한 일이 발생합니다. 2D로 작업하는 데 필요한 것은 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;
    }

---

나는 최고의 투표 답변으로부터 몇 년이 걸렸지 만 계산 시간을 4로 줄였습니다.

원의 1/4에서 픽셀을 계산 한 다음 4를 곱하면됩니다.

이것이 내가 도달 한 솔루션입니다.

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

---

이 문제를 해결하기위한 간단한 Java 코드는 다음과 같습니다.

그리고 그 배후의 수학 : 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;
}

참고 URL : https://stackoverflow.com/questions/481144/equation-for-testing-if-a-point-is-inside-a-circle