如果你有一个圆心(center_x, center_y)和半径为半径的圆,如何测试一个坐标为(x, y)的给定点是否在圆内?
当前回答
PHP
if ((($x - $center_x) ** 2 + ($y - $center_y) ** 2) <= $radius **2) {
return true; // Inside
} else {
return false; // Outside
}
其他回答
数学上,毕达哥拉斯可能是一个简单的方法,许多人已经提到过。
(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编译。
我通过时间获得了执行次数。/a.out
我实现了这个方法,一个正常的方法和一个虚拟的方法来确定定时开销。
正常:21.3秒 : 19.1秒 开销:16.5秒
因此,这个方法在这个实现中似乎更有效。
// 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);
}
下面是解决这个问题的简单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;
}
一般来说,x和y必须满足(x - center_x)²+ (y - center_y)²< radius²。
请注意,满足上式<的点被==替换为圆上的点,满足上式<的点被>替换为圆外的点。
求圆心到所给点之间的距离。如果它们之间的距离小于半径,则该点在圆内。 如果它们之间的距离等于圆的半径,那么这个点就在圆的周长上。 如果距离大于半径,则该点在圆外。
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");
计算距离
D = Math.Sqrt(Math.Pow(center_x - x, 2) + Math.Pow(center_y - y, 2))
return D <= radius
这是用c#写的……转换为python中使用…