圓形與矩形碰撞（無旋轉矩形）

-

承上一篇，接下來是檢定圓形和矩形的碰撞，想法來自這篇 StackOverflow : Circle-Rectangle collision detection (intersection) ，不過這個只能檢定擺正沒有經過旋轉的矩形，即邊長平行兩軸的矩形，例如：


檢定分成三個部份，由於圓形只會靠近一個角落，所以將矩形切割成四個部份，只討論一個角落，碰撞檢定是全部一起看的，只是接下來圖片的呈現只用右上角為例。


第一部份，最先排除足夠遠的可能

如上圖，當圓形夠遠的情形先排除掉，例如圖中紅色的區域，當圓形的圓心在紅色區域時，兩圖形必不相交，那判斷的依據是什麼呢？

當圓形的圓心和矩形的中心（對角線交點）的水平距離超過矩形寬度的一半加上圓半徑，圓形和矩形就足夠遠不會相交，同理圓心和矩形中心的鉛直距離超過矩形高度的一半加上圓半徑，也不會相交，這時候圓心就會落在紅色區域，兩圖形就不會碰撞。此處要用的數據有：

  • 兩中心的水平差 = |圓心 x 坐標 - 矩形中心 x 坐標|
  • 兩中心的鉛直差 = |圓心 y 坐標 - 矩形中心 y 坐標|
  • 矩形寬度的一半 + 圓半徑
  • 矩形高度的一半 + 圓半徑

第二部份，討論餘下之中，足夠近的情形。

經過第一部份，剩下的兩圖形之中心的可能，會被限制在「水平差 <= 矩形寬的一半 + 圓半徑」，而且「鉛直差 <= 矩形高的一半 + 圓半徑」，此時圓心會落在上圖的藍色與黃色區域內，如上圖。

在此情形下如果又更靠近，例如「鉛直差 <= 矩形高的一半」，又因為「水平差 <= 矩形寬的一半 + 圓半徑」則圓心落在黃色區域中，兩圖形就相交；同理如果「水平差 <= 矩形寬的一半」，又因為「鉛直差 <= 矩形高的一半 + 圓半徑」則圓心也落在黃色區域中，兩圖形相交。

要用的數據有：

  • 兩中心的水平差 = |圓心 x 坐標 - 矩形中心 x 坐標|
  • 兩中心的鉛直差 = |圓心 y 坐標 - 矩形中心 y 坐標|
  • 矩形寬度的一半
  • 矩形高度的一半


第三部份，細膩判斷角落的情形。

最後，就剩下在第二部份的圖片中藍色的正方形，這是以圓半徑圍成的正方形。圓心落在此處的圓可能與矩形相交，也可能不會：

如果圓形與矩形要有交點，考慮矩形的頂點和圓心的矩離，兩點之間距離要小於圓形的半徑，故反過來以矩形頂點為圓心畫一個四分之一圓：

當圓心落在上圖的淡藍色區域內，圓形就和矩形頂點相交或使頂點在圓內，兩圖形就碰撞。而那個距離就利用 ( 水平差 - 半寬長 ) 和 ( 鉛直差 - 半高長 ) 來畢氏定理，要用的數據有：

  • 兩中心的水平差 = |圓心 x 坐標 - 矩形中心 x 坐標|
  • 兩中心的鉛直差 = |圓心 y 坐標 - 矩形中心 y 坐標|
  • 矩形寬度的一半
  • 矩形高度的一半
  • ( 水平差 - 寬度的一半 )2 + ( 鉛直差 - 高度的一半 )2 和 ( 圓半徑 )2


Java code 參考如下： 
  public boolean isCircRectCollide(Circle circ, Rectangle rect) {

    int deltaX = Math.abs( circ.X() - rect.X() );      // 兩中心的水平差
    int deltaY = Math.abs( circ.Y() - rect.Y() );      // 兩中心的鉛直差
    double halfWidth = rect.Width() / 2f;              // 矩形寬度的一半
    double halfHeight = rect.Height() / 2f;            // 矩形高度的一半
    int radius = circ.Radius();                        // 圓半徑

    if(deltaX > halfWidth + radius || deltaY > halfHeight + radius) {
      return false;                            // 第一部份
    }

    if(deltaX <= halfWidth || deltaY <= halfHeight) {
      return true;                             // 第二部份
    }

    double distance = Math.pow(deltaX - halfWidth, 2) + Math.pow(deltaY - halfHeight, 2);
    return distance < Math.pow(radius, 2);     // 第三部份
  }

留言

張貼留言