如果你有一个圆心(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)) { }
其他回答
这与Jason Punyon提到的解决方案相同,但它包含伪代码示例和更多细节。写完这篇文章后,我看到了他的回答,但我不想删除我的。
我认为最容易理解的方法是先计算圆心到点的距离。我会用这个公式:
d = sqrt((circle_x - x)^2 + (circle_y - y)^2)
然后,简单地比较公式的结果,距离(d),与半径。如果距离(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是点的坐标。
进入3D世界,如果你想检查一个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;
}
数学上,毕达哥拉斯可能是一个简单的方法,许多人已经提到过。
(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);
}
如上所述,使用欧几里得距离。
from math import hypot
def in_radius(c_x, c_y, r, x, y):
return math.hypot(c_x-x, c_y-y) <= r
iOS 15,接受的答案写在Swift 5.5
func isInRectangle(center: CGPoint, radius: Double, point: CGPoint) -> Bool
{
return point.x >= center.x - radius && point.x <= center.x + radius &&
point.y >= center.y - radius && point.y <= center.y + radius
}
//test if coordinate (x, y) is within a radius from coordinate (center_x, center_y)
func isPointInCircle(center: CGPoint,
radius:Double, point: CGPoint) -> Bool
{
if(isInRectangle(center: center, radius: radius, point: point))
{
var dx:Double = center.x - point.x
var dy:Double = center.y - point.y
dx *= dx
dy *= dy
let distanceSquared:Double = dx + dy
let radiusSquared:Double = radius * radius
return distanceSquared <= radiusSquared
}
return false
}