如何分辨圆和矩形在二维欧几里得空间中是否相交?(即经典二维几何)
当前回答
我想出的最简单的解决办法非常直接。
它的工作原理是在矩形中找到离圆最近的点,然后比较距离。
您可以通过一些操作来完成所有这些操作,甚至可以避免使用平方根函数。
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轴指向下方。
如果你想要一个解决移动的圆形和矩形之间碰撞的解决方案,这要复杂得多,并且包含在我的另一个答案中。
其他回答
如果你对一个更图形化的解决方案感兴趣,甚至在(平面上)旋转的矩形..
演示:https://jsfiddle.net/exodus4d/94mxLvqh/2691/
这个想法是:
将场景转换为原点[0,0] 如果矩形不在平面上,则旋转中心应在 (0,0) 将场景旋转回平面 计算交点
const hasIntersection = ({x: cx, y: cy, r: cr}, {x, y, width, height}) => { const distX = Math.abs(cx - x - width / 2); const distY = Math.abs(cy - y - height / 2); if (distX > (width / 2 + cr)) { return false; } if (distY > (height / 2 + cr)) { return false; } if (distX <= (width / 2)) { return true; } if (distY <= (height / 2)) { return true; } const Δx = distX - width / 2; const Δy = distY - height / 2; return Δx * Δx + Δy * Δy <= cr * cr; }; const rect = new DOMRect(50, 20, 100, 50); const circ1 = new DOMPoint(160, 80); circ1.r = 20; const circ2 = new DOMPoint(80, 95); circ2.r = 20; const canvas = document.getElementById('canvas'); const ctx = canvas.getContext('2d'); ctx.strokeRect(rect.x, rect.y, rect.width, rect.height); ctx.beginPath(); ctx.strokeStyle = hasIntersection(circ1, rect) ? 'red' : 'green'; ctx.arc(circ1.x, circ1.y, circ1.r, 0, 2 * Math.PI); ctx.stroke(); ctx.beginPath(); ctx.strokeStyle = hasIntersection(circ2, rect) ? 'red' : 'green'; ctx.arc(circ2.x, circ2.y, circ2.r, 0, 2 * Math.PI); ctx.stroke(); <canvas id="canvas"></canvas>
提示:而不是旋转矩形(4点)。你可以向相反的方向旋转圆(1点)。
下面是我的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;
}
圆与矩形相交只有两种情况:
圆的中心在矩形的内部,或者 矩形的一条边在圆上有一个点。
注意,这并不要求矩形与轴平行。
(一种方法是:如果没有一条边在圆中有点(如果所有的边都完全“在”圆外),那么圆仍然可以与多边形相交的唯一方法是它完全位于多边形内部。)
有了这样的见解,就可以像下面这样工作,其中圆的中心是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到直线的垂线的脚是否足够近并且在端点之间,否则检查端点。
最酷的是,同样的想法不仅适用于矩形,而且适用于一个圆与任何简单多边形的交点——甚至不必是凸多边形!
我在制作这款游戏时开发了这个算法:https://mshwf.github.io/mates/
如果圆与正方形接触,那么圆的中心线与正方形中心线之间的距离应该等于(直径+边)/2。 让我们有一个名为touching的变量来保存这个距离。问题是:我应该考虑哪条中心线:水平的还是垂直的? 考虑这个框架:
每条中心线给出了不同的距离,只有一条是没有碰撞的正确指示,但利用人类的直觉是理解自然算法如何工作的开始。
They are not touching, which means that the distance between the two centerlines should be greater than touching, which means that the natural algorithm picks the horizontal centerlines (the vertical centerlines says there's a collision!). By noticing multiple circles, you can tell: if the circle intersects with the vertical extension of the square, then we pick the vertical distance (between the horizontal centerlines), and if the circle intersects with the horizontal extension, we pick the horizontal distance:
另一个例子,圆4:它与正方形的水平延伸相交,那么我们考虑水平距离等于接触。
Ok, the tough part is demystified, now we know how the algorithm will work, but how we know with which extension the circle intersects? It's easy actually: we calculate the distance between the most right x and the most left x (of both the circle and the square), and the same for the y-axis, the one with greater value is the axis with the extension that intersects with the circle (if it's greater than diameter+side then the circle is outside the two square extensions, like circle #7). The code looks like:
right = Math.max(square.x+square.side, circle.x+circle.rad);
left = Math.min(square.x, circle.x-circle.rad);
bottom = Math.max(square.y+square.side, circle.y+circle.rad);
top = Math.min(square.y, circle.y-circle.rad);
if (right - left > down - top) {
//compare with horizontal distance
}
else {
//compare with vertical distance
}
/*These equations assume that the reference point of the square is at its top left corner, and the reference point of the circle is at its center*/
我有一个方法可以避免昂贵的毕达哥拉斯,如果没有必要的话。当矩形和圆的包围框不相交时。
对非欧几里得也适用
class Circle {
// create the bounding box of the circle only once
BBox bbox;
public boolean intersect(BBox b) {
// test top intersect
if (lat > b.maxLat) {
if (lon < b.minLon)
return normDist(b.maxLat, b.minLon) <= normedDist;
if (lon > b.maxLon)
return normDist(b.maxLat, b.maxLon) <= normedDist;
return b.maxLat - bbox.minLat > 0;
}
// test bottom intersect
if (lat < b.minLat) {
if (lon < b.minLon)
return normDist(b.minLat, b.minLon) <= normedDist;
if (lon > b.maxLon)
return normDist(b.minLat, b.maxLon) <= normedDist;
return bbox.maxLat - b.minLat > 0;
}
// test middle intersect
if (lon < b.minLon)
return bbox.maxLon - b.minLon > 0;
if (lon > b.maxLon)
return b.maxLon - bbox.minLon > 0;
return true;
}
}
minLat、maxLat可替换为minY、maxY, minLon、maxLon也可替换为minX、maxX normDist方法比全距离计算快一点。例如,在欧几里得空间中没有平方根(或者没有很多其他的haversine): dat =(lat-circleY);dLon = (lon-circleX);赋范= dLat * dLat + dLon * dLon。当然,如果你使用normDist方法你需要创建一个normedDist = dist*dist;对于圆来说
查看我的GraphHopper项目的完整的BBox和Circle代码。