大家好，我是前端西瓜哥。今天來(lái)講講幾何算法中，比較經(jīng)典的算法：矩形碰撞和包含檢測(cè)算法。

矩形碰撞檢測(cè)是被廣泛使用的算法。

比如在游戲中，為了優(yōu)化圖形碰撞判斷效率（復(fù)雜不規(guī)則圖形之間的碰撞算法很復(fù)雜），經(jīng)常會(huì)使用到包圍盒。

所謂包圍盒子是一個(gè)矩形，通常正好包圍住一個(gè)規(guī)則或不規(guī)則的圖形。如果兩個(gè)圖形的包圍盒沒(méi)有發(fā)生碰撞，那這兩個(gè)圖形一定不會(huì)發(fā)生碰撞，因?yàn)榫匦蔚呐鲎菜惴ê芎?jiǎn)單，所以能夠很好地優(yōu)化性能。

算法實(shí)現(xiàn)

考慮到有些讀者對(duì)原理不感興趣，想趕緊找到算法復(fù)制粘貼，很急，我這里先直接貼上代碼實(shí)現(xiàn)。

判斷矩形是否碰撞：

function isRectIntersect(rect1, rect2) {
  return (
    rect1.x <= rect2.x + rect2.width &&
    rect1.x + rect1.width >= rect2.x &&
    rect1.y <= rect2.y + rect2.height &&
    rect1.y + rect1.height >= rect2.y
  );
}

判斷矩形 1 是否包含矩形 2：

function isRectContain(rect1, rect2) {
  return (
    rect1.x <= rect2.x &&
    rect1.x + rect1.width >= rect2.x + rect2.width &&
    rect1.y <= rect2.y &&
    rect1.y + rect1.height >= rect2.y + rect2.height
  );
}

矩形碰撞檢測(cè)原理

首先明確矩形的定義。我們用 4 個(gè)屬性來(lái)描述一個(gè)矩形，分別為 x、y、width、height，表示矩形的左上角位置和尺寸。

這里用主流的坐標(biāo)系統(tǒng)表示，以屏幕左上角為原點(diǎn)，x軸正方向向右，y 軸正方形向下。

或者我們可以用 minX、minY、maxX，minY 來(lái)表示：

矩形碰撞，也叫矩形相交。矩形發(fā)生碰撞的條件是：兩個(gè)矩形有重疊的區(qū)域。

下圖是兩個(gè)矩形碰撞的一些情況：

先看 x 維度，將兩個(gè)矩形往 x 軸線上投影，我們得到兩條線段。

矩形要相交，首先 x 的范圍上就應(yīng)該有交集，等價(jià)于判斷兩個(gè)線段是否有交點(diǎn)。

先看看什么情況下它們 不會(huì)相交？答案是：一條線段的右端點(diǎn)在另一條線的的左端點(diǎn)的左側(cè)。

所以相交的邏輯是：

!(rect1.x > rect2.x + rect2.width || rect1.x + rect1.width < rect2.x)

轉(zhuǎn)換一下，就是：

rect1.x <= rect2.x + rect2.width &&
rect1.x + rect1.width >= rect2.x

y 維度同理，為：

rect1.y <= rect2.y + rect2.height &&
rect1.y + rect1.height >= rect2.y

所以最終算法實(shí)現(xiàn)為：

function isRectIntersect(rect1: IRect, rect2: IRect) {
  return (
    rect1.x <= rect2.x + rect2.width && // minX1 <maxX
    rect1.x + rect1.width >= rect2.x &&
    rect1.y <= rect2.y + rect2.height &&
    rect1.y + rect1.height >= rect2.y
  );
}

矩形包含原理

思路類似矩形碰撞。

也是判斷兩條線段的位置關(guān)系，rect 1 包含 rect 2，首先在 x 維度上需要滿足 rect 2 的兩個(gè)點(diǎn)都在 rect 1 的 x 范圍內(nèi)。

代碼為：

rect1.x <= rect2.x &&
rect1.x + rect1.width >= rect2.x + rect2.width

y 同理，最終代碼實(shí)現(xiàn)為：

function isRectContain(rect1, rect2) {
  return (
    rect1.x <= rect2.x &&
    rect1.x + rect1.width >= rect2.x + rect2.width &&
    rect1.y <= rect2.y &&
    rect1.y + rect1.height >= rect2.y + rect2.height
  );
}

結(jié)尾

矩形算法的碰撞和包含算法，思路是降低維度，分解為判斷線段的相交關(guān)系。