圆与矩形的碰撞检测算法


知道圆的圆心和半径,如何检测与矩形的碰撞?

Android 算法

Single魂 12 years, 10 months ago

可以这样来判断一个圆和一个矩形的碰撞检测:
一个矩形ABCD大概可以把一个二维空间分成9份,如下图所示:

请输入图片描述

那么可以先确定圆心位于这9个区域的哪一个(后面会详细讲述),然后分别判断:
1.如果是落在5号区域,那不用说,肯定是碰撞了。(如果内包含也算碰撞的话)
2.如果是落在1,3,7,9号区域,那么与圆心最近的点就分别是矩形的4个顶点了。可以根据圆心所在的区域,计算圆心与对应矩形顶点的距离,然后与半径进行比较来判断是否碰撞。
3.如果是落在2,4,6,8号区域,那么与圆心最近的点就是矩形的4条边上的点了。可以根据圆心所在的区域,计算圆心与对应的矩形边的距离,然后与半径进行比较来判断是否碰撞。
这样就可以判断圆与矩形的碰撞了。
第1种情况不用说,直接下结论,圆与矩形碰撞了。
第2种情况只需要计算圆心与某一个矩形顶点的距离,十分简单。例如:如果圆心落在1号区域,则只需要判断圆心到A点的距离与半径的大小即可,因为此时A点是矩形中距离圆心最近的点。
第3种情况需要求圆心O到对应边所在的直线的距离。例如:如果圆心落在2号区域,则只需要判断圆心到边AB所在的直线的距离与半径的大小即可。可以使用向量射影公式推导。示例图如下:

请输入图片描述

先求出AB边所在的直线方程式mx+ny+k=0的参数m和n,则直线的方向向量为f=(-n,m),直线的法向量为g=(m,n),设O(x0,y0),B(x2,y2),垂足为R,则
向量OB=(x2-x0,y2-y0),则圆心O到边AB的距离为:

   
  d = | OB * g | / | g |
  
= |[(x2 - x0) * m + (y2 - y0) * n]| / Math.sqrt(m * m + n * n)

// 因为B在直线上,所以有x2 * m + y2 * n + k = 0,代入上式化简即可得到下面的结果

= (x0 * m + y0 * n + k) / Math.sqrt(m * m + n * n)

可以发现,对于给定直线mx+ny+k=0和给定点O(x0,y0)来说,点O到直线的距离就等于把点O的x和y坐标分别作为x和y值代入直线方程求得的值,除以直线方程中x和y的系数的平方和的方根,即可得到点O到直线的距离。

确定圆心所在的区域的方法 是:
设圆心是O, 逆时针 遍历矩形的4条边,每遍历一条边,例如AC,则通过矢量的叉积来判断点O位于矢量AC的左边还是右边。
设A(x1,y1),C(x2,y2),O(x0,y0),则构造的两个矢量分别是:
AC=(x2-x1,y2-y1), AO=(x3-x1,y3-y1)
则AC和AO的叉积为:(2*2的行列式)

|x2-x1, y2-y1|

|x3-x1, y3-y1|

值为:r = (x2-x1) (y3-y1) - (y2-y1) (x3-x1)

利用右手法则进行判断:
如果r>0,则点O位于矢量AC的左边。
如果r<0,则点O位于矢量AC的右边。
这样就可以分别计算出圆心O与矩形的4条矢量边(注意,这些矢量边是逆时针遍历得到的)的相对方位,就可以确定圆心O的区域了:(这里设f(AC,O) = -1 代表圆心O位于矢量边AC的左边,f(AC,O) = 1 代表圆心O位于矢量边AC的左边)
1.如果圆心O位于每一条矢量边的左边,则圆心O在5号区域,即矩形内部。
2.如果圆心O位于三条矢量边的左边,而位于第4条矢量边的右边,则圆心O在第4条矢量边的右边的区域。例如:假设f(AC,O) = 1, f(CD,O) = 1, f(DB,O) = 1, f(BA,O) = -1, 即圆心O位于矢量边AC,CD,DB的左边,但是位于矢量边BA的右边,那么圆心O就在矢量边BA右边的区域,即2号区域。其他4,6,8号区域同理。
3.如果圆心O位于两条矢量边的左边,而位于两外两条矢量边的右边,则圆心O所在的区域是使其位于右边的两条矢量边公共顶点45度往外延伸的区域。例如,假设f(AC,O) = -1, f(CD,O) = 1, f(DB,O) = 1, f(BA,O) = -1, 即圆心O位于矢量边AC和BA的右边,而位于矢量边CD和DB的左边,那么圆心O所在区域就是矢量边AC和BA的公共点A点45度往外延伸的区域,即1号区域。其他3,7,9号区域同理。
这样就可以判断圆心O所在的区域了。

mizia answered 12 years, 10 months ago

Your Answer