矩形相交以及求出相交的區(qū)域的原理解析
(2)如果兩個(gè)矩形相交,設(shè)計(jì)一個(gè)算法,求出相交的區(qū)域矩形
(1) 對(duì)于這個(gè)問(wèn)題,一般的思路就是判斷一個(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è)式子,就可以說(shuō)明兩個(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
(2) 對(duì)于這個(gè)問(wèn)題,假設(shè)兩個(gè)矩形相交,設(shè)相交之后的矩形為C,且矩形C的左上角坐標(biāo)為(Xc1,Yc1),右下角坐標(biāo)為(Xc2,Yc2),經(jīng)過(guò)觀察上圖,很 顯然可以得到:
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的值來(lái)判斷矩形相交。
Xc1,Yc1,Xc2,Yc2只要同時(shí)滿足下面兩個(gè)式子,就可以說(shuō)明兩個(gè)矩形相交。
3) Xc1 <= Xc2
4) Yc1 <= Yc2
即:
max(Xa1,Xb1) <= min(Xa2,Xb2)
max(Ya1,Yb1) <= min(Ya2,Yb2)
相關(guān)文章
每個(gè)程序員都應(yīng)該學(xué)習(xí)使用Python或Ruby
在這篇文章里,我將會(huì)告訴你,為什么你一定要學(xué)習(xí)Python或Ruby語(yǔ)言2016-07-07Hadoop環(huán)境搭建過(guò)程中遇到的問(wèn)題及解決方法
這篇文章主要介紹了Hadoop環(huán)境搭建過(guò)程中遇到的問(wèn)題及解決方法,本文給大家介紹的非常詳細(xì),具有一定的參考借鑒價(jià)值,需要的朋友參考下吧2019-08-08Source?Insight?4.0.093?安裝破解詳細(xì)圖文教程
這篇文章主要介紹了Source?Insight?4.0.093?安裝破解詳細(xì)圖文教程,source?insight?4是一款非常強(qiáng)大的程序編輯器,如果你沒(méi)有一款合適的代碼編輯器,那么這款軟件不妨試試,可能你會(huì)喜歡2022-08-08matlab中乘法“*”和點(diǎn)乘“.*”;除法“/”和點(diǎn)除“./”的聯(lián)系和區(qū)別
這篇文章主要介紹了matlab中乘法“*”和點(diǎn)乘“.*”;除法“/”和點(diǎn)除“./”的聯(lián)系和區(qū)別,文中通過(guò)示例代碼介紹的非常詳細(xì),對(duì)大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價(jià)值,需要的朋友們下面隨著小編來(lái)一起學(xué)習(xí)學(xué)習(xí)吧2019-12-12Keil?uVision5?5.38官方下載、安裝及注冊(cè)超詳細(xì)圖文教程
這篇文章主要介紹了Keil?uVision5?5.38官方下載、安裝及注冊(cè)教程,本文通過(guò)圖文并茂的形式給大家介紹的非常詳細(xì),對(duì)大家的學(xué)習(xí)或工作具有一定的參考借鑒價(jià)值,需要的朋友可以參考下2023-03-03Trie樹(shù)_字典樹(shù)(字符串排序)簡(jiǎn)介及實(shí)現(xiàn)
有時(shí),我們會(huì)碰到對(duì)字符串的排序,若采用一些經(jīng)典的排序算法,則時(shí)間復(fù)雜度一般為O(n*lgn),但若采用Trie樹(shù),則時(shí)間復(fù)雜度僅為O(n)2014-03-03HTTP提交方式之PUT詳細(xì)介紹及POST和PUT的區(qū)別
這篇文章主要介紹了HTTP提交方式之PUT詳細(xì)介紹及POST和PUT的區(qū)別,本文簡(jiǎn)潔易懂,需要的朋友可以參考下2014-07-07關(guān)于數(shù)據(jù)處理包dplyr的函數(shù)用法總結(jié)
下面小編就為大家?guī)?lái)一篇關(guān)于數(shù)據(jù)處理包dplyr的函數(shù)用法總結(jié)。小編覺(jué)得挺不錯(cuò)的,現(xiàn)在就分享給大家,也給大家做個(gè)參考。一起跟隨小編過(guò)來(lái)看看吧2017-05-05