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


当前回答

有效,一周前才发现,现在才开始测试。

double theta = Math.atan2(cir.getX()-sqr.getX()*1.0,
                          cir.getY()-sqr.getY()*1.0); //radians of the angle
double dBox; //distance from box to edge of box in direction of the circle

if((theta >  Math.PI/4 && theta <  3*Math.PI / 4) ||
   (theta < -Math.PI/4 && theta > -3*Math.PI / 4)) {
    dBox = sqr.getS() / (2*Math.sin(theta));
} else {
    dBox = sqr.getS() / (2*Math.cos(theta));
}
boolean touching = (Math.abs(dBox) >=
                    Math.sqrt(Math.pow(sqr.getX()-cir.getX(), 2) +
                              Math.pow(sqr.getY()-cir.getY(), 2)));

其他回答

下面是我的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;
}

有一种非常简单的方法来做到这一点,你必须在x和y上夹住一个点,但在正方形内部,当圆心在一个垂直轴上的两个正方形边界点之间时,你需要将这些坐标夹到平行轴上,只是要确保夹住的坐标不超过正方形的限制。 然后只需得到圆心与夹紧坐标之间的距离,并检查距离是否小于圆的半径。

以下是我是如何做到的(前4个点是方坐标,其余是圆点):

bool DoesCircleImpactBox(float x, float y, float x1, float y1, float xc, float yc, float radius){
    float ClampedX=0;
    float ClampedY=0;
    
    if(xc>=x and xc<=x1){
    ClampedX=xc;
    }
    
    if(yc>=y and yc<=y1){
    ClampedY=yc;
    }
    
    radius = radius+1;
    
    if(xc<x) ClampedX=x;
    if(xc>x1) ClampedX=x1-1;
    if(yc<y) ClampedY=y;
    if(yc>y1) ClampedY=y1-1;
    
    float XDif=ClampedX-xc;
    XDif=XDif*XDif;
    float YDif=ClampedY-yc;
    YDif=YDif*YDif;
    
    if(XDif+YDif<=radius*radius) return true;
    
    return false;
}

以下是我的做法:

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.

为我工作(只工作时,矩形的角度是180)

function intersects(circle, rect) {
  let left = rect.x + rect.width > circle.x - circle.radius;
  let right = rect.x < circle.x + circle.radius;
  let top = rect.y < circle.y + circle.radius;
  let bottom = rect.y + rect.height > circle.y - circle.radius;
  return left && right && bottom && top;
}

球面和矩形相交于IIF 圆心和矩形的一个顶点之间的距离小于球体的半径 或 圆心与矩形的一条边之间的距离小于球面的半径([点线距离]) 或 圆的中心在矩形的内部 一点上距离:

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

点线路距离:

L1 = [x1,y1],L2 = [x2,y2] (two points of your line, ie the vertex points)
P1 = [px,py] some point

Distance 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)

你的测试应该是这样的:

//rectangle edges: TL (top left), TR (top right), BL (bottom left), BR (bottom right)
//point to test: POI

seperated = false
for egde in { {TL,TR}, {BL,BR}, {TL,BL},{TR-BR} }:  // the edges
    D = edge[0] - edge[1]
    innerProd =  D * POI
    Interval_min = min(D*edge[0],D*edge[1])
    Interval_max = max(D*edge[0],D*edge[1])
    if not (  Interval_min ≤ innerProd ≤  Interval_max ) 
           seperated = true
           break  // end for loop 
    end if
end for
if (seperated is true)    
      return "no intersection"
else 
      return "intersection"
end if

它没有假设一个轴对齐的矩形,并且很容易扩展用于测试凸集之间的交集。