如何分辨圆和矩形在二维欧几里得空间中是否相交?(即经典二维几何)
当前回答
实际上,这要简单得多。你只需要两样东西。
首先,你需要找出从圆中心到矩形每条直线的四个正交距离。如果任意三个圆的半径大于矩形的半径,那么圆就不会与矩形相交。
其次,你需要找到圆中心和矩形中心之间的距离,那么你的圆不会在矩形内部如果距离大于矩形对角线长度的一半。
好运!
其他回答
我在制作这款游戏时开发了这个算法: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*/
这里有一个快速的单行测试:
if (length(max(abs(center - rect_mid) - rect_halves, 0)) <= radius ) {
// They intersect.
}
这是轴对齐的情况,其中rect_二分之一是一个正向量,从矩形的中间指向一个角。length()中的表达式是一个从矩形中心到最近点的增量向量。这适用于任何维度。
有一种非常简单的方法来做到这一点,你必须在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;
}
我的方法:
从OBB /矩形上/中的圆计算closest_point (最近点将位于边缘/角落或内部) 计算从closest_point到圆心的squared_distance (距离的平方避免了平方根) 返回squared_distance <=圆半径的平方
稍微改进一下e。james的回答:
double dx = abs(circle.x - rect.x) - rect.w / 2,
dy = abs(circle.y - rect.y) - rect.h / 2;
if (dx > circle.r || dy > circle.r) { return false; }
if (dx <= 0 || dy <= 0) { return true; }
return (dx * dx + dy * dy <= circle.r * circle.r);
这就减去了一次,而不是最多减去三次。