用于测试点是否在圆内的等式

Question

如果你有一个中心(center_x, center_y)和半径的圆radius,你如何测试一个带坐标的给定点(x, y)是否在圆内？

Answer 1

在一般情况下,x并y必须满足(x - center_x)^2 + (y - center_y)^2 < radius^2.

请注意,满足上述方程的点<换成了==被认为是点上的圆圈,并满足上述方程的点<换成了>被认为是外面的圆圈.

Answer 2

在数学上,毕达哥拉斯可能是一个很多人已经提到过的简单方法.

(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.

如果一个点更可能在这个圆圈内,那么前三个步骤的逆序:

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);
}

Answer 3

您可以使用毕达哥拉斯来测量点和中心之间的距离,看它是否低于半径:

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

此外,Jason指出<=应该替换为<并且取决于使用情况,这实际上可能有意义尽管我认为在严格的数学意义上并非如此.我纠正了.

Answer 4

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;
}

这更有效,更易读.它避免了昂贵的平方根操作.我还添加了一个检查以确定该点是否在圆的边界矩形内.

除非有许多点或多个圆圈,否则不需要进行矩形检查.如果大多数点在圈内,则边界矩形检查实际上会使事情变慢!

一如既往,请务必考虑您的用例.

Answer 5

计算距离

D = Math.Sqrt(Math.Pow(center_x - x, 2) + Math.Pow(center_y - y, 2))
return D <= radius

那是在C#中转换为在python中使用...

Answer 6

求圆心与给定点之间的距离。如果它们之间的距离小于半径，则该点在圆内。如果它们之间的距离等于圆的半径，则该点在圆的圆周上。如果距离大于半径，则该点在圆外。

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");

Answer 7

你应该检查从圆心到点的距离是否小于半径,即

if (x-center_x)**2 + (y-center_y)**2 <= radius**2:
    # inside circle

Answer 8

如上所述 - 使用欧几里德距离.

from math import hypot

def in_radius(c_x, c_y, r, x, y):
    return math.hypot(c_x-x, c_y-y) <= r

Answer 9

下面的等式是一个表达式，用于测试一个点是否在给定的圆内，其中xP & yP是该点的坐标，xC & yC是圆心的坐标，R是该给定圆的半径。

如果上述表达式为真，则该点在圆内。

下面是 C# 中的示例实现：

    public static bool IsWithinCircle(PointF pC, Point pP, Single fRadius){
        return Distance(pC, pP) <= fRadius;
    }

    public static Single Distance(PointF p1, PointF p2){
        Single dX = p1.X - p2.X;
        Single dY = p1.Y - p2.Y;
        Single multi = dX * dX + dY * dY;
        Single dist = (Single)Math.Round((Single)Math.Sqrt(multi), 3);

        return (Single)dist;
    }