如何分辨圆和矩形在二维欧几里得空间中是否相交?(即经典二维几何)
当前回答
有效,一周前才发现,现在才开始测试。
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)));
其他回答
我的方法:
从OBB /矩形上/中的圆计算closest_point (最近点将位于边缘/角落或内部) 计算从closest_point到圆心的squared_distance (距离的平方避免了平方根) 返回squared_distance <=圆半径的平方
这是最快的解决方案:
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;
}
注意执行顺序,一半的宽度/高度是预先计算好的。此外,平方是“手动”完成的,以节省一些时钟周期。
这里有另一个解决方案,实现起来非常简单(也非常快)。它将捕获所有的交点,包括当球体完全进入矩形时。
// clamp(value, min, max) - limits value to the range min..max
// Find the closest point to the circle within the rectangle
float closestX = clamp(circle.X, rectangle.Left, rectangle.Right);
float closestY = clamp(circle.Y, rectangle.Top, rectangle.Bottom);
// Calculate the distance between the circle's center and this closest point
float distanceX = circle.X - closestX;
float distanceY = circle.Y - closestY;
// If the distance is less than the circle's radius, an intersection occurs
float distanceSquared = (distanceX * distanceX) + (distanceY * distanceY);
return distanceSquared < (circle.Radius * circle.Radius);
任何像样的数学库都可以将其缩短为3或4行。
假设你有矩形的四条边,检查从这些边到圆心的距离,如果小于半径,那么这些形状是相交的。
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
圆与矩形相交只有两种情况:
圆的中心在矩形的内部,或者 矩形的一条边在圆上有一个点。
注意,这并不要求矩形与轴平行。
(一种方法是:如果没有一条边在圆中有点(如果所有的边都完全“在”圆外),那么圆仍然可以与多边形相交的唯一方法是它完全位于多边形内部。)
有了这样的见解,就可以像下面这样工作,其中圆的中心是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到直线的垂线的脚是否足够近并且在端点之间,否则检查端点。
最酷的是,同样的想法不仅适用于矩形,而且适用于一个圆与任何简单多边形的交点——甚至不必是凸多边形!