convexhullとは？初心者向けのやさしい解説共起語・同意語・対義語も併せて解説！

この記事を書いた人

高岡智則

年齢：33歳性別：男性職業：Webディレクター（兼ライティング・SNS運用担当）居住地：東京都杉並区・永福町の1LDKマンション出身地：神奈川県川崎市身長：176cm 体系：細身〜普通（最近ちょっとお腹が気になる）血液型：A型誕生日：1992年11月20日最終学歴：明治大学・情報コミュニケーション学部卒通勤：京王井の頭線で渋谷まで（通勤20分）家族構成：一人暮らし、実家には両親と2歳下の妹恋愛事情：独身。彼女は2年いない（本人は「忙しいだけ」と言い張る）

convexhullとは？

convexhull とは平面上の点の集合を囲む最小の凸多角形のことです凸とは図形の任意の2点を結ぶ直線が図形の内部にすべて入る性質を指しますつまり凸包は与えられた点をすべて含みさらに外周を構成する辺を結ぶときに内角が大きくへこまない多角形です

日常に例えるならいくつかの針金で点を囲んでいくとき谷のようにへこまない滑らかな形が凸包の役割をしますここでの基本は最小という点ですつまり点を囲む境界としてこれ以上小さくすることができない形を指します

convex hull の基本イメージ

点の集合を紙の上に置きその周りをぐるっと回して壁のような境界線を引くとしますすべての点はこの境界線の内側または境界上にありますこの境界線が convex hull です

この概念は座標平面だけでなく三次元の点集合にも同じ考え方があり同様に最小の凸包を求めることができます

よく使われるアルゴリズム

凸包を効率的に求める代表的な方法には グラハムスキャン と ジャービスの法 がありますどちらも点集合を順序付けて外周を順にたどる手法です

グラハムスキャンは最初に基準点を決めその点から見た他の点の角度を順に並べますそして境界をつくる点だけを残していくことで凸包を得ます典型的には O(n log n) の計算量です

ジャービスの法は外周をぐるりと回って次の点を選ぶ作業を繰り返します外側の点を順番に選ぶため ギフトラッピング法 とも呼ばれますこちらは最悪ケースで O(nh) の計算量になることがありますが実装が直感的で理解しやすい特徴があります

実務での注意点

凸包を実データで求めるときは座標の浮動小数点演算による誤差に注意しましょう角度計算や向き判定を行うとき小さな丸め誤差が頂点の順序を崩すことがありますそのため計算結果を検証するための追加チェックを入れると安定します

小さな例と練習

点の集合として (0,0) (2,0) (1,2) (1,1) などを考えると凸包の頂点は (0,0) から (2,0) へそして (1,2) の三点で囲まれる形になりますつまりこの例の凸包は三角形です

アルゴリズム	グラハムスキャンとジャービスの法
特徴	グラハムは高速で計算量が安定している一方ジャービスは実装が簡単

用語のまとめ

頂点 : 凸包の角を作る点

境界 : 凸包を構成する外周の線分

内部 : 凸包の内側にある点はすべて境界より内側に位置します

応用例とイメージ

地図データ上の複数の地点を包む最小の境界を見つけることや画像処理で点の集まりの外周を検出する場面などに convexhull は活躍します直感的には地図の船が外周に沿って進むときの輪郭を決めるようなイメージです

まとめと次の一歩

convexhull の考え方はデータ分析やコンピュータビジョン 3D モデリングさらにはロボットの経路計画など幅広い分野で使われます初心者のうちはまず convexhull の定義をしっかり理解しその後グラハムスキャンやジャービスの法のイメージと手順をつかむことから始めましょう

convexhullの同意語

凸包: 点集合を含む最小の凸集合の境界線。通常はその集合を「囲む」凸形状で、点群を全て含む最小の凸多角形の輪郭を指します。
convex hull: 英語の同義語。点集合を含む最小の凸集合を指す数学用語で、日本語では一般に『凸包』と呼ばれます。
最小凸包: 凸包と同じ意味で、特に『最も小さな凸集合』という性質を強調するときに使われる表現です。
外接凸包: 一部の文献で用いられる表現。点集合を包含する最小の凸集合のことを指します。呼称は文献や分野により異なることがあります。

convexhullの対義語・反対語

凹包絡線（concave hull）: 点集合を包含する最小の凹形の境界。 convex hull の対になる直感的な概念で、点群が凹みを持つ形に沿って外周を囲む形を指します。アルファ形状などを使って実現されることが多いです。
非凸包（non-convex hull）: 凸ではなく凹みを持つ包絡線の総称。含む点集合を囲む境界が凹みを含む場合に使われます。実務・研究の場で convex hull の対義語として用いられることがあります。
アルファ形状（Alpha shape）: パラメータ alpha の大きさに応じて凹みをもつ境界を作れる幾何形。 convex hull より柔軟に点集合の形状を表現でき、凹形の包絡線として用いられます。アルファ値を調整することで凹凸の程度を制御できます。
凹形境界（concave boundary）: 凸ではなく凹んだ境界そのもの。凸包の対語として、凹みを伴う外周を指す比喩的表現や説明として使われることがあります。

convexhullの共起語

