計算多邊形的最小面積矩形

Question

我需要計算多邊形周圍的最小面積矩形（最小可能的矩形）。

我唯一的輸入是多邊形中的點數。

我也有點的協調。

Answer 1

將rotating calipers算法用於凸多邊形，否則使用凸包。你當然需要多邊形中點的座標，而不僅僅是點的數量。

Answer 2

顯然，您需要點的座標才能得到答案。如果矩形與X和Y aces對齊，那麼解決方案很簡單。如果你想要任何角度的最小矩形，那麼你需要做一些優化過程。

Answer 3

這叫做Minimum Bounding Box，它是OCR包中使用的最基本的算法。您可以使用OpenCV包裝中的旋轉卡尺來查找實現。一旦你的源代碼，看看這個文件，

cv/src/cvrotcalipers.cpp 

你需要的方法是cvMinAreaRect2()。

Answer 4

首先做一個grahm-scan並得到一組點的convex hull。然後，你可以使用像minimum rectangle discussed here

Answer 5

按照下面的算法

1. 多邊形旋轉到XY平面
2. 選1個邊緣和調整與X軸（使用反正切）這個邊緣。使用min/max x，y查找邊界矩形。計算區域並存儲在列表中
3. 對剪切後的多邊形中的其餘邊執行相同操作。
4. 選取最小面積的矩形。
5. 旋轉邊界矩形回的步驟1和步驟2

用於更詳細地檢查鏈接Minimum-Area-Rectangle