Математически Пифагор, вероятно, является простым методом, о котором многие уже упоминали.
(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);
}