圆形-矩形碰撞检测（交集）

Question

圆形-矩形碰撞检测（交集）

geometrycollision-detection

243

如何判断在二维欧几里得空间中一个圆和一个矩形是否相交？（即经典的二维几何学）

- aib

2

矩形是否总是与坐标轴对齐，还是可以以任意角度旋转？ - e.James

14

@eJames: 这有什么关系呢？你正在检查矩形是否与一个圆形相交；你总是可以变换你的坐标系，使得矩形轴对齐而不改变圆形的位置 :-) - ShreevatsaR

你应该将其作为答案添加，通过旋转-Θ和所有... - aib

5

@ShreevatsaR：这关系到我是否需要担心那个坐标转换。@aib：哦，亲爱的！ - e.James

27个回答

235

圆形和矩形相交只有两种情况：

圆心在矩形内，或
矩形的边缘上有一个点在圆内。

注意，这不需要矩形是轴对齐的。

(一种方法是：如果没有边缘点在圆内（如果所有边缘完全“在外部”），那么圆仍然与多边形相交的唯一方法是它完全位于多边形内部。)

有了这个洞见，像以下代码就可以实现，其中圆形的中心为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到线的垂足是否足够接近并在端点之间，并在否则检查端点。

很酷的事情是，相同的想法不仅适用于矩形，还适用于圆与任何简单多边形的交集——甚至不必是凸多边形！

- ShreevatsaR

38

就我个人而言，我真的认为这个答案比我的更好。主要有两个原因：1. 如果矩形不是轴对齐的，则不需要旋转；2. 这个概念很容易扩展到所有多边形。 - e.James

11

如果矩形完全位于圆内，但圆心不在矩形内，那么怎么办？ - ericsoco

5

@ericsoco：观察得很好。 :-) 我想我应该在“矩形的一条边与圆相交”中说“与圆相交”，因为我指的是它与圆本身共享一个点，而不一定是圆的边界。无论如何，在上面的描述中，“检查从P [圆的中心]到线的垂足是否足够接近并在端点之间，并在其他情况下检查端点”仍将起作用-例如，端点位于圆（圆盘）内。 - ShreevatsaR

12

我认为这个答案被高估了。虽然它看起来有很多花哨的图表和代码示例，但它只是在解释一些显而易见的东西，并最终让读者自行实现。如果我们已经有了神奇的“lineIntersectsCircle”或“pointInRectangle”库函数，那么这个库中很可能已经有“rectangleIntersectsCircle”函数了！ - Paul K

4

@PaulK 你一定比我聪明。 :-) 对我来说这不是“显而易见的事情”；我必须推导出检查这些条件就足够了。同样，如何实现pointInRectangle和intersectCircle也不是显而易见的；这就是为什么我解释了每个函数可能的一个实现方式，即使每个函数可能已经在其他问题中得到了解答。（顺便说一下，这些东西对我来说仍然不是显而易见的；这就是添加证明的原因。这个答案是2008年写的；我只是在2017年添加了图片。）我只是分享我的理解，并没有打算让你感到不悦。 :-) - ShreevatsaR

显示剩余14条评论

150

这里有另一种方案，实现起来相当简单（而且速度也相当快）。它将捕获所有交集，包括球体完全进入矩形的情况。

// 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行。

- Cygon

3

你的代码里有个bug，你在寻找最接近Y轴时使用的是Left和Right，而不是Top和Bottom，除此之外非常好的解决方案。 - manveru

13

我最喜欢这个答案。它简短易懂，速度快。 - John Kurlak

4

如果矩形倾斜于x轴和y轴，我认为你的解决方案会失败。 - Leo

4

@Leo 我认为修改这个算法以适应这种情况并不难，只需要应用一个坐标变换，使原点位于矩形中心，并且矩形不再是斜的。你只需要将变换应用到圆的中心即可。 - enobayram

1

这基本上与 http://www.migapro.com/circle-and-rotated-rectangle-collision-detection/ 所找到的代码相同，我还将其移植到Objective-C。非常有效；这是解决问题的好方法。 - PKCLsoft

显示剩余4条评论

11

我想到的最简单解决方法非常直接。它的原理是找到离圆形最近的矩形上的点，然后比较它们之间的距离。你可以用几个操作完成所有这些步骤，甚至可以避免使用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轴向下。

