IT用語集 › プログラミング › 凸包
点の集合を包み込む最小の凸図形で、板に打った釘のまわりに輪ゴムを掛けた形を想像するとよい。
代表的なアルゴリズムは、グラハム・スキャン（1972年）、ギフト包装法（ジャーヴィスの行進、1973年）、QuickHull、そして最適な O(n log h) を達成するチャンのアルゴリズムである。2次元では凸包は多角形、3次元では多面体になる。
ゲームや物理演算では、モデルの凸包を衝突形状として使うことが多い。凸同士の判定はGJKで安価かつ頑健に行えるためだ。凹形状のモデルは、先に凸分解で分割しておく。