如何分辨圆和矩形在二维欧几里得空间中是否相交?(即经典二维几何)
当前回答
有一种非常简单的方法来做到这一点,你必须在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;
}
其他回答
圆与矩形相交只有两种情况:
圆的中心在矩形的内部,或者 矩形的一条边在圆上有一个点。
注意,这并不要求矩形与轴平行。
(一种方法是:如果没有一条边在圆中有点(如果所有的边都完全“在”圆外),那么圆仍然可以与多边形相交的唯一方法是它完全位于多边形内部。)
有了这样的见解,就可以像下面这样工作,其中圆的中心是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到直线的垂线的脚是否足够近并且在端点之间,否则检查端点。
最酷的是,同样的想法不仅适用于矩形,而且适用于一个圆与任何简单多边形的交点——甚至不必是凸多边形!
下面是我的C代码,用于解决球体和非轴对齐的盒子之间的碰撞。它依赖于我自己的几个库例程,但它可能对某些人有用。我在游戏中使用了它,效果非常好。
float physicsProcessCollisionBetweenSelfAndActorRect(SPhysics *self, SPhysics *actor)
{
float diff = 99999;
SVector relative_position_of_circle = getDifference2DBetweenVectors(&self->worldPosition, &actor->worldPosition);
rotateVector2DBy(&relative_position_of_circle, -actor->axis.angleZ); // This aligns the coord system so the rect becomes an AABB
float x_clamped_within_rectangle = relative_position_of_circle.x;
float y_clamped_within_rectangle = relative_position_of_circle.y;
LIMIT(x_clamped_within_rectangle, actor->physicsRect.l, actor->physicsRect.r);
LIMIT(y_clamped_within_rectangle, actor->physicsRect.b, actor->physicsRect.t);
// Calculate the distance between the circle's center and this closest point
float distance_to_nearest_edge_x = relative_position_of_circle.x - x_clamped_within_rectangle;
float distance_to_nearest_edge_y = relative_position_of_circle.y - y_clamped_within_rectangle;
// If the distance is less than the circle's radius, an intersection occurs
float distance_sq_x = SQUARE(distance_to_nearest_edge_x);
float distance_sq_y = SQUARE(distance_to_nearest_edge_y);
float radius_sq = SQUARE(self->physicsRadius);
if(distance_sq_x + distance_sq_y < radius_sq)
{
float half_rect_w = (actor->physicsRect.r - actor->physicsRect.l) * 0.5f;
float half_rect_h = (actor->physicsRect.t - actor->physicsRect.b) * 0.5f;
CREATE_VECTOR(push_vector);
// If we're at one of the corners of this object, treat this as a circular/circular collision
if(fabs(relative_position_of_circle.x) > half_rect_w && fabs(relative_position_of_circle.y) > half_rect_h)
{
SVector edges;
if(relative_position_of_circle.x > 0) edges.x = half_rect_w; else edges.x = -half_rect_w;
if(relative_position_of_circle.y > 0) edges.y = half_rect_h; else edges.y = -half_rect_h;
push_vector = relative_position_of_circle;
moveVectorByInverseVector2D(&push_vector, &edges);
// We now have the vector from the corner of the rect to the point.
float delta_length = getVector2DMagnitude(&push_vector);
float diff = self->physicsRadius - delta_length; // Find out how far away we are from our ideal distance
// Normalise the vector
push_vector.x /= delta_length;
push_vector.y /= delta_length;
scaleVector2DBy(&push_vector, diff); // Now multiply it by the difference
push_vector.z = 0;
}
else // Nope - just bouncing against one of the edges
{
if(relative_position_of_circle.x > 0) // Ball is to the right
push_vector.x = (half_rect_w + self->physicsRadius) - relative_position_of_circle.x;
else
push_vector.x = -((half_rect_w + self->physicsRadius) + relative_position_of_circle.x);
if(relative_position_of_circle.y > 0) // Ball is above
push_vector.y = (half_rect_h + self->physicsRadius) - relative_position_of_circle.y;
else
push_vector.y = -((half_rect_h + self->physicsRadius) + relative_position_of_circle.y);
if(fabs(push_vector.x) < fabs(push_vector.y))
push_vector.y = 0;
else
push_vector.x = 0;
}
diff = 0; // Cheat, since we don't do anything with the value anyway
rotateVector2DBy(&push_vector, actor->axis.angleZ);
SVector *from = &self->worldPosition;
moveVectorBy2D(from, push_vector.x, push_vector.y);
}
return diff;
}
有效,一周前才发现,现在才开始测试。
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)));
这是最快的解决方案:
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;
}
注意执行顺序,一半的宽度/高度是预先计算好的。此外,平方是“手动”完成的,以节省一些时钟周期。
球面和矩形相交于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
它没有假设一个轴对齐的矩形,并且很容易扩展用于测试凸集之间的交集。