凸包(Convex Hull)ビジュアライザー

平面上の点群に対して、Andrewのmonotone chainアルゴリズムで凸包(convex hull)を構築する様子をアニメーションで可視化 — push/popの過程をステップごとに確認できます。ブラウザ上ですぐ動作します。

無料登録不要クライアントサイドプライバシーに配慮 Updated 6月 11, 2026

速度

疑似コード

Press Run to animate the algorithm.

使い方

1 Runを押すと、散らばった点群から凸包の構築が始まります。
2 monotone chainアルゴリズムが点をpush(追加)し、左折にならない曲がり方をした点をpop(除去)していく様子を確認しましょう。
3 Shuffleで新しいランダムな点群を生成したり、1ステップずつ実行したりできます。
4 緑色の輪郭線が、最終的にできあがった凸包です。

このツールを使う理由

Andrewのmonotone chainアルゴリズムが下部包と上部包を構築する様子を見ることができます。
右折を生む点がなぜ列から取り除かれるのかを理解できます。
O(n log n)の計算量で構築が進む様子を観察できます — コストの大部分はソート処理に集中しています。
すべてブラウザ内で完結します。登録もアップロードも不要です。

よくある質問

凸包とは何ですか?

点の集合をすべて含む最小の凸多角形のことです。すべての点の周りに輪ゴムを張り、それをきつく締め上げた形を思い浮かべるとわかりやすいでしょう。

このツールではどのアルゴリズムを使っていますか?

Andrewのmonotone chainアルゴリズムです。点をソートしたうえで、下部包と上部包を構築し、各点をpush(追加)しながら、左折(反時計回り)にならない曲がり方をする点をpop(除去)していきます。

凸包の計算量はどれくらいですか?

O(n log n)です。これは主に最初のソート処理によって決まる計算量で、チェーン自体の構築は線形時間で行えます。Graham scanやQuickHullも同様の平均的な計算量になります。

凸包は何に使われますか?

衝突判定(collision detection)、形状解析、経路探索(pathfinding)、GIS、そして多くの幾何アルゴリズムの前処理ステップとして利用されます。