如何分辨圆和矩形在二维欧几里得空间中是否相交?(即经典二维几何)


当前回答

首先检查矩形和与圆相切的正方形是否重叠(简单)。如果它们不重叠,就不会碰撞。 检查圆的中心是否在矩形内(简单)。如果它在里面,它们就会碰撞。 计算矩形边到圆中心的最小平方距离(略硬)。如果小于半径的平方,它们就会碰撞,否则不会。

它是有效的,因为:

首先,它用一个便宜的算法检查最常见的场景,当它确定它们没有碰撞时,它就结束了。 然后它用一个廉价的算法检查下一个最常见的场景(不要计算平方根,使用平方值),当它确定它们碰撞时,它就结束了。 然后它执行更昂贵的算法来检查与矩形边框的碰撞。

其他回答

为了可视化,拿你的键盘的numpad。如果键“5”代表你的矩形,那么所有的键1-9代表空间的9个象限除以构成矩形的线(5是里面的线)。

1)如果圆的中心在象限5(即在矩形内),则两个形状相交。

这里有两种可能的情况: a)圆与矩形的两条或多条相邻边相交。 b)圆与矩形的一条边相交。

第一种情况很简单。如果圆与矩形的两条相邻边相交,则它必须包含连接这两条边的角。(或者说它的中心在象限5,我们已经讲过了。还要注意,圆只与矩形的两条相对边相交的情况也被覆盖了。)

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是上边,交点的y坐标是A和B, x坐标是P。

你可以构造四条线的交点并检查它们是否在相应的边上,或者找出P在哪个象限并检查相应的交点。两者都应该化简为相同的布尔方程。要注意的是,上面的步骤2并没有排除P位于“角落”象限之一;它只是在寻找一个十字路口。

编辑:事实证明,我忽略了一个简单的事实,即#2是#3的子情况。毕竟,角也是边缘上的点。请看下面@ShreevatsaR的回答,你会得到很好的解释。与此同时,忘记上面的第二条,除非你想要一个快速但冗余的检查。

以下是我的做法:

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

下面是它的工作原理:

The first pair of lines calculate the absolute values of the x and y difference between the center of the circle and the center of the rectangle. This collapses the four quadrants down into one, so that the calculations do not have to be done four times. The image shows the area in which the center of the circle must now lie. Note that only the single quadrant is shown. The rectangle is the grey area, and the red border outlines the critical area which is exactly one radius away from the edges of the rectangle. The center of the circle has to be within this red border for the intersection to occur. The second pair of lines eliminate the easy cases where the circle is far enough away from the rectangle (in either direction) that no intersection is possible. This corresponds to the green area in the image. The third pair of lines handle the easy cases where the circle is close enough to the rectangle (in either direction) that an intersection is guaranteed. This corresponds to the orange and grey sections in the image. Note that this step must be done after step 2 for the logic to make sense. The remaining lines calculate the difficult case where the circle may intersect the corner of the rectangle. To solve, compute the distance from the center of the circle and the corner, and then verify that the distance is not more than the radius of the circle. This calculation returns false for all circles whose center is within the red shaded area and returns true for all circles whose center is within the white shaded area.

这是最快的解决方案:

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

注意执行顺序,一半的宽度/高度是预先计算好的。此外,平方是“手动”完成的,以节省一些时钟周期。

我为处理形状创建了类 希望你喜欢

public class Geomethry {
  public static boolean intersectionCircleAndRectangle(int circleX, int circleY, int circleR, int rectangleX, int rectangleY, int rectangleWidth, int rectangleHeight){
    boolean result = false;

    float rectHalfWidth = rectangleWidth/2.0f;
    float rectHalfHeight = rectangleHeight/2.0f;

    float rectCenterX = rectangleX + rectHalfWidth;
    float rectCenterY = rectangleY + rectHalfHeight;

    float deltax = Math.abs(rectCenterX - circleX);
    float deltay = Math.abs(rectCenterY - circleY);

    float lengthHypotenuseSqure = deltax*deltax + deltay*deltay;

    do{
        // check that distance between the centerse is more than the distance between the circumcircle of rectangle and circle
        if(lengthHypotenuseSqure > ((rectHalfWidth+circleR)*(rectHalfWidth+circleR) + (rectHalfHeight+circleR)*(rectHalfHeight+circleR))){
            //System.out.println("distance between the centerse is more than the distance between the circumcircle of rectangle and circle");
            break;
        }

        // check that distance between the centerse is less than the distance between the inscribed circle
        float rectMinHalfSide = Math.min(rectHalfWidth, rectHalfHeight);
        if(lengthHypotenuseSqure < ((rectMinHalfSide+circleR)*(rectMinHalfSide+circleR))){
            //System.out.println("distance between the centerse is less than the distance between the inscribed circle");
            result=true;
            break;
        }

        // check that the squares relate to angles
        if((deltax > (rectHalfWidth+circleR)*0.9) && (deltay > (rectHalfHeight+circleR)*0.9)){
            //System.out.println("squares relate to angles");
            result=true;
        }
    }while(false);

    return result;
}

public static boolean intersectionRectangleAndRectangle(int rectangleX, int rectangleY, int rectangleWidth, int rectangleHeight, int rectangleX2, int rectangleY2, int rectangleWidth2, int rectangleHeight2){
    boolean result = false;

    float rectHalfWidth = rectangleWidth/2.0f;
    float rectHalfHeight = rectangleHeight/2.0f;
    float rectHalfWidth2 = rectangleWidth2/2.0f;
    float rectHalfHeight2 = rectangleHeight2/2.0f;

    float deltax = Math.abs((rectangleX + rectHalfWidth) - (rectangleX2 + rectHalfWidth2));
    float deltay = Math.abs((rectangleY + rectHalfHeight) - (rectangleY2 + rectHalfHeight2));

    float lengthHypotenuseSqure = deltax*deltax + deltay*deltay;

    do{
        // check that distance between the centerse is more than the distance between the circumcircle
        if(lengthHypotenuseSqure > ((rectHalfWidth+rectHalfWidth2)*(rectHalfWidth+rectHalfWidth2) + (rectHalfHeight+rectHalfHeight2)*(rectHalfHeight+rectHalfHeight2))){
            //System.out.println("distance between the centerse is more than the distance between the circumcircle");
            break;
        }

        // check that distance between the centerse is less than the distance between the inscribed circle
        float rectMinHalfSide = Math.min(rectHalfWidth, rectHalfHeight);
        float rectMinHalfSide2 = Math.min(rectHalfWidth2, rectHalfHeight2);
        if(lengthHypotenuseSqure < ((rectMinHalfSide+rectMinHalfSide2)*(rectMinHalfSide+rectMinHalfSide2))){
            //System.out.println("distance between the centerse is less than the distance between the inscribed circle");
            result=true;
            break;
        }

        // check that the squares relate to angles
        if((deltax > (rectHalfWidth+rectHalfWidth2)*0.9) && (deltay > (rectHalfHeight+rectHalfHeight2)*0.9)){
            //System.out.println("squares relate to angles");
            result=true;
        }
    }while(false);

    return result;
  } 
}

这里有一个快速的单行测试:

if (length(max(abs(center - rect_mid) - rect_halves, 0)) <= radius ) {
  // They intersect.
}

这是轴对齐的情况,其中rect_二分之一是一个正向量,从矩形的中间指向一个角。length()中的表达式是一个从矩形中心到最近点的增量向量。这适用于任何维度。