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


当前回答

预检查一个完全封装矩形的圆是否与矩形发生碰撞。 检查圆内的矩形角。 对于每条边,看看是否有一条线与圆相交。将中心点C投影到直线AB上,得到点d。如果CD的长度小于半径,则发生了碰撞。

    projectionScalar=dot(AC,AB)/(mag(AC)*mag(AB));
    if(projectionScalar>=0 && projectionScalar<=1) {
        D=A+AB*projectionScalar;
        CD=D-C;
        if(mag(CD)<circle.radius){
            // there was a collision
        }
    }

其他回答

球面和矩形相交于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

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

以下是我的做法:

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

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

对于那些需要用SQL在地理坐标中计算圆/矩形碰撞的人, 这是我在oracle 11中实现的e.James建议算法。

在输入中,它需要圆坐标,圆半径km和矩形的两个顶点坐标:

CREATE OR REPLACE FUNCTION "DETECT_CIRC_RECT_COLLISION"
(
    circleCenterLat     IN NUMBER,      -- circle Center Latitude
    circleCenterLon     IN NUMBER,      -- circle Center Longitude
    circleRadius        IN NUMBER,      -- circle Radius in KM
    rectSWLat           IN NUMBER,      -- rectangle South West Latitude
    rectSWLon           IN NUMBER,      -- rectangle South West Longitude
    rectNELat           IN NUMBER,      -- rectangle North Est Latitude
    rectNELon           IN NUMBER       -- rectangle North Est Longitude
)
RETURN NUMBER
AS
    -- converts km to degrees (use 69 if miles)
    kmToDegreeConst     NUMBER := 111.045;

    -- Remaining rectangle vertices 
    rectNWLat   NUMBER;
    rectNWLon   NUMBER;
    rectSELat   NUMBER;
    rectSELon   NUMBER;

    rectHeight  NUMBER;
    rectWIdth   NUMBER;

    circleDistanceLat   NUMBER;
    circleDistanceLon   NUMBER;
    cornerDistanceSQ    NUMBER;

BEGIN
    -- Initialization of remaining rectangle vertices  
    rectNWLat := rectNELat;
    rectNWLon := rectSWLon;
    rectSELat := rectSWLat;
    rectSELon := rectNELon;

    -- Rectangle sides length calculation
    rectHeight := calc_distance(rectSWLat, rectSWLon, rectNWLat, rectNWLon);
    rectWidth := calc_distance(rectSWLat, rectSWLon, rectSELat, rectSELon);

    circleDistanceLat := abs( (circleCenterLat * kmToDegreeConst) - ((rectSWLat * kmToDegreeConst) + (rectHeight/2)) );
    circleDistanceLon := abs( (circleCenterLon * kmToDegreeConst) - ((rectSWLon * kmToDegreeConst) + (rectWidth/2)) );

    IF circleDistanceLon > ((rectWidth/2) + circleRadius) THEN
        RETURN -1;   --  -1 => NO Collision ; 0 => Collision Detected
    END IF;

    IF circleDistanceLat > ((rectHeight/2) + circleRadius) THEN
        RETURN -1;   --  -1 => NO Collision ; 0 => Collision Detected
    END IF;

    IF circleDistanceLon <= (rectWidth/2) THEN
        RETURN 0;   --  -1 => NO Collision ; 0 => Collision Detected
    END IF;

    IF circleDistanceLat <= (rectHeight/2) THEN
        RETURN 0;   --  -1 => NO Collision ; 0 => Collision Detected
    END IF;


    cornerDistanceSQ := POWER(circleDistanceLon - (rectWidth/2), 2) + POWER(circleDistanceLat - (rectHeight/2), 2);

    IF cornerDistanceSQ <=  POWER(circleRadius, 2) THEN
        RETURN 0;  --  -1 => NO Collision ; 0 => Collision Detected
    ELSE
        RETURN -1;  --  -1 => NO Collision ; 0 => Collision Detected
    END IF;

    RETURN -1;  --  -1 => NO Collision ; 0 => Collision Detected
END;    

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

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

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