兩個矩形的相交面積，怎麼求演算法效率相對較高？

補充。矩形不一定平行坐標軸。

目前的做法是找一個完全包含兩個矩形的正的大矩形，判斷大矩形內的每個點是否在兩個小矩形中。程序效率較低。

---

題目不完整啊，沒有說矩形的邊是否平行於坐標軸，如果有旋轉的話... 這麼複雜的情況咱們還是不討論了吧 （其實就是我不會的意思）

那麼假設矩形的邊都平行於坐標軸，分別表示為(left1,top1,right1,bottom1), (left2,top2,right2,bottom2)，則相交部分必定也是矩形，算長x寬就可以啦

相交部分的寬，可以看成兩個矩形的寬，在x軸上的投影的長度

也就是兩條線段的總長度，減去重疊之後新線段的長度

按下圖示意，算出 A+B-W 就可以了

用矩形坐標套進去，就是 overlapX = (right1-left1)+(right2-left2) - ( max(right1,right2) - min(left1,left2) )

不管A B兩條線段怎麼移來移去，誰長誰短，這個式子都不變的，如果是&<=0，自然是沒有相交

同理再算出高就可以了。

---

這道題有兩種演算法。

1.直接求多邊形面積

多邊形的頂點包括以下兩部分：

1. 所有相交的線段交點；

2. 所有在對方內部的矩形頂點。

因此整個求解過程可以分為以下四步：

1. 找到所有的線段交點；

2. 找到所有的在對方內部的矩形頂點；

3. 求出以上兩個點集並的凸包；

4. 求出凸包面積。

2.半平面交

每個矩形都可以看作四個半平面的交，因此矩形面積交就等價於八個半平面交。

程序略，學習文中演算法可參考：

1. 求線段交點：談談"求線段交點"的幾種演算法(js實現,完整版)

2. 求點是否在多邊形內部：判斷點在多邊形內的多種寫法

3. 求凸包：凸包，計算幾何-經典演算法

4. 求多邊形面積：任意多邊形的面積公式

5. 半平面交：半平面相交_羅伯斯

感謝關注。

---

求矩形面積,再求多邊形面積,然後相減...

可以先判斷中點的連線距離是否長於對角線和的一半做一些預處理...

---

把矩形分解為像素進行運算

---

改進了下。先找矩形交點，再算多邊形面積。效率明顯高了 (o;TωT)o

---

兩點之間求長和點到直線的距離都是高中的知識吧？ 計算出兩個三角形的面積就可以了。

---

推薦閱讀：