將凸多邊形擬合到給定的矩形中

Question

我想通過旋轉和縮放將凸多邊形合併到給定的矩形中。

我的方法是以小步驟旋轉多邊形（如1°）並始終測量分數（最大水平距離/最大垂直距離），取最接近分數的矩形（矩形寬度/矩形高度）和將其縮放以適合矩形。

我不知道是否有一個「不太原始」的方法。此外，與僅測量最大水平和垂直距離相比，可能有更好的「最佳擬合」定義。我的真正目標是讓多邊形「看起來不錯」，當我將它存儲爲圖像文件或將其打印在頁面上時。

Answer 1

您可以使用像rotating calipers這樣的方法。

雖然旋轉卡尺算法找到具有兩條平行線的反對頂點對，但您需要四條垂直線 - 邊界矩形。

選擇第一個頂點，找到它的反對頂點 - 它是第一個卡尺對。
構建與第一個卡尺垂直的第二個卡尺對。
將兩個卡尺對旋轉到一起，直到找到下一個反平面對（在第一個卡尺之間或在第二個卡尺之間） - 確定下一個極值角點。
繼續旋轉卡鉗。

邊界矩形的寬度和高度將在極值點之間連續變化。寬度/高度比例也會持續。所以如果你發現在第i個極值點W/H < P和第（i + 1）個極值點W/H> P，其中P是需要的比例，那麼區間i..i + 1包含需要的P值（Bolzano's theorem）。

當您找到與解決方案的區間（如果存在），只需計算在此角度間隔（三角方程）的卡尺寬度的比例並獲得精確的角度值。三角方程似乎看起來

Sin(A)/Sin(A + Pi/2) = F 
or 
Sin(A)/Cos(A) = Tan(A) = F