圆-矩形碰撞检测(相交)

Question

圆-矩形碰撞检测(相交)

如何判断二维欧几里德空间中的圆与矩形是否相交？(即经典的二维几何)

Answer 1

当圆与矩形相交时，只有两种情况：要么圆心位于矩形内，要么矩形的一个边在圆中有一个点。请注意，这并不要求矩形是轴平行的。(一种观察方法是：如果圆中没有一个点(如果所有的边都“在”圆之外)，那么圆仍然可以与多边形相交的唯一方法是它完全位于多边形内。)有了这个洞察力，下面这样的东西就能工作了，在那里圆圈有中心。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到行足够近，并且在端点之间，否则检查终结点。最酷的是同IDEA不仅适用于矩形，而且适用于圆与任意一个圆的交点。简单多边形-甚至不一定是凸的！

Answer 2

我会这样做：bool&nbsp;intersects(CircleType&nbsp;circle,&nbsp;RectType&nbsp;rect) { &nbsp;&nbsp;&nbsp;&nbsp;circleDistance.x&nbsp;=&nbsp;abs(circle.x&nbsp;-&nbsp;rect.x); &nbsp;&nbsp;&nbsp;&nbsp;circleDistance.y&nbsp;=&nbsp;abs(circle.y&nbsp;-&nbsp;rect.y); &nbsp;&nbsp;&nbsp;&nbsp;if&nbsp;(circleDistance.x&nbsp;>&nbsp;(rect.width/2&nbsp;+&nbsp;circle.r))&nbsp;{&nbsp;return&nbsp;false;&nbsp;} &nbsp;&nbsp;&nbsp;&nbsp;if&nbsp;(circleDistance.y&nbsp;>&nbsp;(rect.height/2&nbsp;+&nbsp;circle.r))&nbsp;{&nbsp;return&nbsp;false;&nbsp;} &nbsp;&nbsp;&nbsp;&nbsp;if&nbsp;(circleDistance.x&nbsp;<=&nbsp;(rect.width/2))&nbsp;{&nbsp;return&nbsp;true;&nbsp;}&nbsp; &nbsp;&nbsp;&nbsp;&nbsp;if&nbsp;(circleDistance.y&nbsp;<=&nbsp;(rect.height/2))&nbsp;{&nbsp;return&nbsp;true;&nbsp;} &nbsp;&nbsp;&nbsp;&nbsp;cornerDistance_sq&nbsp;=&nbsp;(circleDistance.x&nbsp;-&nbsp;rect.width/2)^2&nbsp;+ &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;(circleDistance.y&nbsp;-&nbsp;rect.height/2)^2; &nbsp;&nbsp;&nbsp;&nbsp;return&nbsp;(cornerDistance_sq&nbsp;<=&nbsp;(circle.r^2)); }下面是它的工作原理：第一对直线计算圆心和矩形中心之间x和y差值的绝对值。这会将四个象限折叠成一个，这样计算就不必再做四次了。这张图显示了圆心现在必须放置的区域。注意，只显示了一个象限。矩形是灰色区域，红色边框勾勒出与矩形边缘正好有一个半径的临界区域。圆的中心必须在这个红色的边界内，才能发生交点。第二对线消除了简单的情况，即圆离矩形足够远(在任一方向)，不可能相交。这与图像中的绿色区域相对应。第三对线处理简单的情况，即圆足够接近矩形(在任一方向)，以保证一个交点。这对应于图像中的橙色和灰色部分。注意，这个步骤必须在步骤2之后完成，这样逻辑才有意义。其余的线计算出圆圈可能与矩形角相交的困难情况。若要求解，请计算从圆心到拐角的距离，然后验证距离不大于圆的半径。此计算对中心位于红色阴影区域内的所有圆返回false，对于中心位于白阴影区域内的所有圆返回true。