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

Facebookシェア Twitterツイート LINEで送る Googleシェア このエントリーをはてなブックマークに追加
この章を学ぶ前に必要な知識
Up
0
Down

要約

概要

二つの凸包を元に新しい凸包を求めるアルゴリズムについて紹介します.上側の凸包の辺と下側の凸包を求めることがゴールになります.Divide and Conquerアルゴリズム(分割統治法)の手法の途中でも必要となる技術です.
ー 条件 ー
  • 二つの凸包
  • 凸包Aの全ての点が凸包Bの全ての点より左
ー 効果 ー
  • 二つの凸包を統合した新しい凸包を得る
ーポイントー
  • 凸包を結ぶ上側を結ぶ線と、下側を結ぶ線を求めます
  • 初めに凸包Aの最も右の点と凸包Bの最も左の点を結び、上下に点を移動させて新しい凸包の点を探します

解  説

二つの凸包を統合した凸包を求める方法について紹介します. この凸包のアルゴリズムでは、凸包Aと凸包Bが完全に軸上で分離できていて、それぞれの最右点、最左点からスタートして新しい辺を二つ見つけます. この処理はDivide and Conquer(分割統治法) アルゴリズムの中で必要な処理になります.
二つの凸包を統合した凸包を求めたい
新しい凸包を作るアルゴリズム. Upper TangentとLower Tangentを求めます.
凸包を求めるアルゴリズムの詳細について記述します. 凸包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で更新が不要になったら終了します. アルゴリズムが終わると直線が両方の凸包に接している状態になります. これを今度はそれぞれの凸包で逆周りに探していき、下側の辺を見つけます. 上側も下側の辺も見つけることができたら、不要になった間の辺を全て除去します. これで新しい凸包ができました.
新しい凸包を求めるアルゴリズムの詳細
この章を学んで新たに学べる
Comments

Reasons
>>隠す