如果你想要解决移动圆和矩形之间碰撞的问题，那就更加复杂，可以参考我在另一个答案中提供的解决方案。

- ClickerMonkey

如果圆的半径太小并且其中心在矩形内部，那么这将无法检测到交集！ - Yoav

2

你能提供一个导致它失败的实际输入吗？当圆在内部时，测试的左侧部分为0.0。除非半径为零，否则测试的右侧部分应该> 0.0。 - ClickerMonkey

这对旋转矩形也适用吗？如果不是，请给我一些提示... - M Abdul Sami

谢谢，兄弟。它对我来说完美地运行了。 - Abhay Koradiya

圆的起点是在左上角还是中心？ - slier

这基本上与@Cygon的答案相同，但没有额外的变量和注释。 - Pharap

10

如果你的圆和矩形相交，则需要满足以下条件之一：
- 圆心到矩形一个顶点的距离小于圆的半径
- 圆心到矩形一条边的距离小于圆的半径（参考点线距离）
- 圆心在矩形内部

点与点之间的距离：

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

点到线的距离：

L1 = [x1,y1]，L2 = [x2,y2]（线的两个端点）
P1 = [px,py]（某个点）
距离 d =  abs( (x2-x1)(y1-py)-(x1-px)(y2-y1) ) / Distance(L1,L2)

圆心在矩形内部：
采用分隔轴方法：如果存在可以将矩形与点分开的投影到一条直线上，则它们不相交。

对于矩形的每条边，你需要将点投影到平行于该边的线上，然后判断它们是否相交。如果它们不在所有4个投影上都相交，则它们（点和矩形）不相交。

你只需要使用点积（ x= [x1,x2] , y = [y1,y2] , x*y = x1*y1 + x2*y2 ）

相关代码如下：

//矩形边缘：TL（左上角）、TR（右上角）、BL（左下角）、BR（右下角）
//要测试的点：POI
seperated = false
for egde in { {TL,TR}, {BL,BR}, {TL,BL},{TR-BR} }:  // 矩形边缘
    D = edge[0] - edge[1]
    内积 =  D * POI

Interval_min = min(D*edge[0],D*edge[1])
Interval_max = max(D*edge[0],D*edge[1])
如果不满足 (  Interval_min ≤ innerProd ≤  Interval_max ) 
       seperated = true
       break  // 结束 for 循环 
end if
end for
如果 (seperated 是 true)    
      返回 "无交集"
else 
      返回 "有交集"
end if

这并不假定轴对齐的矩形，并且可以轻松扩展以测试凸集之间的相交。

- user104676

1

点对点距离不应该使用平方而不是绝对值吗？ - Thomas

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

注意执行顺序，宽度/高度减半是预先计算的。此外，为了节省一些时钟周期，平方是手动完成的。

- intrepidis

4

我认为在没有证据的情况下，你不能声称在最昂贵的代码路径中进行五次测试/比较是“最快的解决方案”。 - sam hocevar

2

请参阅 https://zh.wikipedia.org/wiki/%E4%BA%BA%E6%B0%91%E8%AE%BA%E9%87%8F 和 https://zh.wikipedia.org/wiki/%E4%BB%8E%E4%B8%8D%E7%9F%A5%E4%B9%8B%E4%B8%AD%E6%8E%A8%E8%AE%BA。 - sam hocevar

1

根据我的经验，使用这种方法大部分时间不会发生碰撞。因此，在大部分代码执行之前，测试将导致退出。 - intrepidis

4

事实上，这非常简单。你只需要两个东西。

首先，你需要找到从圆心到矩形每条线的四个正交距离。如果其中任意三个大于圆半径，则你的圆不会与矩形相交。

其次，你需要找到圆心和矩形中心之间的距离，然后如果该距离大于矩形对角线长度的一半，则圆将不在矩形内部。

祝好运！

- user1329187

4

如果您对更加图形化的解决方案感兴趣，甚至可以在（平面）旋转的矩形上使用...

演示：https://jsfiddle.net/exodus4d/94mxLvqh/2691/ 思路是:

将场景翻译到原点[0,0]
- 如果矩形不在平面上，则旋转中心应该在[0,0]
将场景旋转回平面
计算交集

