凸包(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)いきます。
機能
ステップごとのアニメーション
点がソートされ、曲がり方が判定されながら凸包が構築される様子を確認できます。
計算量
時間計算量: O(n log n)(ソート処理が支配的)。空間計算量: O(n)。
100%プライベート
すべてブラウザ内で実行され、何もアップロードされません。
例
Input
points incl. one interior pointOutput
hull = outer points only; interior point excluded主な用途
-
1
計算幾何学
多くの幾何アルゴリズムで使われる基礎的な凸包を確認できます。
-
2
衝突判定と境界
点群を囲むタイトな凸境界を計算します。
-
3
向き判定の学習
凸包を構築する左折・右折判定を理解します。
Zerethonの凸包(convex hull)ビジュアライザーは、O(n log n)アルゴリズム(Graham scanやAndrew's monotone chainなど — 最初のソート処理が支配的)を用いて、ブラウザ上で一連の点を囲む最小の凸多角形を求める過程をアニメーションで表示します。内部の点は凸包から除外され、必要な空間はO(n)です。
- カテゴリ
- アルゴリズム
- 料金
- 無料
- プライバシー
- ブラウザベース
- 登録
- 不要
参考文献
- 凸包 — Wolfram MathWorld — Wolfram MathWorld
- VisuAlgo — 凸包 — VisuAlgo (NUS)
- 凸包 — ウィキペディア
プライバシー
明記されない限り、データがブラウザの外に送信されることはありません。凸包(Convex Hull)ビジュアライザー は完全にクライアント側で動作します — サーバーへのアップロードなし、ログなし、入力内容のトラッキングなし。
Zerethon Social で作成・共有・成長しよう
無料登録。ポイントを獲得し、実績を集め、世界中のクリエイターとつながりましょう。