已知一多邊形，如何求得與其重合度最高的矩形？

已知一多邊形的頂點組成的集合，如何求得與其重合度最高的矩形？

設多邊形為A，結果矩形為B，「重合度最高」就是使得的 A xor B 面積最小，也就是使得 A和B的並集-A和B的交集 面積最小。

另外，我猜想A的質心（這個用opencv可以輕易的求出來）應當和B的中心是重合的。

如圖，已知黑色的多邊形，怎麼求得紅色的矩形，使得灰色區域面積最小？

---

我的演算法是這樣的：

你上面的圖是凸多邊形，我就拿一個極端的凹多邊形來試試：

這個多邊形夠極端吧（帶個把）

題主所說的找到此圖形的質心。這個方向是對的。假設此圖的質心是O點。如下圖：

如上圖所指，我們找到了質心，然後我們要確定最適合的矩形的朝向（向哪個方向傾斜）

這樣我們遍歷A圖形的所有頂點，找到離O點最遠的那個點定為F點。應該是下圖這個點：

然後以O到F建立X軸：

然後垂直於x-axis建立y軸。

以下是一個動態調節的過程（想像一下攝像機焦距的對焦過程）

以O點為出發向+X方向移動一條平行於y軸的平行線，直到與圖形A不相交即到達F點。如下圖

同樣的過程向-x方向發射一條平行線，到達圖形的最遠端，如下圖：

還剩剩餘y軸兩個方向，同樣這樣處理，最後如圖：

其實就是一個包裹A圖形的最小矩形ABCD.

下面是動態調節的過程，保持AB:BD的比例（保持此矩形的長寬比），縮小此矩形，直到此矩形的面積 = A圖形的面積。如下圖：

然後黑色矩形就是題主所要求的重合度最高的矩形。

如果有什麼問題，也請幫忙指正一下。

--------------------------------------------------------------------------------------- @孫鵬飛

針對有人說一下圖形不適合，我也簡單做了下示意圖，我沒有電腦驗證過，我基本認為也是可以解決的。P為到質心的最遠點，以確定X軸的方向。

---

OpenCV里有boundingRect函數，不謝！

---

如果能確定矩形的方位，二分兩邊長應該可以搞定。

---

多邊形擬合，先逐步減少擬合所需要的點數，最後簡化為一個四邊形，再去求最接近這個四邊形的矩形，循序漸進，肯定有部分特例，但是這種方法比較穩定而且實用

---

一個想法，不一定對。軸向的確定是不是可以通過找到一維投影最大的連續峰所在的方向，取投影方向作為矩形的一軸？

另一個想法，也不一定對。利用主成分提取？

---

實在不行遺傳演算法吧.....

---

@葉蔚 你的方法這奇葩形狀不適用

---

推薦閱讀：