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

Question

如何判断圆和矩形在二维欧几里得空间中是否相交？ (即经典的二维几何)

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。