凸包(Convex Hull)ビジュアライザー
平面上の点群に対して、Andrewのmonotone chainアルゴリズムで凸包(convex hull)を構築する様子をアニメーションで可視化 — push/popの過程をステップごとに確認できます。ブラウザ上ですぐ動作します。
疑似コード
Press Run to animate the algorithm.
Time · Space
使い方
- 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、そして多くの幾何アルゴリズムの前処理ステップとして利用されます。
凸包(Convex Hull)ビジュアライザー とは？
凸包ビジュアライザーは、点の集合をすべて含む最小の凸多角形を求める過程を示すツールです。Andrewのmonotone chainアルゴリズムを使用し、点をソートしたうえで下部包(lower hull)と上部包(upper hull)を構築し、左折(left turn)にならない点を取り除いて(pop)いきます。
機能
Step-by-step animation
Watch the hull get built as points are sorted and turns are tested.
Complexity
Time: O(n log n) (sort-dominated). Space: O(n).
100% private
Runs entirely in your browser — nothing is uploaded.
例
Input
points incl. one interior pointOutput
hull = outer points only; interior point excluded主な用途
-
1
Computational geometry
See the foundational hull used by many geometry algorithms.
-
2
Collision & bounds
Compute a tight convex boundary around a point cloud.
-
3
Learn orientation tests
Understand left/right turn tests that build the hull.
Zerethon's convex hull visualizer animates finding the smallest convex polygon that encloses a set of points in your browser, using an O(n log n) algorithm (such as Graham scan or Andrew's monotone chain — dominated by the initial sort). Interior points are excluded from the hull; space is O(n).
- カテゴリ
- アルゴリズム
- 料金
- 無料
- プライバシー
- ブラウザベース
- 登録
- 不要
References
- Convex Hull — Wolfram MathWorld — Wolfram MathWorld
- VisuAlgo — Convex Hull — VisuAlgo (NUS)
- Convex hull — Wikipedia
プライバシー
明記されない限り、データがブラウザの外に送信されることはありません。凸包(Convex Hull)ビジュアライザー は完全にクライアント側で動作します — サーバーへのアップロードなし、ログなし、入力内容のトラッキングなし。
関連ツール
バブルソート ビジュアライザー
バブルソートの動きをアニメーションで確認できるツール。ステップ実行や速度調整、カスタム入力データ、比較・交換回数のリアルタイム表示、擬似コードの表示に対応しています。すべてブラウザ内だけで動作します。
ツールを開く挿入ソート(Insertion Sort)ビジュアライザー
挿入ソートをアニメーションで可視化。ステップ実行や速度調整、カスタム入力、比較回数・書き込み回数のリアルタイム表示、疑似コード(pseudocode)表示に対応。すべてブラウザ内で完結します。
ツールを開く選択ソート(Selection Sort)ビジュアライザー
ステップ実行、速度調整、カスタム入力、比較/交換回数のライブカウンター、擬似コードを備えたSelection Sortのアニメーション。すべてブラウザ内だけで完結します。
ツールを開くマージソート ビジュアライザー
マージソートの動きをアニメーションで再現するツールです。ステップ実行、速度調整、独自のデータ入力、比較・書き込み回数のリアルタイム表示、擬似コード表示に対応。すべてブラウザ上だけで動作します。
ツールを開くZerethon Social で作成・共有・成長しよう
無料登録。ポイントを獲得し、実績を集め、世界中のクリエイターとつながりましょう。