凸包

convex-hull.png

凸包って何?

衝突判定においては、点群を囲む最小の凸多角形のこと。
凸包を求めるアルゴリズムはたくさんあります。

  1. Andrew's Algorithm….頑強で実装が簡単。2Dでは最強。
  2. Quickhull Algorithm…3Dでもok
  3. 分割統治法を用いた方法
  4. ドロネー三角形分割する過程でも凸包が求まります

などなど

2次元の点群を囲む最小の凸多角形を求める

分割統治法による方法

分割統治法で効率よく解ける問題のうちの一つ。
点群をx座標によって左右に分割することにより、小問題に再帰的に分割し、
それらを解いて得られた隣り合う2つの凸方を併合して1角凸包を生成することを繰り返して、全体の解を得る。
計算量はO(nlogn)
なんか、点群から三角形群を作る話にも似てるな。

Andrew's algorithm

  1. 点群をlexicographicにソートする。左→右順に点を並べる。(上下は関係なし)
  2. upper chainを作成する
    1. x座標で左の点から順番に辿っていき、前の点2つで構成される線に対して、次の点がどちら側に位置しているかどうかみる
  3. lowe chainを作成する
  4. upper&lower chainをつなげて凸包の完成
andrew.png

chainの作成

まず、簡単のためx座標で全く同じ値の座標の点は無いと仮定して説明します。
線に対して点がどっちがわに存在するかどうか判定しながらchainを作ります。
線に対して右側(時計回り)に点が存在していたら、点をaddして
線に対して左側(反時計周り)に点が存在していたら、点をremoveします。

ソースコード

github

参考にした本


bounding-volume quickhull

サポートサイト Wikidot.com bounding-volumequickhull