資訊專欄INFORMATION COLUMN
摘要：設(shè)計(jì)一個(gè)算法，確定兩個(gè)矩形是否相交即有重疊區(qū)域如果兩個(gè)矩形相交，設(shè)計(jì)一個(gè)算法，求出相交的區(qū)域矩形對(duì)于這個(gè)問題，一般的思路就是判斷一個(gè)矩形的四個(gè)頂點(diǎn)是否在另一個(gè)矩形的區(qū)域內(nèi)。這樣，可以依據(jù)的值來判斷矩形相交。
問題：給定兩個(gè)矩形A和B，矩形A的左上角坐標(biāo)為（Xa1,Ya1），右下角坐標(biāo)為（Xa2,Ya2），矩形B的左上角坐標(biāo)為（Xb1,Yb1），右下角 坐標(biāo)為（Xb2,Yb2）。
（1）設(shè)計(jì)一個(gè)算法，確定兩個(gè)矩形是否相交（即有重疊區(qū)域）
（2）如果兩個(gè)矩形相交，設(shè)計(jì)一個(gè)算法，求出相交的區(qū)域矩形
(1) 對(duì)于這個(gè)問題，一般的思路就是判斷一個(gè)矩形的四個(gè)頂點(diǎn)是否在另一個(gè)矩形的區(qū)域內(nèi)。這個(gè)思路最簡(jiǎn)單，但是效率不高，并且存在錯(cuò)誤，錯(cuò)誤在哪里，下面分析一 下。
如上圖，把矩形的相交（區(qū)域重疊）分成三種（可能也有其他劃分），對(duì)于第三種情況，如圖中的（3），兩個(gè)矩形相交，但并不存在一個(gè)矩形的頂點(diǎn)在另一個(gè)矩形 內(nèi)部。所以那種思路存在一個(gè)錯(cuò)誤，對(duì)于這種情況的相交則檢查不出。
仔細(xì)觀察上圖，想到另一種思路，那就是判斷兩個(gè)矩形的中心坐標(biāo)的水平和垂直距離，只要這兩個(gè)值滿足某種條件就可以相交。
矩形A的寬 Wa = Xa2-Xa1 高 Ha = Ya2-Ya1
矩形B的寬 Wb = Xb2-Xb1 高 Hb = Yb2-Yb1
矩形A的中心坐標(biāo) (Xa3,Ya3) = （ (Xa2+Xa1)/2 ，(Ya2+Ya1)/2 ）
矩形B的中心坐標(biāo) (Xb3,Yb3) = （ (Xb2+Xb1)/2 ，(Yb2+Yb1)/2 ）
所以只要同時(shí)滿足下面兩個(gè)式子，就可以說明兩個(gè)矩形相交。
1） | Xb3-Xa3 | <= Wa/2 + Wb/2
2） | Yb3-Ya3 | <= Ha/2 + Hb/2
即：
| Xb2+Xb1-Xa2-Xa1 | <= Xa2-Xa1 + Xb2-Xb1
| Yb2+Yb1-Ya2-Ya1 | <=Y a2-Ya1 + Yb2-Yb1
附上js實(shí)現(xiàn)
intersect = function(rect1, rect2) {
var half1Width = rect1.width / 2,
half1Height = rect1.height / 2,
half2Width = rect2.width / 2,
half2Height = rect2.height / 2,
cen1 = {
x: rect1.x + half1Width,
y: rect1.y + half1Height
},
cen2 = {
x: rect2.x + half2Width,
y: rect2.y + half2Height
};
return Math.abs(cen2.x - cen1.x) <= half1Width + half2Width &&
Math.abs(cen2.y - cen1.y) <= half1Height + half2Height;
};
(2) 對(duì)于這個(gè)問題，假設(shè)兩個(gè)矩形相交，設(shè)相交之后的矩形為C，且矩形C的左上角坐標(biāo)為（Xc1,Yc1），右下角坐標(biāo)為（Xc2,Yc2），經(jīng)過觀察上圖，很 顯然可以得到：
Xc1 = max(Xa1,Xb1)
Yc1 = max(Ya1,Yb1)
Xc2 = min(Xa2,Xb2)
Yc2 = min(Ya2,Yb2)
這樣就求出了矩形的相交區(qū)域。
另外，注意到在不假設(shè)矩形相交的前提下，定義（Xc1,Yc1）,（Xc2,Yc2）,且Xc1,Yc1,Xc2,Yc2的值由上面四個(gè)式子得出。這樣， 可以依據(jù)Xc1,Yc1,Xc2,Yc2的值來判斷矩形相交。
Xc1,Yc1,Xc2,Yc2只要同時(shí)滿足下面兩個(gè)式子，就可以說明兩個(gè)矩形相交。
3) Xc1 <= Xc2
4) Yc1 <= Yc2
即：
max(Xa1,Xb1) <= min(Xa2,Xb2)
max(Ya1,Yb1) <= min(Ya2,Yb2)
宣傳下我的區(qū)塊管理框架Magix：https://github.com/thx/magix
歡迎試用Magix、star與fork
文章版權(quán)歸作者所有，未經(jīng)允許請(qǐng)勿轉(zhuǎn)載,若此文章存在違規(guī)行為，您可以聯(lián)系管理員刪除。
轉(zhuǎn)載請(qǐng)注明本文地址：http://systransis.cn/yun/87821.html
摘要：避讓算法采用的是四分位模型算法，接下來手把手教你寫避讓算法，老司機(jī)帶你裝逼帶你飛。創(chuàng)建四分位模型所謂四分位模型，每一個(gè)標(biāo)記點(diǎn)都有上下左右四個(gè)放文字的位子，如果左邊放不下，那就放右邊試試，還不行就放到下面試試，以此類推，原理就這么簡(jiǎn)單，哈哈。 本文作者：TalkingData 可視化工程師李鳳祿編輯：Aresn inMap 是一款基于 canvas 的大數(shù)據(jù)可視化庫，專注于大數(shù)據(jù)方向點(diǎn)線...
摘要：微信端口的小游戲相信大家已經(jīng)做了很多類似于碰撞檢測(cè)這種也是數(shù)不勝數(shù)因?yàn)檎系K物和主角都是圖片也就意味著碰撞檢測(cè)實(shí)際上是兩個(gè)矩形直接是否有交叉的判斷包括這樣的框架也是這樣子做的當(dāng)然這種方法也無可厚非然而唯一的問題是如果素材障礙物和主角并不能鋪滿 微信端口的小游戲相信大家已經(jīng)做了很多,類似于碰撞檢測(cè)這種也是數(shù)不勝數(shù).因?yàn)檎系K物和主角都是圖片,也就意味著碰撞檢測(cè)實(shí)際上是兩個(gè)矩形直接是否有交叉...
摘要：本文作者可視化工程師李鳳祿是可視化團(tuán)隊(duì)開源的一款基于的大數(shù)據(jù)可視化庫，專注于大數(shù)據(jù)方向點(diǎn)線面的可視化效果展示。目前支持散點(diǎn)圍欄熱力網(wǎng)格聚合等方式致力于讓大數(shù)據(jù)可視化變得簡(jiǎn)單易用。后續(xù)會(huì)輸出創(chuàng)造更好的可視化圖形和算法，并后續(xù)推出版本。 showImg(https://segmentfault.com/img/bV0yHB?w=1600&h=900); 本文作者：TalkingData 可...
閱讀 2665·2021-11-25 09:43
閱讀 684·2021-11-12 10:36
閱讀 4654·2021-11-08 13:18
閱讀 2194·2021-09-06 15:00
閱讀 3127·2019-08-30 15:56
閱讀 946·2019-08-30 13:57
閱讀 2002·2019-08-30 13:48
閱讀 1426·2019-08-30 11:13
