algorithm - 誰かが回転キャリパーを私に説明できますか？

Question

一連の点の最小の囲み長方形（任意に整列）を計算するのに苦労しています。

グラハムのアルゴリズムを使って凸包を計算することができました。

私が立ち往生しているところは次のステップです。回転キャリパー法を考えましたが、アルゴリズムの説明がうまくいかないようです。

Answer 1

凸包がある場合、基本的なアルゴリズムは簡単です。凸包の各エッジを通過し、ポイントを回転させて、エッジが主軸、たとえばX軸に沿っているようにします。次に、それらの点の軸に沿ったバウンディングボックスを見つけます。最小のバウンディングボックスを選択してください。

軸に沿ったバウンディングボックスは、各次元の最小値と最大値を取得することで見つけることができます。

バウンディングボックスを反対の量だけ回転させると、元のポイントが囲まれるようになります。

これをより効率的にするために、バウンディングボックスに影響を与える可能性のあるポイントは凸包だけであることに注意してください。

本当に効率的にするために、凸包の周りに一度にバウンディングボックスに接触しているポイントは4つしかないことに注意してください（これは厳密には当てはまりませんが、今は無視してください）。次のエッジがバウンディングボックスと揃うようにポイントを回転させると、それらのポイントの3つは同じになり、1つのポイントは凸包の周りの次のポイントに置き換えられます。これにより、凸包上の点の数が線形であるアルゴリズムを作成できます。

ここで、2つのエッジが平行または垂直である特殊なケースがあります。これにより、一度に4つ以上のポイントがバウンディングボックスに接触しますが、実際には問題ではありません。次に使用する2つの平行なエッジのどちらかを選択できる場合は、1つを任意に選択できます。