二つの凸包を統合した凸包を求めたい

二つの凸包を統合した凸包を求める方法について紹介します. この凸包のアルゴリズムでは、凸包Aと凸包Bが完全に軸上で分離できていて、それぞれの最右点、最左点からスタートして新しい辺を二つ見つけます. この処理はDivide and Conquer(分割統治法) アルゴリズムの中で必要な処理になります.

凸包を求めるアルゴリズムの詳細について記述します. 凸包Aは左側、凸包Bは右側にあるものとして、凸包Aの全ての点は凸包Bの全ての点の左側にあるものとします. 1. 凸包Aの最も右の点と凸包Bの最も左の点を結びます. 【まずは、上側の辺(Upper Tangent)を求めます. 初めに凸包Bの点を上にずらすことを考えます.】 2. 「今結んでいる直線が凸包Bを貫通しているか」または「凸包Bの時計回りで次の点が直線の左にきているか」を確認します. 3. もし貫通しているまたは左にきているであれば、結んでいる線のB側を次の点に移動します. 4. これの凸包B側の更新を「凸包Bを貫通しない」または「次の点が線の右側」に来るまで繰り返します. 5. 4.で凸包B側の点の更新が終わったら、次は凸包A側の点を更新していきます.これも更新が不要になるまで繰り返します.(点を見る順番が反時計回り、線の右側に来ていないかを確認するように反転するので要注意) 6. 上記の2-5で更新が不要になったら終了します. アルゴリズムが終わると直線が両方の凸包に接している状態になります. これを今度はそれぞれの凸包で逆周りに探していき、下側の辺を見つけます. 上側も下側の辺も見つけることができたら、不要になった間の辺を全て除去します. これで新しい凸包ができました.