線分交差ビジュアライザー
線分の交差判定をアニメーションで可視化 — 外積を使った向き判定(orientation test)と正確な交点の計算を、ステップごとに確認できます。ブラウザだけで動作します。
疑似コード
Press Run to animate the algorithm.
Time · Space
使い方
- 1 Runを押して、2本の線分が交差するかどうかを判定します。
- 2 結果を決める4つの向き判定(外積)の過程を確認します。
- 3 交差していれば交点が緑色でマークされ、交差していなければ線分が赤色に変わります。
- 4 Shuffleを使うと、新しい線分のペアがランダムに生成されます。
このツールを使う理由
- 4つの外積による向き判定が、除算を使わずにどうやって線分の交差を検出するのかを確認できます。
- 「それぞれの線分が、もう一方を含む直線をまたいでいる」という判定ルールを理解できます。
- 2本の線分が交差する際に、正確な交点がどのように計算されるかを確認できます。
- 処理はすべてブラウザ内で完結します。登録もデータのアップロードも不要です。
よくある質問
2本の線分が交差しているかどうかはどうやって判定しますか?
向き判定(外積)を使います。それぞれの線分の両端点が、もう一方の線分を含む直線に対して反対側にある場合、2本の線分は実際に交差しています。
外積による向き判定とは何ですか?
(b−a) × (c−a) の符号によって、点cが a から b への有向直線の左側(正)、右側(負)、あるいは直線上(ゼロ)のどこにあるかが分かります。
計算量はどのくらいですか?
O(1) です — 2本の線分に対して一定回数の算術演算を行うだけです。n本の線分同士の交差を効率的に求める場合は、計算量 O((n+k) log n) のスイープライン(sweep-line)アルゴリズムが使われます。
交点はどのように計算されますか?
2本の直線の方程式を行列式(クラメルの公式)で解くことで求めます。2本の線分が交差していることが分かれば、正確な交点が得られます。
線分交差ビジュアライザー とは？
線分交差ビジュアライザーは、2本の線分が交差するかどうかを判定する向き判定(外積)の仕組みをアニメーションで示すツールです。判定の条件は「それぞれの線分の両端が、もう一方の線分を含む直線をまたいでいること」。交差している場合は、正確な交点も計算します。
機能
Orientation tests
Watch the cross-product turn tests decide whether the segments cross.
Complexity
Two segments: O(1). n segments (sweep-line): O((n + k) log n). Space: O(n).
100% private
Runs entirely in your browser — nothing is uploaded.
例
Input
segments (0,0)-(4,4) and (0,4)-(4,0)Output
intersect: yes, at (2, 2)主な用途
-
1
Geometry & graphics
Detect crossing edges in polygons, maps, or collision checks.
-
2
Learn orientation math
See how signed cross products classify turns and crossings.
-
3
Sweep-line intuition
Understand how the sweep-line finds all intersections efficiently.
Zerethon's line segment intersection visualizer animates whether two segments cross and where, in your browser, using orientation (cross-product) tests. Testing two segments is O(1); detecting all intersections among n segments takes O((n + k) log n) with a sweep-line (Bentley–Ottmann, k = intersections). Space is O(n).
- カテゴリ
- アルゴリズム
- 料金
- 無料
- プライバシー
- ブラウザベース
- 登録
- 不要
References
- Line segment intersection — Wikipedia
- MIT OCW 6.006 — Introduction to Algorithms (CLRS) — MIT OpenCourseWare
プライバシー
明記されない限り、データがブラウザの外に送信されることはありません。線分交差ビジュアライザー は完全にクライアント側で動作します — サーバーへのアップロードなし、ログなし、入力内容のトラッキングなし。
関連ツール
バブルソート ビジュアライザー
バブルソートの動きをアニメーションで確認できるツール。ステップ実行や速度調整、カスタム入力データ、比較・交換回数のリアルタイム表示、擬似コードの表示に対応しています。すべてブラウザ内だけで動作します。
ツールを開く挿入ソート(Insertion Sort)ビジュアライザー
挿入ソートをアニメーションで可視化。ステップ実行や速度調整、カスタム入力、比較回数・書き込み回数のリアルタイム表示、疑似コード(pseudocode)表示に対応。すべてブラウザ内で完結します。
ツールを開く選択ソート(Selection Sort)ビジュアライザー
ステップ実行、速度調整、カスタム入力、比較/交換回数のライブカウンター、擬似コードを備えたSelection Sortのアニメーション。すべてブラウザ内だけで完結します。
ツールを開くマージソート ビジュアライザー
マージソートの動きをアニメーションで再現するツールです。ステップ実行、速度調整、独自のデータ入力、比較・書き込み回数のリアルタイム表示、擬似コード表示に対応。すべてブラウザ上だけで動作します。
ツールを開くZerethon Social で作成・共有・成長しよう
無料登録。ポイントを獲得し、実績を集め、世界中のクリエイターとつながりましょう。