如果你有一个圆心(center_x, center_y)和半径为半径的圆,如何测试一个坐标为(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)) { }
其他回答
PHP
if ((($x - $center_x) ** 2 + ($y - $center_y) ** 2) <= $radius **2) {
return true; // Inside
} else {
return false; // Outside
}
一般来说,x和y必须满足(x - center_x)²+ (y - center_y)²< radius²。
请注意,满足上式<的点被==替换为圆上的点,满足上式<的点被>替换为圆外的点。
计算距离
D = Math.Sqrt(Math.Pow(center_x - x, 2) + Math.Pow(center_y - y, 2))
return D <= radius
这是用c#写的……转换为python中使用…
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;
}
这样效率更高,可读性更强。它避免了昂贵的平方根运算。我还添加了一个检查,以确定点是否在圆的边界矩形内。
矩形检查是不必要的,除非有许多点或许多圆。如果大多数点都在圆圈内,边框检查实际上会使事情变慢!
像往常一样,一定要考虑您的用例。
数学上,毕达哥拉斯可能是一个简单的方法,许多人已经提到过。
(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);
}