判斷矩形相交以及求出相交的區域

kyanag 發布于2019-08-21 14:14 / 1842人閱讀

摘要：設計一個算法，確定兩個矩形是否相交即有重疊區域如果兩個矩形相交，設計一個算法，求出相交的區域矩形對于這個問題，一般的思路就是判斷一個矩形的四個頂點是否在另一個矩形的區域內。這樣，可以依據的值來判斷矩形相交。

問題：給定兩個矩形A和B，矩形A的左上角坐標為（Xa1,Ya1），右下角坐標為（Xa2,Ya2），矩形B的左上角坐標為（Xb1,Yb1），右下角坐標為（Xb2,Yb2）。
（1）設計一個算法，確定兩個矩形是否相交（即有重疊區域）
（2）如果兩個矩形相交，設計一個算法，求出相交的區域矩形

(1) 對于這個問題，一般的思路就是判斷一個矩形的四個頂點是否在另一個矩形的區域內。這個思路最簡單，但是效率不高，并且存在錯誤，錯誤在哪里，下面分析一下。

如上圖，把矩形的相交（區域重疊）分成三種（可能也有其他劃分），對于第三種情況，如圖中的（3），兩個矩形相交，但并不存在一個矩形的頂點在另一個矩形內部。所以那種思路存在一個錯誤，對于這種情況的相交則檢查不出。

仔細觀察上圖，想到另一種思路，那就是判斷兩個矩形的中心坐標的水平和垂直距離，只要這兩個值滿足某種條件就可以相交。
矩形A的寬 Wa = Xa2-Xa1 高 Ha = Ya2-Ya1
矩形B的寬 Wb = Xb2-Xb1 高 Hb = Yb2-Yb1
矩形A的中心坐標 (Xa3,Ya3) = （ (Xa2+Xa1)/2 ，(Ya2+Ya1)/2 ）
矩形B的中心坐標 (Xb3,Yb3) = （ (Xb2+Xb1)/2 ，(Yb2+Yb1)/2 ）
所以只要同時滿足下面兩個式子，就可以說明兩個矩形相交。
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實現

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) 對于這個問題，假設兩個矩形相交，設相交之后的矩形為C，且矩形C的左上角坐標為（Xc1,Yc1），右下角坐標為（Xc2,Yc2），經過觀察上圖，很顯然可以得到：
Xc1 = max(Xa1,Xb1)
Yc1 = max(Ya1,Yb1)
Xc2 = min(Xa2,Xb2)
Yc2 = min(Ya2,Yb2)
這樣就求出了矩形的相交區域。
另外，注意到在不假設矩形相交的前提下，定義（Xc1,Yc1）,（Xc2,Yc2）,且Xc1,Yc1,Xc2,Yc2的值由上面四個式子得出。這樣，可以依據Xc1,Yc1,Xc2,Yc2的值來判斷矩形相交。
Xc1,Yc1,Xc2,Yc2只要同時滿足下面兩個式子，就可以說明兩個矩形相交。
3) Xc1 <= Xc2
4) Yc1 <= Yc2
即：
max(Xa1,Xb1) <= min(Xa2,Xb2)
max(Ya1,Yb1) <= min(Ya2,Yb2)

宣傳下我的區塊管理框架Magix：https://github.com/thx/magix

歡迎試用Magix、star與fork

GPU云服務器云服務器 php 數組相交判斷可視區域 js判斷所選區域免費的域名以及服務器

文章版權歸作者所有，未經允許請勿轉載,若此文章存在違規行為，您可以聯系管理員刪除。

轉載請注明本文地址：http://specialneedsforspecialkids.com/yun/87821.html

你不知道的前端算法之文字避讓

摘要：避讓算法采用的是四分位模型算法，接下來手把手教你寫避讓算法，老司機帶你裝逼帶你飛。創建四分位模型所謂四分位模型，每一個標記點都有上下左右四個放文字的位子，如果左邊放不下，那就放右邊試試，還不行就放到下面試試，以此類推，原理就這么簡單，哈哈。本文作者：TalkingData 可視化工程師李鳳祿編輯：Aresn inMap 是一款基于 canvas 的大數據可視化庫，專注于大數據方向點線...

yedf 2019-08-21 18:44 評論0 收藏0
H5中優化碰撞檢測

摘要：微信端口的小游戲相信大家已經做了很多類似于碰撞檢測這種也是數不勝數因為障礙物和主角都是圖片也就意味著碰撞檢測實際上是兩個矩形直接是否有交叉的判斷包括這樣的框架也是這樣子做的當然這種方法也無可厚非然而唯一的問題是如果素材障礙物和主角并不能鋪滿微信端口的小游戲相信大家已經做了很多,類似于碰撞檢測這種也是數不勝數.因為障礙物和主角都是圖片,也就意味著碰撞檢測實際上是兩個矩形直接是否有交叉...

蘇丹 2019-08-22 11:05 評論0 收藏0
TalkingData 開源地理信息可視化框架 inMap

摘要：本文作者可視化工程師李鳳祿是可視化團隊開源的一款基于的大數據可視化庫，專注于大數據方向點線面的可視化效果展示。目前支持散點圍欄熱力網格聚合等方式致力于讓大數據可視化變得簡單易用。后續會輸出創造更好的可視化圖形和算法，并后續推出版本。 showImg(https://segmentfault.com/img/bV0yHB?w=1600&h=900); 本文作者：TalkingData 可...

xeblog 2019-08-22 11:21 評論0 收藏0