const hasIntersection = ({x: cx, y: cy, r: cr}, {x, y, width, height}) => {
  const distX = Math.abs(cx - x - width / 2);
  const distY = Math.abs(cy - y - height / 2);

  if (distX > (width / 2 + cr)) {
    return false;
  }
  if (distY > (height / 2 + cr)) {
    return false;
  }

  if (distX <= (width / 2)) {
    return true;
  }
  if (distY <= (height / 2)) {
    return true;
  }

  const Δx = distX - width / 2;
  const Δy = distY - height / 2;
  return Δx * Δx + Δy * Δy <= cr * cr;
};

const rect = new DOMRect(50, 20, 100, 50);
const circ1 = new DOMPoint(160, 80);
circ1.r = 20;

const circ2 = new DOMPoint(80, 95);
circ2.r = 20;

const canvas = document.getElementById('canvas');
const ctx = canvas.getContext('2d');

ctx.strokeRect(rect.x, rect.y, rect.width, rect.height);

ctx.beginPath();
ctx.strokeStyle = hasIntersection(circ1, rect) ? 'red' : 'green';
ctx.arc(circ1.x, circ1.y, circ1.r, 0, 2 * Math.PI);
ctx.stroke();

ctx.beginPath();
ctx.strokeStyle = hasIntersection(circ2, rect) ? 'red' : 'green';
ctx.arc(circ2.x, circ2.y, circ2.r, 0, 2 * Math.PI);
ctx.stroke();

<canvas id="canvas"></canvas>

提示：不必旋转矩形（4个点），而是将圆（1个点）沿相反方向旋转。

- Exodus 4D

如何处理多个矩形和多个圆形？ - Ayfri

3

这是我的C代码，用于解决球和非轴对齐框之间的碰撞问题。它依赖于我自己的一些库例程，但可能对某些人有用。我在游戏中使用它，它完美地工作。

float physicsProcessCollisionBetweenSelfAndActorRect(SPhysics *self, SPhysics *actor)
{
    float diff = 99999;

    SVector relative_position_of_circle = getDifference2DBetweenVectors(&self->worldPosition, &actor->worldPosition);
    rotateVector2DBy(&relative_position_of_circle, -actor->axis.angleZ); // This aligns the coord system so the rect becomes an AABB

    float x_clamped_within_rectangle = relative_position_of_circle.x;
    float y_clamped_within_rectangle = relative_position_of_circle.y;
    LIMIT(x_clamped_within_rectangle, actor->physicsRect.l, actor->physicsRect.r);
    LIMIT(y_clamped_within_rectangle, actor->physicsRect.b, actor->physicsRect.t);

    // Calculate the distance between the circle's center and this closest point
    float distance_to_nearest_edge_x = relative_position_of_circle.x - x_clamped_within_rectangle;
    float distance_to_nearest_edge_y = relative_position_of_circle.y - y_clamped_within_rectangle;

    // If the distance is less than the circle's radius, an intersection occurs
    float distance_sq_x = SQUARE(distance_to_nearest_edge_x);
    float distance_sq_y = SQUARE(distance_to_nearest_edge_y);
    float radius_sq = SQUARE(self->physicsRadius);
    if(distance_sq_x + distance_sq_y < radius_sq)   
    {
        float half_rect_w = (actor->physicsRect.r - actor->physicsRect.l) * 0.5f;
        float half_rect_h = (actor->physicsRect.t - actor->physicsRect.b) * 0.5f;

        CREATE_VECTOR(push_vector);         

        // If we're at one of the corners of this object, treat this as a circular/circular collision
        if(fabs(relative_position_of_circle.x) > half_rect_w && fabs(relative_position_of_circle.y) > half_rect_h)
        {
            SVector edges;
            if(relative_position_of_circle.x > 0) edges.x = half_rect_w; else edges.x = -half_rect_w;
            if(relative_position_of_circle.y > 0) edges.y = half_rect_h; else edges.y = -half_rect_h;   

            push_vector = relative_position_of_circle;
            moveVectorByInverseVector2D(&push_vector, &edges);

            // We now have the vector from the corner of the rect to the point.
            float delta_length = getVector2DMagnitude(&push_vector);
            float diff = self->physicsRadius - delta_length; // Find out how far away we are from our ideal distance

            // Normalise the vector
            push_vector.x /= delta_length;
            push_vector.y /= delta_length;
            scaleVector2DBy(&push_vector, diff); // Now multiply it by the difference
            push_vector.z = 0;
        }
        else // Nope - just bouncing against one of the edges
        {
            if(relative_position_of_circle.x > 0) // Ball is to the right
                push_vector.x = (half_rect_w + self->physicsRadius) - relative_position_of_circle.x;
            else
                push_vector.x = -((half_rect_w + self->physicsRadius) + relative_position_of_circle.x);

            if(relative_position_of_circle.y > 0) // Ball is above
                push_vector.y = (half_rect_h + self->physicsRadius) - relative_position_of_circle.y;
            else
                push_vector.y = -((half_rect_h + self->physicsRadius) + relative_position_of_circle.y);

            if(fabs(push_vector.x) < fabs(push_vector.y))
                push_vector.y = 0;
            else
                push_vector.x = 0;
        }

        diff = 0; // Cheat, since we don't do anything with the value anyway
        rotateVector2DBy(&push_vector, actor->axis.angleZ);
        SVector *from = &self->worldPosition;       
        moveVectorBy2D(from, push_vector.x, push_vector.y);
    }   
    return diff;
}

