精确检测正方形和圆形重叠的算法？

Question

我正在实现(在C++中)一种方法来检测在2d平面上两个静态的轴对齐形状之间何时发生重叠.形状是正方形或圆形,因此有三种情况我需要考虑重叠:方形,圆形和圆形方形.

方形和圆形也很简单,但我很难在网上找到关于计算方形圆重叠的正确算法的任何可靠信息.

我知道我可以将方块嵌入圆圈内(反之亦然)作为一种粗略的方法,但我对于更精确地做到这一点的最干净的方法感兴趣？

在线研究表明这个问题有一个"正确"的答案,但尚不清楚答案究竟是什么.

Answer 1

这是一个简单而快速的算法：

bool doesSquareCircleOverlap(float squareCenterX, float squareCenterY, float squareHalfSize, float circleCenterX, float circleCenterY, float circleRadius) {
    float x = fabs(circleCenterX - squareCenterX) - squareHalfSize;
    float y = fabs(circleCenterY - squareCenterY) - squareHalfSize;

    if (x>0) {
        if (y>0) {
            return x*x + y*y<circleRadius*circleRadius;
        } else {
            return x<circleRadius;
        }
    } else {
        return y<circleRadius;
    }
}

请注意，正方形由中心和半角表示。

基本上，它的作用是：

• 它删除了对称的情况fabs()
• 将角放入原点
• 检查圆心在哪个区域，以确定正方形上距圆最近的点。如果该闭合点比 更近circleRadius，则存在重叠。