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

Question

CH1 と CH2 を 2 つの凸多角形とする。2 つの多角形間の相互関係の考えられるすべての異なるケースで機能することを正当化する、頂点の数に線形の時間でそれらの結合の凸包を計算するアルゴリズムを与えます。

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

Answer 1

回転キャリパーは、このような問題に対する強力なツールです。

この記事のパート 2.6The Convex Hull of Two Convex Polygonsを見てください。

コメントするには:これは非常に単純なアルゴリズムであると確信しています。

• 縦線から始めます。
• 両方の多角形の左端の点を見つけます。その中で一番左のものを選びなさい。ハルに属します。
• この点で線を修正します。
• （両方のポリゴンから）次のポイントに触れるまで、このポイントを中心にラインを回転させます（前方検索のみが必要なため、全体の時間はO（m + n）であることに注意してください）
• この点を船体に追加し、ラインを修正します。
• 繰り返す。

詳細については、記事 (およびその他の rot.cal. の説明) を参照してください。

このアルゴリズムはギフトラッピングに似ていることに注意してください