- Madrayken

2

为了形象化，可以想象你的键盘数字键。如果键“5”代表你的矩形，则1-9键代表由构成你的矩形的线条分割的九个空间象限（其中5是内部）。

1）如果圆的中心在第五象限（即在矩形内部），则两个形状相交。

解决这个问题后，有两种可能情况： a）圆与矩形的两个或更多相邻边相交。 b）圆与矩形的一条边相交。

第一种情况很简单。如果圆与矩形的两个相邻边相交，则它必须包含连接这两个边的角落。（或者，它的中心位于第五象限，我们已经涵盖了这一点。还要注意，圆仅与矩形的两个对立边相交的情况也被涵盖了。）

2）如果矩形的任何一个角A、B、C、D在圆内，则两个形状相交。

第二种情况比较棘手。我们应该注意到，只有当圆的中心位于第2、4、6或8象限中的一个时，它才会发生。（实际上，如果中心位于象限1、3、7、8中的任何一个，相应的角将是最靠近它的点。）

现在我们有了这样一个情况，即圆的中心位于一个“边缘”象限中，并且它仅与相应的边相交。然后，距离圆心最近的边上的点必须位于圆内。

3）对于每条线AB、BC、CD、DA，通过圆心P构造垂线p(AB,P)、p(BC,P)、p(CD,P)、p(DA,P)。对于每条垂线，如果与原始边的交点位于圆内，则两个形状相交。

这最后一步有一个快捷方式。如果圆的中心在第8象限，而边AB是顶部边，则交点将具有A和B的y坐标以及中心P的x坐标。

您可以构建四个线交点并检查它们是否位于其相应的边上，或者找出P所在的象限并检查相应的交点。两种方法都应简化为相同的布尔方程。请注意，上面的第2步没有排除P位于其中一个“角落”象限的可能性；它只是寻找交点。

编辑：事实证明，我忽视了一个简单的事实，即＃2是＃3的子案例。毕竟，角也是边上的点。请参见下面@ShreevatsaR的答案，以获得出色的解释。同时，除非您想要一个快速但多余的检查，否则请忘记上述＃2。

- aib

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- eJames · Accepted Answer

这是我会如何做的：

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

下面是它的工作原理：

illusration

第一对代码计算圆心与矩形中心的x和y差的绝对值。这将四个象限缩成一个，从而省去了重复计算。图像显示了圆心现在必须位于其中的区域。请注意，仅显示单个象限。矩形是灰色区域，红色边框勾画了临界区域，该区域距离矩形边缘正好有一个半径。圆的中心必须在此红色边界内才能发生交集。
第二对代码消除了圆远离矩形的简单情况（两个方向）。这对应于图像中的绿色区域。
第三对代码处理了圆足够靠近矩形的简单情况（两个方向），这样就保证了交集的存在。这对应于图像中的橙色和灰色部分。请注意，这一步骤必须在步骤2之后执行，以使逻辑合理。
其余代码计算了圆可能与矩形角相交的困难情况。为解决此问题，计算圆心与角之间的距离，然后验证该距离是否不超过圆的半径。对于所有中心位于红色阴影区域内的圆，此计算返回false，并对于所有中心位于白色阴影区域内的圆，此计算返回true。