橢圓與矩形碰撞檢測演算法：整數運算高效實作

問題定義

判斷橢圓（中心 (x0,y0)、X 半徑 rx、Y 半徑 ry）與矩形（左上 (xmin,ymin)、右下 (xmax,ymax)）是否相交。避免浮點運算，全程使用 32-bit 整數運算，適合 J2ME 等無 FPU 環境。

數學原理

橢圓方程式：(x/rx)² + (y/ry)² = 1。
兩邊同乘 (rx·ry)² 得整數判別式：
left = (dx·ry)² + (dy·rx)²
right = (rx·ry)²
若 left ≤ right 則點在橢圓內或邊界上。

演算法步驟

1. 若橢圓中心落在矩形內，直接回傳 true。
2. 找出矩形上距離中心最近的點 (x,y)：
   x = clamp(x0, xmin, xmax)
y = clamp(y0, ymin, ymax)
3. 計算 dx = x - x0、dy = y - y0。
4. 代入判別式比較。

完整 Java 實作

public static final boolean isCollide(int x0, int y0, int rx, int ry,
                                      int xmin, int ymin, int xmax, int ymax) {
    // 1. 圓心在矩形內
    if (x0 >= xmin && x0 <= xmax && y0 >= ymin && y0 <= ymax) {
        return true;
    }
    // 2. 最近點
    int x = x0 < xmin ? xmin : (x0 > xmax ? xmax : x0);
    int y = y0 < ymin ? ymin : (y0 > ymax ? ymax : y0);
    // 3. 判別式
    int dx = x - x0;
    int dy = y - y0;
    dx *= dx; dy *= dy;
    rx *= rx; ry *= ry;
    dx *= ry; dy *= rx;
    return (dx + dy) <= (rx * ry);
}

效能與精度分析

• 零浮點運算：適合 CLDC 1.0/1.1 無 FPU 裝置。
• 整數溢位風險：rx, ry ≤ 46340 時 rx*ry 不會溢位 32-bit signed int。遊戲座標通常遠小於此值。
• 分支預測友善：僅含簡單比較與算術，極適合即時遊戲迴圈。

擴展應用

• 圓形碰撞：rx = ry = radius 即為圓矩相交。
• 旋轉矩形：先將矩形頂點反向旋轉至橢圓座標系，再套用本演算法。
• 廣義檢測：先用包圍箱快速剔除，再精測橢圓。

結語

此整數版橢圓矩形碰撞檢測兼顧效能與精度，是 J2ME 遊戲開發物理引擎的核心基石之一。