一組點的最大周長邊界矩形

Question

我一直在這個看似簡單的問題掙扎了很長一段時間。我給了一組點（我進一步簡化爲一個凸包），我的任務是找到一個包含它們的矩形（不一定是軸對齊的），沒有額外的空間（所以它是在點周圍緊身）並具有最大可能的周長。對我來說找到最小的那個並不麻煩，但這已被證明是一個更難以解決的問題。當搜索最小的邊界矩形時，我能夠使用這樣的假設：矩形邊的一邊總是與一個邊的邊對齊，但在這裏我沒有看到這種情況。我錯過了一些痛苦明顯的東西嗎？到目前爲止我唯一可以想到的方法是測試對角點對，如果它們可以投影到矩形的兩側並使用一些三角函數來最大化該函數，但我只是在計算中迷失了自己。

在此先感謝！

Answer 1

首先，計算點集的凸包。

現在，考慮旋轉多邊形並計算最小的包圍軸對齊的矩形。請注意，頂點，左側點，右側點和底點將圍繞從一個頂點到下一個頂點的凸包沿順時針方向進行。

你不能明確地嘗試每一個可能的角度。但是，你可以做一個掃描線。但是，給定一個角度後，可以在旋轉多邊形之後計算頂點，左側，底部和右側點以及頂部，左側，底部和右側的第一個點，以便在繼續旋轉多邊形。所以你可以得到一系列的角度，你當前選擇的頂部，左側，底部和右側是正確的;更進一步，你知道下一個正確的選擇top，left，bottom和right是。對於頂部，左側，底部和右側的每一個合法選擇，您都必須計算固定a和b在某個範圍內的a * sin（theta）+ b * cos（theta）的最大值THETA。回想一下，a * sin（theta）+ b * cos（theta）= sqrt（a^2 + b^2）cos（theta-arctan（b/a））。你評估函數在你的時間間隔的邊界以及衍生物爲零的地方（在arctan（b/a）加上任何整數倍pi），你是黃金。