線分交差ビジュアライザー
線分の交差判定をアニメーションで可視化 — 外積を使った向き判定(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本の線分が交差するかどうかを判定する向き判定(外積)の仕組みをアニメーションで示すツールです。判定の条件は「それぞれの線分の両端が、もう一方の線分を含む直線をまたいでいること」。交差している場合は、正確な交点も計算します。
機能
方向判定テスト
外積による向き判定が線分の交差を判定する様子を確認できます。
計算量
2つの線分: O(1)。n本の線分(スイープライン法): O((n + k) log n)。空間計算量: O(n)。
100%プライベート
すべてブラウザ内で完結し、データはアップロードされません。
例
Input
segments (0,0)-(4,4) and (0,4)-(4,0)Output
intersect: yes, at (2, 2)主な用途
-
1
幾何学とグラフィックス
多角形、地図、または衝突判定における交差する辺を検出します。
-
2
方向判定の数学を学ぶ
符号付き外積がどのように向きと交差を分類するかを確認できます。
-
3
スイープラインの直感的理解
スイープライン法がすべての交点を効率的に見つける仕組みを理解できます。
Zerethonの線分交差ビジュアライザーは、2つの線分が交差するかどうか、そしてどこで交差するかを、方向判定(外積によるテスト)を使ってブラウザ上でアニメーション表示します。2つの線分のテストはO(1)、n本の線分間のすべての交点を検出するにはスイープライン法(Bentley–Ottmannアルゴリズム、k = 交点数)でO((n + k) log n)かかります。空間計算量はO(n)です。
- カテゴリ
- アルゴリズム
- 料金
- 無料
- プライバシー
- ブラウザベース
- 登録
- 不要
参考文献
- Line segment intersection — Wikipedia
- MIT OCW 6.006 — Introduction to Algorithms (CLRS) — MIT OpenCourseWare
プライバシー
明記されない限り、データがブラウザの外に送信されることはありません。線分交差ビジュアライザー は完全にクライアント側で動作します — サーバーへのアップロードなし、ログなし、入力内容のトラッキングなし。
Zerethon Social で作成・共有・成長しよう
無料登録。ポイントを獲得し、実績を集め、世界中のクリエイターとつながりましょう。