圆 - 矩形碰撞检测(交叉)

Question

如何判断圆形和矩形在2D欧几里德空间中是否相交？(即经典2D几何)

Answer 1

我将如何做到这一点:

bool intersects(CircleType circle, RectType rect)
{
    circleDistance.x = abs(circle.x - rect.x);
    circleDistance.y = abs(circle.y - rect.y);

    if (circleDistance.x > (rect.width/2 + circle.r)) { return false; }
    if (circleDistance.y > (rect.height/2 + circle.r)) { return false; }

    if (circleDistance.x <= (rect.width/2)) { return true; } 
    if (circleDistance.y <= (rect.height/2)) { return true; }

    cornerDistance_sq = (circleDistance.x - rect.width/2)^2 +
                         (circleDistance.y - rect.height/2)^2;

    return (cornerDistance_sq <= (circle.r^2));
}

以下是它的工作原理:

1. 第一对线计算圆心和矩形中心之间的x和y差的绝对值.这将四个象限折叠成一个,因此计算不必进行四次.图像显示圆圈中心现在必须位于的区域.请注意,仅显示单个象限.矩形是灰色区域,红色边框勾勒出临界区域,该区域与矩形边缘恰好相差一个半径.圆的中心必须在此红色边界内,以便发生交叉.

2. 第二对线消除了圆形远离矩形(在任一方向上)足够远而不可能交叉的简单情况.这对应于图像中的绿色区域.

3. 第三对线处理容易的情况,其中圆圈足够接近矩形(在任一方向上),保证交叉点.这对应于图像中的橙色和灰色部分.请注意,必须在步骤2之后执行此步骤才能使逻辑有意义.

4. 剩下的线计算圆可能与矩形的角相交的困难情况.要求解,请计算距圆心和拐角的距离,然后验证距离是否不大于圆的半径.对于中心位于红色阴影区域内的所有圆,此计算返回false,对于中心位于白色阴影区域内的所有圆,该计算返回true.

Answer 2

当圆与矩形相交时,只有两种情况:

• 圆的中心位于矩形内部,或者
• 矩形的一个边缘在圆圈中有一个点.

请注意,这不要求矩形是轴平行的.

(一种观察方式:如果没有边缘在圆中有一个点(如果所有边都完全"在圆"之外),那么圆仍然可以与多边形相交的唯一方法是它是否完全位于圆内多边形.)

有了这种洞察力,像下面的工作,其中圆的中心P和半径R,以及矩形的顶点A,B,C,D的顺序(不完整的代码):

def intersect(Circle(P, R), Rectangle(A, B, C, D)):
    S = Circle(P, R)
    return (pointInRectangle(P, Rectangle(A, B, C, D)) or
            intersectCircle(S, (A, B)) or
            intersectCircle(S, (B, C)) or
            intersectCircle(S, (C, D)) or
            intersectCircle(S, (D, A)))

如果您正在编写任何几何图形,则可能已在库中具有上述功能.否则,pointInRectangle()可以通过多种方式实施; 多边形方法中的任何一般点都可以使用,但是对于一个矩形,您可以检查它是否有效:

0 ? AP·AB ? AB·AB and 0 ? AP·AD ? AD·AD

并且intersectCircle()易于实现:一种方法是检查从P线到线的垂直脚是否足够接近并且在端点之间,否则检查端点.

很酷的是,同样的想法不仅适用于矩形,而且适用于圆与任何简单多边形的交叉- 甚至不必是凸起的!

Answer 3

这是另一个实现起来非常简单的解决方案(也非常快).它将捕获所有交叉点,包括球体完全进入矩形时.

// clamp(value, min, max) - limits value to the range min..max

// Find the closest point to the circle within the rectangle
float closestX = clamp(circle.X, rectangle.Left, rectangle.Right);
float closestY = clamp(circle.Y, rectangle.Top, rectangle.Bottom);

// Calculate the distance between the circle's center and this closest point
float distanceX = circle.X - closestX;
float distanceY = circle.Y - closestY;

