您现在的位置：程式碼之家 >> 編程語言 > >> Java 程式設計 >> J2ME

2D 碰撞檢測算法實現：矩形重疊、線段相交與交點計算

編輯：J2ME

遊戲開發與圖形應用中，高效精確的碰撞檢測是核心基礎模塊。本文提供三個經過優化的靜態工具方法：矩形包圍盒快速剔除、線段相交判定、線段交點/重疊段計算，均採用整數運算避免浮點誤差，適合 J2ME 等資源受限環境。

1. 矩形重疊測試 (AABB)

public static boolean rectHitTest(int x1, int y1, int x2, int y2,
                                  int x3, int y3, int x4, int y4) {
    // 快速分離軸判斷：任一軸投影不重疊則無碰撞
    if (Math.max(x1, x2) < Math.min(x3, x4) ||
        Math.max(y1, y2) < Math.min(y3, y4) ||
        Math.min(x1, x2) > Math.max(x3, x4) ||
        Math.min(y1, y2) > Math.max(y3, y4)) {
        return false;
    }
    return true;
}

採用 分離軸定理 (SAT) 一維投影邏輯，四次比較即可判定，極其高效，常作為複雜形狀碰撞的 Broad Phase 廉價剔除。

2. 線段相交測試

public static boolean segmentHitTest(int x1, int y1, int x2, int y2,
                                     int x3, int y3, int x4, int y4) {
    // Phase 1: 包圍盒快速剔除
    if (!rectHitTest(x1, y1, x2, y2, x3, y3, x4, y4)) return false;

    // Phase 2: 向量叉積法判斷跨立關係
    // 向量 AC × AB 與 AD × AB 異號 => C、D 在 AB 兩側
    // 向量 CA × CD 與 CB × CD 異號 => A、B 在 CD 兩側
    // 兩條件同時滿足 => 線段相交
    return (vectorProduct(x1 - x3, y1 - y3, x4 - x3, y4 - y3) *
            vectorProduct(x2 - x3, y2 - y3, x4 - x3, y4 - y3) <= 0) &&
           (vectorProduct(x3 - x1, y3 - y1, x2 - x1, y2 - y1) *
            vectorProduct(x4 - x1, y4 - y1, x2 - x1, y2 - y1) <= 0);
}

private static int vectorProduct(int x1, int y1, int x2, int y2) {
    return x1 * y2 - x2 * y1; // 叉積 Z 分量
}

利用 向量叉積符號 判斷點在有向線段兩側，結合包圍盒預檢，實現 O(1) 精確相交判定，自動處理共線重疊情況（返回 true）。

3. 線段交點 / 重疊段計算


/**
 * @return int[] 
 *   null          - 不相交
 *   length=2 [x,y] - 單一交點
 *   length=4 [x1,y1,x2,y2] - 共線重疊段兩端點
 */
public static int[] segmentHitPoint(int x1, int y1, int x2, int y2,
                                    int x3, int y3, int x4, int y4) {
    if (!segmentHitTest(x1, y1, x2, y2, x3, y3, x4, y4)) return null;

    final int MATH_SHIFT = 10; // 定點數精度位移 (1024x)
    int k1, k2, a1, a2, x, y;

    // 情況 1: 兩線段均垂直 (x1==x2 && x3==x4)
    if (x1 == x2 && x3 == x4 && x1 == x3) {
        return getOverlapSegmentOnVerticalLine(x1, y1, y2, y3, y4);
    }
    // 情況 2: 第一段垂直
    else if (x1 == x2) {
        k2 = fixedPointDiv(y3 - y4, x3 - x4);
        a2 = y3 - fixedPointMul(k2, x3);
        x = x1;
        y = fixedPointMul(k2, x) + a2;
    }
    // 情況 3: 第二段垂直
    else if (x3 == x4) {
        k1 = fixedPointDiv(y1 - y2, x1 - x2);
        a1 = y1 - fixedPointMul(k1, x1);
        x = x3;
        y = fixedPointMul(k1, x) + a1;
    }
    // 情況 4: 一般情況
    else {
        k1 = fixedPointDiv(y1 - y2, x1 - x2);
        k2 = fixedPointDiv(y3 - y4, x3 - x4);
        if (k1 == k2) { // 平行共線
            return getOverlapSegmentOnLine(x1, y1, x2, y2, x3, y3, x4, y4);
        }
        a1 = y1 - fixedPointMul(k1, x1);
        a2 = y3 - fixedPointMul(k2, x3);
        x = fixedPointDiv(a2 - a1, k1 - k2);
        y = fixedPointMul(k1, x) + a1;
    }
    return new int[]{x, y};
}

// 定點數輔助運算 (模擬定點數避免浮點)
private static int fixedPointMul(int a, int b) { return (a * b) >> MATH_SHIFT; }
private static int fixedPointDiv(int a, int b) { return (a << MATH_SHIFT) / b; }