如何分辨圆和矩形在二维欧几里得空间中是否相交?(即经典二维几何)
当前回答
球面和矩形相交于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
它没有假设一个轴对齐的矩形,并且很容易扩展用于测试凸集之间的交集。
其他回答
为了可视化,拿你的键盘的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的回答,你会得到很好的解释。与此同时,忘记上面的第二条,除非你想要一个快速但冗余的检查。
假设你有矩形的四条边,检查从这些边到圆心的距离,如果小于半径,那么这些形状是相交的。
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
这里有另一个解决方案,实现起来非常简单(也非常快)。它将捕获所有的交点,包括当球体完全进入矩形时。
// 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行。
我有一个方法可以避免昂贵的毕达哥拉斯,如果没有必要的话。当矩形和圆的包围框不相交时。
对非欧几里得也适用
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代码。
圆与矩形相交只有两种情况:
圆的中心在矩形的内部,或者 矩形的一条边在圆上有一个点。
注意,这并不要求矩形与轴平行。
(一种方法是:如果没有一条边在圆中有点(如果所有的边都完全“在”圆外),那么圆仍然可以与多边形相交的唯一方法是它完全位于多边形内部。)
有了这样的见解,就可以像下面这样工作,其中圆的中心是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到直线的垂线的脚是否足够近并且在端点之间,否则检查端点。
最酷的是,同样的想法不仅适用于矩形,而且适用于一个圆与任何简单多边形的交点——甚至不必是凸多边形!