線分凸包の計算 2005・計算幾何学 本谷 凸包 与えられた図形を含む最小の凸図 （輪ゴムで囲む） 凸包の計算 • 応用１：ロボット・衝突判定 凸包の計算 • 応用２：「最も離れた２点」の探索 • 答えは凸包に寄与する点のどれか 凸包の計算 • 応用３：分類 凸包の計算法 • • • • • 包装法 Grahamの走査法 逐次構成法 分割統治法 その他 包装法 1. • y座標最小の点を見つけて p0 と呼ぶ． 複数あったらx座標が最小のもの 2. ① ② ③ ④ ⑤ i=0としたあと，①から⑤を実行 点piを原点として他点を見込む角を計算 角度最小の点pjを求める． pi – pjを凸包の辺に登録 j=0なら終了 i=jとして①に戻る 包装法 １： ｙ座標最小の点を原点に，ｘ軸となす角 が最小の点を探す．見付かった点を凸包の 一点に追加． 包装法 ２：見付かった点
