如何分辨圆和矩形在二维欧几里得空间中是否相交?(即经典二维几何)
当前回答
对于那些需要用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;
其他回答
首先检查矩形和与圆相切的正方形是否重叠(简单)。如果它们不重叠,就不会碰撞。 检查圆的中心是否在矩形内(简单)。如果它在里面,它们就会碰撞。 计算矩形边到圆中心的最小平方距离(略硬)。如果小于半径的平方,它们就会碰撞,否则不会。
它是有效的,因为:
首先,它用一个便宜的算法检查最常见的场景,当它确定它们没有碰撞时,它就结束了。 然后它用一个廉价的算法检查下一个最常见的场景(不要计算平方根,使用平方值),当它确定它们碰撞时,它就结束了。 然后它执行更昂贵的算法来检查与矩形边框的碰撞。
这是最快的解决方案:
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;
}
注意执行顺序,一半的宽度/高度是预先计算好的。此外,平方是“手动”完成的,以节省一些时钟周期。
圆与矩形相交只有两种情况:
圆的中心在矩形的内部,或者 矩形的一条边在圆上有一个点。
注意,这并不要求矩形与轴平行。
(一种方法是:如果没有一条边在圆中有点(如果所有的边都完全“在”圆外),那么圆仍然可以与多边形相交的唯一方法是它完全位于多边形内部。)
有了这样的见解,就可以像下面这样工作,其中圆的中心是P,半径是R,矩形的顶点是A, B, C, D(不完整的代码):
def intersect(Circle(P, R), Rectangle(A, B, C, D)):
S = Circle(P, R)
return (pointInRectangle(P, Rectangle(A, B, C, D)) or
intersectCircle(S, (A, B)) or
intersectCircle(S, (B, C)) or
intersectCircle(S, (C, D)) or
intersectCircle(S, (D, A)))
如果你在写任何几何,你的库中可能已经有了上面的函数。否则,pointInRectangle()可以用几种方式实现;任何一般的多边形点方法都可以工作,但对于矩形,你可以检查这是否有效:
0 ≤ AP·AB ≤ AB·AB and 0 ≤ AP·AD ≤ AD·AD
intersectCircle()也很容易实现:一种方法是检查从P到直线的垂线的脚是否足够近并且在端点之间,否则检查端点。
最酷的是,同样的想法不仅适用于矩形,而且适用于一个圆与任何简单多边形的交点——甚至不必是凸多边形!
这里有一个快速的单行测试:
if (length(max(abs(center - rect_mid) - rect_halves, 0)) <= radius ) {
// They intersect.
}
这是轴对齐的情况,其中rect_二分之一是一个正向量,从矩形的中间指向一个角。length()中的表达式是一个从矩形中心到最近点的增量向量。这适用于任何维度。
我想出的最简单的解决办法非常直接。
它的工作原理是在矩形中找到离圆最近的点,然后比较距离。
您可以通过一些操作来完成所有这些操作,甚至可以避免使用平方根函数。
public boolean intersects(float cx, float cy, float radius, float left, float top, float right, float bottom)
{
float closestX = (cx < left ? left : (cx > right ? right : cx));
float closestY = (cy < top ? top : (cy > bottom ? bottom : cy));
float dx = closestX - cx;
float dy = closestY - cy;
return ( dx * dx + dy * dy ) <= radius * radius;
}
就是这样!上面的解决方案假设原点在世界的左上方,x轴指向下方。
如果你想要一个解决移动的圆形和矩形之间碰撞的解决方案,这要复杂得多,并且包含在我的另一个答案中。