頂点の数を計算するアルゴリズム

Question

CH1とCH2を2つの凸多角形とします。 2つのポリゴン間の相互関係のすべての異なる可能性のあるケースすべてで動作することを正当化するアルゴリズムを、頂点の数と時間的に線形で結合する凸包を計算します。

これを行う方法はありますか？

Answer 1

Rotating calipersは、このような問題の強力な手段です。コメントにthis article

の一部2.6 The Convex Hull of Two Convex Polygonsで

ルック：私は、これは非常に単純なアルゴリズムであると確信しています。

• 縦線で始まります。
• 両方のポリゴンの最も左の点を見つけます。一番左のものを選択してください。それは船体に属します。
• この時点で行を修正します。
• 次の点（両方のポリゴンから）に接触するまで線を回転させます（前方検索のみが必要なので、全体の時間はO（m + n）です）。
• この点を船体に追加し、ライン。
• を繰り返します。

詳しくは、記事（およびその他の説明文）を参照してください。このアルゴリズムはgift wrapping