如何分辨圆和矩形在二维欧几里得空间中是否相交?(即经典二维几何)
当前回答
我想出的最简单的解决办法非常直接。
它的工作原理是在矩形中找到离圆最近的点,然后比较距离。
您可以通过一些操作来完成所有这些操作,甚至可以避免使用平方根函数。
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轴指向下方。
如果你想要一个解决移动的圆形和矩形之间碰撞的解决方案,这要复杂得多,并且包含在我的另一个答案中。
其他回答
为了可视化,拿你的键盘的numpad。如果键“5”代表你的矩形,那么所有的键1-9代表空间的9个象限除以构成矩形的线(5是里面的线)。
1)如果圆的中心在象限5(即在矩形内),则两个形状相交。
这里有两种可能的情况: a)圆与矩形的两条或多条相邻边相交。 b)圆与矩形的一条边相交。
第一种情况很简单。如果圆与矩形的两条相邻边相交,则它必须包含连接这两条边的角。(或者说它的中心在象限5,我们已经讲过了。还要注意,圆只与矩形的两条相对边相交的情况也被覆盖了。)
2)如果矩形的任意角A、B、C、D在圆内,则这两个形状相交。
第二种情况比较棘手。我们应该注意到,只有当圆的中心位于2、4、6或8象限中的一个象限时,才会发生这种情况。(事实上,如果中心在1、3、7、8象限中的任何一个象限上,则相应的角将是离它最近的点。)
现在我们有了圆的中心在一个“边”象限内的情况,它只与相应的边相交。那么,边缘上最接近圆中心的点必须在圆内。
3)对于每条直线AB, BC, CD, DA,构造经过圆中心p的垂直线p(AB, p), p(BC, p), p(CD, p), p(DA, p),对于每条垂直线,如果与原边的交点在圆内,则两个图形相交。
最后一步有一个捷径。如果圆的圆心在象限8,边AB是上边,交点的y坐标是A和B, x坐标是P。
你可以构造四条线的交点并检查它们是否在相应的边上,或者找出P在哪个象限并检查相应的交点。两者都应该化简为相同的布尔方程。要注意的是,上面的步骤2并没有排除P位于“角落”象限之一;它只是在寻找一个十字路口。
编辑:事实证明,我忽略了一个简单的事实,即#2是#3的子情况。毕竟,角也是边缘上的点。请看下面@ShreevatsaR的回答,你会得到很好的解释。与此同时,忘记上面的第二条,除非你想要一个快速但冗余的检查。
实际上,这要简单得多。你只需要两样东西。
首先,你需要找出从圆中心到矩形每条直线的四个正交距离。如果任意三个圆的半径大于矩形的半径,那么圆就不会与矩形相交。
其次,你需要找到圆中心和矩形中心之间的距离,那么你的圆不会在矩形内部如果距离大于矩形对角线长度的一半。
好运!
有一种非常简单的方法来做到这一点,你必须在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;
}
def colision(rect, circle):
dx = rect.x - circle.x
dy = rect.y - circle.y
distance = (dy**2 + dx**2)**0.5
angle_to = (rect.angle + math.atan2(dx, dy)/3.1415*180.0) % 360
if((angle_to>135 and angle_to<225) or (angle_to>0 and angle_to<45) or (angle_to>315 and angle_to<360)):
if distance <= circle.rad/2.+((rect.height/2.0)*(1.+0.5*abs(math.sin(angle_to*math.pi/180.)))):
return True
else:
if distance <= circle.rad/2.+((rect.width/2.0)*(1.+0.5*abs(math.cos(angle_to*math.pi/180.)))):
return True
return False
这里有另一个解决方案,实现起来非常简单(也非常快)。它将捕获所有的交点,包括当球体完全进入矩形时。
// 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行。