如何分辨圆和矩形在二维欧几里得空间中是否相交?(即经典二维几何)
当前回答
假设你有矩形的四条边,检查从这些边到圆心的距离,如果小于半径,那么这些形状是相交的。
if sqrt((rectangleRight.x - circleCenter.x)^2 +
(rectangleBottom.y - circleCenter.y)^2) < radius
// then they intersect
if sqrt((rectangleRight.x - circleCenter.x)^2 +
(rectangleTop.y - circleCenter.y)^2) < radius
// then they intersect
if sqrt((rectangleLeft.x - circleCenter.x)^2 +
(rectangleTop.y - circleCenter.y)^2) < radius
// then they intersect
if sqrt((rectangleLeft.x - circleCenter.x)^2 +
(rectangleBottom.y - circleCenter.y)^2) < radius
// then they intersect
其他回答
首先检查矩形和与圆相切的正方形是否重叠(简单)。如果它们不重叠,就不会碰撞。 检查圆的中心是否在矩形内(简单)。如果它在里面,它们就会碰撞。 计算矩形边到圆中心的最小平方距离(略硬)。如果小于半径的平方,它们就会碰撞,否则不会。
它是有效的,因为:
首先,它用一个便宜的算法检查最常见的场景,当它确定它们没有碰撞时,它就结束了。 然后它用一个廉价的算法检查下一个最常见的场景(不要计算平方根,使用平方值),当它确定它们碰撞时,它就结束了。 然后它执行更昂贵的算法来检查与矩形边框的碰撞。
对于那些需要用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;
为我工作(只工作时,矩形的角度是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;
}
这是最快的解决方案:
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到直线的垂线的脚是否足够近并且在端点之间,否则检查端点。
最酷的是,同样的想法不仅适用于矩形,而且适用于一个圆与任何简单多边形的交点——甚至不必是凸多边形!