// If the distance is less than the circle's radius, an intersection occurs
float distanceSquared = (distanceX * distanceX) + (distanceY * distanceY);
return distanceSquared < (circle.Radius * circle.Radius);

任何体面的数学库,可以缩短为3或4行.

Answer 4

你的球体和矩形与IIF相交
,圆心与矩形的一个顶点之间的距离小于球体的半径,
或者
圆心与矩形的一个边缘之间的距离小于球体的半径( [ 点线距离 ])
或
圆心位于矩形

点点距离内:

P1 = [x1,y1]
P2 = [x2,y2]
Distance = sqrt(abs(x1 - x2)+abs(y1-y2))

点线距离:

L1 = [x1,y1],L2 = [x2,y2] (two points of your line, ie the vertex points)
P1 = [px,py] some point

Distance d =  abs( (x2-x1)(y1-py)-(x1-px)(y2-y1) ) / Distance(L1,L2)

在rect内部的圆心:
采取一个分离轴的方法:如果在一条线上有一个投影,将该矩形与该点分开,它们就不会相交

将点投影在平行于矩形边的线上,然后可以轻松确定它们是否相交.如果它们不与所有4个投影相交,则它们(点和矩形)不能相交.

你只需要内积(x = [x1,x2],y = [y1,y2],x*y = x1*y1 + x2*y2)

你的测试看起来像那样:

//rectangle edges: TL (top left), TR (top right), BL (bottom left), BR (bottom right)
//point to test: POI

seperated = false
for egde in { {TL,TR}, {BL,BR}, {TL,BL},{TR-BR} }:  // the edges
    D = edge[0] - edge[1]
    innerProd =  D * POI
    Interval_min = min(D*edge[0],D*edge[1])
    Interval_max = max(D*edge[0],D*edge[1])
    if not (  Interval_min ≤ innerProd ≤  Interval_max ) 
           seperated = true
           break  // end for loop 
    end if
end for
if (seperated is true)    
      return "no intersection"
else 
      return "intersection"
end if

这并不假设轴对齐的矩形,并且可以很容易地扩展以测试凸集之间的交叉点.

Answer 5

我想出的最简单的解决方案非常简单。

它的工作原理是找到矩形中最接近圆的点，然后比较距离。

您可以通过一些操作完成所有这些，甚至可以避免使用 sqrt 函数。

public boolean intersects(float cx, float cy, float radius, float left, float top, float right, float bottom)
{
   float closestX = (cx < left ? left : (cx > right ? right : cx));
   float closestY = (cy < top ? top : (cy > bottom ? bottom : cy));
   float dx = closestX - cx;
   float dy = closestY - cy;

   return ( dx * dx + dy * dy ) <= radius * radius;
}

就是这样！上述解决方案假设原点位于世界的左上角，x 轴向下。

如果您想要处理移动圆和矩形之间碰撞的解决方案，它会复杂得多，并且在我的另一个答案中有所介绍。

Answer 6

这是最快的解决方案:

public static boolean intersect(Rectangle r, Circle c)
{
    float cx = Math.abs(c.x - r.x - r.halfWidth);
    float xDist = r.halfWidth + c.radius;
    if (cx > xDist)
        return false;
    float cy = Math.abs(c.y - r.y - r.halfHeight);
    float yDist = r.halfHeight + c.radius;
    if (cy > yDist)
        return false;
    if (cx <= r.halfWidth || cy <= r.halfHeight)
        return true;
    float xCornerDist = cx - r.halfWidth;
    float yCornerDist = cy - r.halfHeight;
    float xCornerDistSq = xCornerDist * xCornerDist;
    float yCornerDistSq = yCornerDist * yCornerDist;
    float maxCornerDistSq = c.radius * c.radius;
    return xCornerDistSq + yCornerDistSq <= maxCornerDistSq;
}

请注意执行顺序,并预先计算宽度/高度的一半.平方也是"手动"完成的,以节省一些时钟周期.