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

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

(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

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

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