凸包: 点集合を囲む最小の凸集合。2D/3Dを問わず、内部の点を含み、外周は凸な形状になる。
convex hull: 英語の用語。日本語では“凸包”と呼ばれ、点集合を囲む最小の凸集合を指す。
点集合: 凸包の入力となる点の集まり。2D なら平面上の点、3D なら点群。
点群: 3次元などの空間に散らばる点の集合。凸包を作る対象になることが多い。
2D: 二次元の凸包を扱う状況を示す識別子。
3D: 三次元の凸包を扱う状況を示す識別子。
凸多角形: 2D の凸包は外周が凸多角形になる。
頂点: 凸包を構成する角の点。 hull vertices。
辺: 凸包の境界を形成する直線分。
面: 3D凸包の境界を構成する平面/三角形の集合。
極点: 凸包の外部へ突出する点。現実には凸包の頂点になることが多い。
最小凸集合: 凸包は元の点集合を含みつつ、最も小さい凸集合。
アルゴリズム: 凸包を計算するための手法群。
グラハムスキャン: Graham scan。2D 凸包を求める代表的アルゴリズム。時間計算量は O(n log n)。
Graham scan: グラハムスキャンの英語表記。2D凸包を求める代表的アルゴリズム。
ジャービス法: Jarvis march。2Dで外周を一周するように次の凸点を選ぶアルゴリズム。
ギフトラッピング法: Gift wrapping method の和訳。ジャービス法の別称として使われることがある。
アンドリュー法: アンドリューの単調連鎖法。2D凸包を効率的に求めるアルゴリズム。
モノトーン連鎖法: Monotone chain algorithm の日本語表記。
クイックハル法: QuickHull。分割統治風の凸包アルゴリズム。
QuickHull: 英語名。平均的には O(n log n) 程度の計算量で凸包を求めるアルゴリズム。
SciPy: Python の SciPy ライブラリ。scipy.spatial.ConvexHull で凸包を計算できる。
scipy.spatial.ConvexHull: SciPy の凸包クラス。2D/3D の凸包を扱える。
CGAL: C++ の計算幾何ライブラリ。凸包を含む多くの幾何計算を実装済み。
Shapely: Python の幾何ライブラリ。convex_hull などの機能を提供。
3D凸包: 3次元空間における凸包。頂点・辺・面から成り、凸多面体になる。
凸集合: 凸性を持つ集合。凸包はこの概念を最小の形で表現したもの。
支援関数: 凸包の境界を特徴づける数学的概念のひとつ。外方向の境界を記述する。
時間計算量: アルゴリズムの実行時間の目安。代表例として O(n log n) が挙げられる。
O(n log n): 凸包の代表的な計算時間のオーダー。データ数 n に対して対数を含む。
境界線: 2D 凸包の外周を構成する境界を指す。

convexhullの関連用語

凸包（Convex Hull）: 点の集合を囲む最小の凸集合。2Dでは凸多角形、3Dでは凸多面体となり、内部の点は他の点の凸結合として表現できる。
極点（エクストリームポイント）: 凸包を構成する点のうち、他の点の凸結合だけでは表せず、必ず現れる点。外周上に現れることが多い。
頂点（Vertex）: 凸包の境界を構成する点。2Dでは凸多角形の頂点、3Dでは凸多面体の頂点。
辺（Edge）: 凸包の境界をつなぐ直線要素。2Dでは辺、3Dではエッジ。
面（Face）: 3D凸包の境界を構成する平面領域。複数の辺で囲まれる面。
2D凸包 / 二次元凸包: 平面上の点集合の凸包。最も基本的なケース。
3D凸包 / 三次元凸包: 空間内の点集合の凸包。
グラハムスキャン / Graham scan: 点を極角順に並べ、凸性を保つように走査して凸包を構築するアルゴリズム。
ジャービス法 / Gift wrapping: 外周の点を順番に選んで周回させ、凸包を構成するアルゴリズム。最悪計算量は O(nh)。
アンドリューのモノトーンチェーン / Andrew's monotone chain: 点を x 座標で並べ、上部と下部を連結して凸包を作るアルゴリズム。時間計算量は O(n log n)。
クイックハル / QuickHull: 外部点を基準に分割して再帰的に凸包を構築するアルゴリズム。平均 O(n log n)、最悪 O(n^2)。
Chan のアルゴリズム: 凸包のサイズ h を使って O(n log h) で求める、理論的に高速なアルゴリズム。
Melkman のアルゴリズム: 平面上の単純なポリラインから凸包をオンラインで構築する手法。
凸層 / Onion decomposition: 点集合を最も外側の凸包から順に剥がして層状に分解する方法。
半空間交法 / Half-space intersection: 凸集合を半空間の交として表現し、交わりから凸包を得る別の計算方法。
Carathéodory の定理: d 次元の凸集合では、任意の点を d+1 点の凸結合で表せるという重要な定理。
Radon の定理: d 次元の点集合は、2つの凸集合の凸結合が交差する点を共有できるという基礎定理。
Convex Hull Trick（凸包トリック）: 動的計画法の最適化テクニックで、直線の最小値を効率的に求める。幾何学的凸包計算とは別物なので混同に注意。