有人可以向我解釋旋轉卡鉗嗎？

Question

我正在努力計算一組點的最小包圍矩形（任意對齊）。

我能夠使用格雷厄姆算法計算凸包。

我卡在哪裏是下一步。我想過使用旋轉卡尺方法，但我似乎無法找到算法的充分解釋。

Answer 1

如果你有凸包，那麼一個簡單的基本算法。您只需穿過凸包的每個邊緣並旋轉您的點，以便邊沿沿着主軸，比如說X軸。然後找到這些點的軸對齊邊界框。選擇邊界框最小的那個。

通過獲取每個維度的最小值和最大值，可以找到軸對齊的邊界框。

如果您按相反的數量旋轉邊界框，現在它將包圍原始點。

爲了使效率更高，請注意，只有可能影響邊界框的點位於凸包上。

爲了使其效果非常好，請注意，在任何一次觸摸邊界框的凸包周圍只有四個點（這不完全正確，但現在忽略）。如果旋轉點剛好足以使下一個邊與邊界框對齊，那麼其中三個點是相同的，其中一個點將用凸包圍的下一個點替換。這可以讓你創建一個算法，該算法在凸包上的點數是線性的。

現在有兩個邊平行或垂直的特殊情況。這會導致在任何時候都有四個以上的點觸摸邊界框，但實際上並不重要。如果您可以選擇下一個要使用的兩個平行邊線中的哪一個，則可以任意選擇一個邊線。