一个准确检测正方形和圆形重叠的算法？

Question

我正在使用C++实现一个方法，以检测在2D平面上发生两个静态轴对齐形状重叠的情况。这些形状可以是正方形或圆形，因此我需要考虑三种情况：正方形-正方形、圆形-圆形和圆形-正方形。

正方形-正方形和圆形-圆形都很简单，但我在网上找不到关于计算正方形-圆形重叠的正确算法的可靠信息。

我知道可以将正方形嵌入圆形（或反之）作为粗略的方法，但我想知道更精确的清晰方法是什么？

在线研究表明，这个问题有一个“正确”的答案，但并没有明确说明具体的答案是什么。

- transiti0nary

---

https://dev59.com/tXRC5IYBdhLWcg3wJNYN - Michael Dorgan

更一般地说，找到矩形（正方形）上离圆心最近的点。如果形状是AA，则这很简单。如果不是，则可以使用点积来计算。如果此距离小于圆的半径，则存在碰撞。除非圆完全在正方形内部，否则需要检查每个点是否包含在内（每个顶点与中心的距离与半径比较）。 - Michael Dorgan

最干净的方法取决于您的图形存储了哪些信息。您的圆是由3个点的坐标建模，还是您有中心和半径？对于您的矩形，也是3个点，还是其他什么？如果您提供给我这些信息，我将很高兴回到高中数学！ - Oliv

或者我给你一个提示：假设A和B是矩形边的两个端点，长度为l，C是圆心。令d为C到线(AB)的距离，您有这个关系式abs(ABxAC)=l*d，其中x是向量AB和AC的叉积。此外，乘积的符号可以指示圆心是朝内还是朝外。 - Oliv

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更接近，则存在重叠。

- geza