平面走査法を使った 一般線分の 交点列挙アルゴリズム

Presentation on theme: "平面走査法を使った 一般線分の 交点列挙アルゴリズム"— Presentation transcript:

1 平面走査法を使った 一般線分の 交点列挙アルゴリズム
プログラミングIII 磯 直行

2 平面走査法による 一般線分集合の 交点列挙 計算機にとっては大変時間のかかる処理 単純法なら O(n2) ↓ 効率の良い アルゴリズムだと
１ ２ ３ ５ ７ ６ ４ ０ x y 平面走査法による 一般線分集合の 交点列挙 計算機にとっては大変時間のかかる処理 単純法なら O(n2) ↓ 効率の良い アルゴリズムだと O(n log n) 高速！

3 高速に実行するための基礎知識 データ構造「ヒープ」 2分木の親子方向（y軸方向）に大小関係を 保持したデータ構造 データ構造「2分探索木」
2分木の横方向（ｘ軸方向）に大小関係を 小 形状に関する条件： 高さー１までは完全2分木 葉は左寄せ 大 形状に関する条件：なし 小 大

4 Point1 走査線 （スイープライン） ↓ 「ヒープ」を利用 走査線を移動させ y座標の小さい順に 図面を走査 走査線の 次の停止位置は
候補の中でもっとも y座標の小さいもの ↓ たくさんの候補の中から 走査線が次に停止する y座標をすぐに答えることの できる データ構造 「ヒープ」を利用 高速！ １ ２ ３ ５ ７ ６ ４ ０ x y 交差発見！ 交差発見！ 交差発見！

5 Point2 交差の探索 ↓ 「２分探索木」を利用 走査線が停止するごとに 走査線と交差する多くの 線分から交差するものを
y Point2 交差の探索 走査線が停止するごとに 走査線と交差する多くの 線分から交差するものを 高速に調査する必要あり ↓ x軸方向に高速探索ができる データ構造 「２分探索木」を利用 高速！ ７ ６ ５ 走査線と交差する 線分の位置関係を保持 ４ ３ ２ １ x ０ １ ２ ３ ４ ５ ６ ７

6 効率の良い 一般線分の交差列挙アルゴリズム
線分の端点をy座標をキーとしてヒープHに挿入 2分探索木Tを空にする While Hが空でない do Hから最小要素pを取り出す pが線分ｌ の下端点ならば，l をTに挿入する．Tにおいてl と隣接する2本の 線分との間に交点があれば，それらを報告する．交点を新しい線分の下端点としてHに挿入する c． pが線分l の上端点ならば，ｌ をTから削除する．l の削除によってはじめて 隣接する（それまでl の両隣に位置していた）線分の間に交点があれば， それを報告する．交点を新しい線分の下端点としてHに挿入する． 用意するデータ構造 ヒープ　H （必要な操作：「データの挿入」と「最小データの探索･削除」） 2分探索木 T （必要な操作：「データの挿入」と「削除」，および「隣接データの探索」）

7 l4 l1 l2 l3 交点列挙アルゴリズム実行例 y 探索のための準備 １．線分の端点をy座標をキーとして ヒープ H に挿入する．
２．2分探索木 T を空にする． (6,7) ７ (3,6) ６ ヒープ H （次に走査線が停止するy座標を保持） ５ どの順でも良いので，Hへ挿入 例えば，各線分の下端点，上端点の順で挿入 l4 (1,4) ４ 「空」でスタート l1 ３ (5,3) l2 ２ l3 (7,2) (1,2) ２分探索木 T （走査線上の線分のx座標を保持） １ (3,1) (4,1) 「空」でスタート x ０ １ ２ ３ ４ ５ ６ ７

8 l4 l1 l2 l3 交点列挙アルゴリズム実行例 y 探索のための準備 １．線分の端点をy座標をキーとして ヒープ H に挿入する．
２．2分探索木 T を空にする． (6,7) ７ (3,6) ６ ヒープ H （次に走査線が停止するy座標を保持） ５ どの順でも良いので，Hへ挿入 例えば，各線分の下端点，上端点の順で挿入 l4 (1,4) l1の下端点（１，２）を追加 ４ l1 ２ （l1下） 完了！ ３ (5,3) l2 ２ l3 (7,2) (1,2) ２分探索木 T （走査線上の線分のx座標を保持） １ (3,1) (4,1) 「空」のまま x ０ １ ２ ３ ４ ５ ６ ７

9 l4 l1 l2 l3 交点列挙アルゴリズム実行例 y 探索のための準備 １．線分の端点をy座標をキーとして ヒープ H に挿入する．
２．2分探索木 T を空にする． (6,7) ７ (3,6) ６ ヒープ H （次に走査線が停止するy座標を保持） ５ どの順でも良いので，Hへ挿入 例えば，各線分の下端点，上端点の順で挿入 l4 (1,4) l1の上端点（6，7）を追加 ４ l1 ２ （l1下） 完了！ ７ （l1上） ３ (5,3) l2 ２ l3 (7,2) (1,2) ２分探索木 T （走査線上の線分のx座標を保持） １ (3,1) (4,1) 「空」のまま x ０ １ ２ ３ ４ ５ ６ ７

10 l4 l1 l2 l3 交点列挙アルゴリズム実行例 y 探索のための準備 １．線分の端点をy座標をキーとして ヒープ H に挿入する．
２．2分探索木 T を空にする． (6,7) ７ (3,6) ６ ヒープ H （次に走査線が停止するy座標を保持） ５ どの順でも良いので，Hへ挿入 例えば，各線分の下端点，上端点の順で挿入 l4 (1,4) l2の下端点（４，１）を追加 ４ l1 ２ （l1下） ７ （l1上） １ （l２下） ３ 大小（上下）関係不整合 →親子で要素を交換 (5,3) l2 ２ l3 (7,2) (1,2) ２分探索木 T （走査線上の線分のx座標を保持） １ (3,1) (4,1) 「空」のまま x ０ １ ２ ３ ４ ５ ６ ７

11 l4 l1 l2 l3 交点列挙アルゴリズム実行例 y 探索のための準備 １．線分の端点をy座標をキーとして ヒープ H に挿入する．
２．2分探索木 T を空にする． (6,7) ７ (3,6) ６ ヒープ H （次に走査線が停止するy座標を保持） ５ どの順でも良いので，Hへ挿入 例えば，各線分の下端点，上端点の順で挿入 l4 (1,4) l2の下端点（４，１）を追加 ４ l1 １ （l２下） 完了！ ７ （l1上） ２ （l1下） ３ (5,3) l2 ２ l3 (7,2) (1,2) ２分探索木 T （走査線上の線分のx座標を保持） １ (3,1) (4,1) 「空」のまま x ０ １ ２ ３ ４ ５ ６ ７

12 l4 l1 l2 l3 交点列挙アルゴリズム実行例 y 探索のための準備 １．線分の端点をy座標をキーとして ヒープ H に挿入する．
２．2分探索木 T を空にする． (6,7) ７ (3,6) ６ ヒープ H （次に走査線が停止するy座標を保持） ５ どの順でも良いので，Hへ挿入 例えば，各線分の下端点，上端点の順で挿入 l4 (1,4) l2の上端点（１，４）を追加 ４ l1 １ （l２下） ７ （l1上） ２ （l1下） ３ ４ （l2上） (5,3) l2 大小（上下）関係不整合 →親子で要素を交換 （場合によっては，さらに上方向へ交換することもある） ２ l3 (7,2) (1,2) ２分探索木 T （走査線上の線分のx座標を保持） １ (3,1) (4,1) 「空」のまま x ０ １ ２ ３ ４ ５ ６ ７

13 l4 l1 l2 l3 交点列挙アルゴリズム実行例 y 探索のための準備 １．線分の端点をy座標をキーとして ヒープ H に挿入する．
２．2分探索木 T を空にする． (6,7) ７ (3,6) ６ ヒープ H （次に走査線が停止するy座標を保持） ５ どの順でも良いので，Hへ挿入 例えば，各線分の下端点，上端点の順で挿入 l4 (1,4) l2の上端点（１，４）を追加 ４ l1 １ （l２下） 完了！ ４ （l2上） ２ （l1下） ３ ７ （l1上） (5,3) （場合によっては，さらに上方向へ交換することもある） l2 ２ l3 (7,2) (1,2) ２分探索木 T （走査線上の線分のx座標を保持） １ (3,1) (4,1) 「空」のまま x ０ １ ２ ３ ４ ５ ６ ７

14 l4 l1 l2 l3 交点列挙アルゴリズム実行例 y 探索のための準備 １．線分の端点をy座標をキーとして ヒープ H に挿入する．
２．2分探索木 T を空にする． (6,7) ７ (3,6) ６ ヒープ H （次に走査線が停止するy座標を保持） ５ どの順でも良いので，Hへ挿入 例えば，各線分の下端点，上端点の順で挿入 l4 (1,4) l3の下端点（３，１）を追加 ４ l1 １ （l２下） ７ （l1上） ２ （l1下） ３ ４ （l2上） １ （l３下） (5,3) l2 大小（上下）関係不整合 →親子で要素を交換 ２ l3 (7,2) (1,2) ２分探索木 T （走査線上の線分のx座標を保持） １ (3,1) (4,1) 「空」のまま x ０ １ ２ ３ ４ ５ ６ ７

15 l4 l1 l2 l3 交点列挙アルゴリズム実行例 y 探索のための準備 １．線分の端点をy座標をキーとして ヒープ H に挿入する．
２．2分探索木 T を空にする． (6,7) ７ (3,6) ６ ヒープ H （次に走査線が停止するy座標を保持） ５ どの順でも良いので，Hへ挿入 例えば，各線分の下端点，上端点の順で挿入 l4 (1,4) l3の下端点（３，１）を追加 ４ l1 １ （l２下） 完了！ １ （l3下） ２ （l1下） ３ ４ （l２上） ７ （l1上） (5,3) l2 ２ l3 (7,2) (1,2) ２分探索木 T （走査線上の線分のx座標を保持） １ (3,1) (4,1) 「空」のまま x ０ １ ２ ３ ４ ５ ６ ７

16 l4 l1 l2 l3 交点列挙アルゴリズム実行例 y 探索のための準備 １．線分の端点をy座標をキーとして ヒープ H に挿入する．
２．2分探索木 T を空にする． (6,7) ７ (3,6) ６ ヒープ H （次に走査線が停止するy座標を保持） ５ どの順でも良いので，Hへ挿入 例えば，各線分の下端点，上端点の順で挿入 l4 (1,4) l3の上端点（５，３）を追加 ４ l1 １ （l２下） 完了！ １ （l3下） ２ （l1下） ３ ４ （l2上） ７ （l1上） ３ （l３上） (5,3) l2 ２ l3 (7,2) (1,2) ２分探索木 T （走査線上の線分のx座標を保持） １ (3,1) (4,1) 「空」のまま x ０ １ ２ ３ ４ ５ ６ ７

17 l4 l1 l2 l3 交点列挙アルゴリズム実行例 y 探索のための準備 １．線分の端点をy座標をキーとして ヒープ H に挿入する．
２．2分探索木 T を空にする． (6,7) ７ (3,6) ６ ヒープ H （次に走査線が停止するy座標を保持） ５ どの順でも良いので，Hへ挿入 例えば，各線分の下端点，上端点の順で挿入 l4 (1,4) l4の下端点（７，２）を追加 ４ l1 １ （l２下） 完了！ １ （l3下） ２ （l1下） ３ ４ （l2上） ７ （l1上） ３ （l３上） ２ （l４下） (5,3) l2 ２ l3 (7,2) (1,2) ２分探索木 T （走査線上の線分のx座標を保持） １ (3,1) (4,1) 「空」のまま x ０ １ ２ ３ ４ ５ ６ ７

18 l4 l1 l2 l3 交点列挙アルゴリズム実行例 y 探索のための準備 １．線分の端点をy座標をキーとして ヒープ H に挿入する．
２．2分探索木 T を空にする． (6,7) ７ (3,6) ６ ヒープ H （次に走査線が停止するy座標を保持） ５ どの順でも良いので，Hへ挿入 例えば，各線分の下端点，上端点の順で挿入 l4 (1,4) l4の上端点（３，６）を追加 ４ l1 根(root)は最小値→ １ （l２下） 完了！ １ （l3下） ２ （l1下） ３ ４ （l2上） ７ （l1上） ３ （l３上） ２ （l４下） (5,3) ヒープ完成！ l2 ６ （l4上） ２ l3 データの最小値は根(root)に保存される （次に走査線を停止させる座標値がわかる） (7,2) (1,2) ２分探索木 T （走査線上の線分のx座標を保持） １ (3,1) (4,1) 「空」のまま x ０ １ ２ ３ ４ ５ ６ ７

19 l4 l1 l2 l3 交点列挙アルゴリズム実行例 y 走査線を移動させ，探索実行 While Hが空でない do 下端点，上端点，交点に
場合わけして交点探索処理 (6,7) ７ (3,6) ６ ヒープ H （次に走査線が停止するy座標を保持） ５ 走査線の停止位置は y=1とわかったので ヒープの根を削除してヒープを再構成 l4 (1,4) １ （l２下） ４ l1 最後の要素を 強制的に根へ １ （l3下） ２ （l1下） ３ ４ （l2上） ７ （l1上） ３ （l３上） ２ （l４下） (5,3) l2 ６ （l4上） ２ l3 (7,2) (1,2) ２分探索木 T （走査線上の線分のx座標を保持） 走査線 １ (3,1) (4,1) 「空」のまま x ０ １ ２ ３ ４ ５ ６ ７

20 l4 l1 l2 l3 交点列挙アルゴリズム実行例 y 走査線を移動させ，探索実行 While Hが空でない do 下端点，上端点，交点に
場合わけして交点探索処理 (6,7) ７ (3,6) ６ ヒープ H （次に走査線が停止するy座標を保持） ５ 走査線の停止位置は y=1とわかったので ヒープの根を削除してヒープを再構成 l4 (1,4) 大小（上下）関係不整合 →子の小さい方と交換 ４ l1 ６ （l４上） （場合によっては， さらに下方向へ交換することもある） １ （l3下） ２ （l1下） ３ ４ （l2上） ７ （l1上） ３ （l３上） ２ （l４下） (5,3) l2 ２ l3 (7,2) (1,2) ２分探索木 T （走査線上の線分のx座標を保持） 走査線 １ (3,1) (4,1) 「空」のまま x ０ １ ２ ３ ４ ５ ６ ７

21 l4 l1 l2 l3 交点列挙アルゴリズム実行例 y 走査線を移動させ，探索実行 While Hが空でない do 下端点，上端点，交点に
場合わけして交点探索処理 (6,7) ７ (3,6) ６ ヒープ H （次に走査線が停止するy座標を保持） ５ 走査線の停止位置は y=1とわかったので ヒープの根を削除してヒープを再構成 l4 (1,4) 大小（上下）関係不整合 →子の小さい方と交換 ４ l1 １ （l３下） （場合によっては， さらに下方向へ交換することもある） ６ （l４上） ２ （l1下） ３ ４ （l2上） ７ （l1上） ３ （l３上） ２ （l４下） (5,3) l2 ２ l3 (7,2) (1,2) ２分探索木 T （走査線上の線分のx座標を保持） 走査線 １ (3,1) (4,1) 「空」のまま x ０ １ ２ ３ ４ ５ ６ ７

22 l4 l1 l2 l3 交点列挙アルゴリズム実行例 y 走査線を移動させ，探索実行 While Hが空でない do 下端点，上端点，交点に
場合わけして交点探索処理 (6,7) ７ (3,6) ６ ヒープ H （次に走査線が停止するy座標を保持） ５ 走査線の停止位置は y=1とわかったので ヒープの根を削除してヒープを再構成 l4 (1,4) ４ l1 １ （l３下） ４ （l２上） ２ （l1下） ３ ６ （l４上） ７ （l1上） ３ （l３上） ２ （l４下） (5,3) l2 ヒープ再構成完了！ ２ l3 （場合によっては，さらに下方向へ交換することもある） (7,2) (1,2) ２分探索木 T （走査線上の線分のx座標を保持） 走査線 １ (3,1) (4,1) 「空」のまま x ０ １ ２ ３ ４ ５ ６ ７

23 l4 l1 l2 l3 交点列挙アルゴリズム実行例 y 走査線を移動させ，探索実行 While Hが空でない do 下端点，上端点，交点に
場合わけして交点探索処理 (6,7) ７ (3,6) ６ ヒープ H （次に走査線が停止するy座標を保持） ５ 走査線の停止位置は y=1とわかったので ヒープの根を削除してヒープを再構成 l4 (1,4) ４ l1 １ （l３下） ４ （l２上） ２ （l1下） ３ ６ （l４上） ７ （l1上） ３ （l３上） ２ （l４下） (5,3) l2 ヒープ再構成完了！ ２ l3 （場合によっては，さらに下方向へ交換することもある） (7,2) (1,2) ２分探索木 T （走査線上の線分のx座標を保持） 走査線 １ (3,1) (4,1) l2を追加 l2 完了！ x ０ １ ２ ３ ４ ５ ６ ７ 両隣の線分と交差の可能性あり →チェック→交点をヒープに追加

24 l4 l1 l2 l3 交点列挙アルゴリズム実行例 y 走査線を移動させ，探索実行 While Hが空でない do 下端点，上端点，交点に
場合わけして交点探索処理 (6,7) ７ (3,6) ６ ヒープ H （次に走査線が停止するy座標を保持） ５ 走査線の停止位置は y=1とわかったので ヒープの根を削除してヒープを再構成 l4 (1,4) １ （l３下） ４ l1 ４ （l２上） ２ （l1下） ３ ６ （l４上） ７ （l1上） ３ （l３上） ２ （l４下） (5,3) 最後の要素を 強制的に根へ l2 ２ l3 (7,2) (1,2) ２分探索木 T （走査線上の線分のx座標を保持） 走査線 １ (3,1) (4,1) l2を追加 l2 x ０ １ ２ ３ ４ ５ ６ ７

25 l4 l1 l2 l3 交点列挙アルゴリズム実行例 y 走査線を移動させ，探索実行 While Hが空でない do 下端点，上端点，交点に
場合わけして交点探索処理 (6,7) ７ (3,6) ６ ヒープ H （次に走査線が停止するy座標を保持） ５ 走査線の停止位置は y=1とわかったので ヒープの根を削除してヒープを再構成 l4 (1,4) ４ l1 ２ （l4下） ４ （l２上） ２ （l1下） ３ ６ （l４上） ７ （l1上） ３ （l３上） (5,3) l2 ヒープ再構成完了！ ２ l3 （場合によっては，さらに下方向へ交換することもある） (7,2) (1,2) ２分探索木 T （走査線上の線分のx座標を保持） 走査線 １ (3,1) (4,1) l2を追加 l2 x ０ １ ２ ３ ４ ５ ６ ７

26 l4 l1 l2 l3 交点列挙アルゴリズム実行例 y 走査線を移動させ，探索実行 While Hが空でない do 下端点，上端点，交点に
場合わけして交点探索処理 (6,7) ７ (3,6) ６ ヒープ H （次に走査線が停止するy座標を保持） ５ 交点が発見された場合はヒープに追加 l4 (1,4) ４ 交点のy座標を追加 l1 ２ （l4下） 1.5 （l2とl3） ４ （l２上） ２ （l1下） ３ ６ （l４上） ７ （l1上） ３ （l３上） (5,3) l2 ２ l3 (7,2) (1,2) ２分探索木 T （走査線上の線分のx座標を保持） 走査線 １ (3,1) (4,1) l3を追加 l2 完了！ l3 x ０ １ ２ ３ ４ ５ ６ ７ 両隣の線分と交差の可能性あり →チェック→交点をヒープに追加

27 l4 l1 l2 l3 交点列挙アルゴリズム実行例 y 走査線を移動させ，探索実行 While Hが空でない do 下端点，上端点，交点に
場合わけして交点探索処理 (6,7) ７ (3,6) ６ ヒープ H （次に走査線が停止するy座標を保持） ５ 交点が発見された場合はヒープに追加 l4 (1,4) 大小（上下）関係不整合 →親と交換 ４ l1 ２ （l4下） ４ （l２上） ２ （l1下） ３ ６ （l４上） ７ （l1上） ３ （l３上） 1.5 （l2とl3） (5,3) （場合によっては， さらに上方向へ交換することもある） l2 ２ l3 (7,2) (1,2) ２分探索木 T （走査線上の線分のx座標を保持） 走査線 １ (3,1) (4,1) l2 完了！ l3 x ０ １ ２ ３ ４ ５ ６ ７

28 l4 l1 l2 l3 交点列挙アルゴリズム実行例 y 走査線を移動させ，探索実行 While Hが空でない do 下端点，上端点，交点に
場合わけして交点探索処理 (6,7) ７ (3,6) ６ ヒープ H （次に走査線が停止するy座標を保持） ５ 交点が発見された場合はヒープに追加 l4 (1,4) さらに大小（上下）関係不整合 →さらに親と交換 ４ l1 ２ （l4下） ４ （l２上） 1.5 （l2とl3） ３ ６ （l４上） ７ （l1上） ３ （l３上） ２ （l1下） (5,3) （場合によっては，さらに上方向へ交換することもある） l2 ２ l3 (7,2) (1,2) ２分探索木 T （走査線上の線分のx座標を保持） 走査線 １ (3,1) (4,1) l2 完了！ l3 x ０ １ ２ ３ ４ ５ ６ ７

29 l4 l1 l2 l3 交点列挙アルゴリズム実行例 y 走査線を移動させ，探索実行 While Hが空でない do 下端点，上端点，交点に
場合わけして交点探索処理 (6,7) ７ (3,6) ６ ヒープ H （次に走査線が停止するy座標を保持） ５ 交点が発見された場合はヒープに追加 l4 (1,4) ４ l1 1.5 （l2とl3） ４ （l２上） ２ （l4下） ３ ６ （l４上） ７ （l1上） ３ （l３上） ２ （l1下） (5,3) l2 ヒープ再構成完了！ ２ l3 （場合によっては，さらに下方向へ交換することもある） (7,2) (1,2) ２分探索木 T （走査線上の線分のx座標を保持） 走査線 １ (3,1) (4,1) l2 完了！ l3 x ０ １ ２ ３ ４ ５ ６ ７

30 l4 l1 l2 l3 交点列挙アルゴリズム実行例 y 走査線を移動させ，探索実行 While Hが空でない do 下端点，上端点，交点に
場合わけして交点探索処理 (6,7) ７ (3,6) ６ ヒープ H （次に走査線が停止するy座標を保持） ５ 走査線の停止位置は y=1.5とわかったので ヒープの根を削除してヒープを再構成 l4 (1,4) 1.5 （l2とl3） ４ l1 ４ （l２上） ２ （l4下） ３ ６ （l４上） ７ （l1上） ３ （l３上） ２ （l1下） (5,3) 最後の要素を 強制的に根へ l2 ２ l3 走査線 (7,2) (1,2) ２分探索木 T （走査線上の線分のx座標を保持） １ (3,1) (4,1) l2 完了！ l3 x ０ １ ２ ３ ４ ５ ６ ７

31 l4 l1 l2 l3 交点列挙アルゴリズム実行例 y 走査線を移動させ，探索実行 While Hが空でない do 下端点，上端点，交点に
場合わけして交点探索処理 (6,7) ７ (3,6) ６ ヒープ H （次に走査線が停止するy座標を保持） ５ 走査線の停止位置は y=1.5とわかったので ヒープの根を削除してヒープを再構成 l4 (1,4) ４ l1 ２ （l１下） ４ （l２上） ２ （l4下） ３ ６ （l４上） ７ （l1上） ３ （l３上） (5,3) l2 ヒープ再構成完了！ ２ l3 （場合によっては，下方向へ交換することもある） 走査線 (7,2) (1,2) ２分探索木 T （走査線上の線分のx座標を保持） １ (3,1) (4,1) l2 完了！ l3 x 交点で線分の左右関係を入替 →隣接線分との交差チェック ０ １ ２ ３ ４ ５ ６ ７

32 l4 l1 l2 l3 交点列挙アルゴリズム実行例 y 走査線を移動させ，探索実行 While Hが空でない do 下端点，上端点，交点に
場合わけして交点探索処理 (6,7) ７ (3,6) ６ ヒープ H （次に走査線が停止するy座標を保持） ５ 走査線の停止位置は y=1.5とわかったので ヒープの根を削除してヒープを再構成 l4 (1,4) ４ l1 ２ （l１下） ４ （l２上） ２ （l4下） ３ ６ （l４上） ７ （l1上） ３ （l３上） (5,3) l2 ヒープ再構成完了！ ２ l3 （場合によっては，下方向へ交換することもある） 走査線 (7,2) (1,2) ２分探索木 T （走査線上の線分のx座標を保持） １ (3,1) (4,1) l2 完了！ l3 x 交点で線分の左右関係を入替 →隣接線分との交差チェック ０ １ ２ ３ ４ ５ ６ ７

33 l4 l1 l2 l3 交点列挙アルゴリズム実行例 y 走査線を移動させ，探索実行 While Hが空でない do 下端点，上端点，交点に
場合わけして交点探索処理 (6,7) ７ (3,6) ６ ヒープ H （次に走査線が停止するy座標を保持） ５ 走査線の停止位置は y=2とわかったので ヒープの根を削除してヒープを再構成 l4 (1,4) ２ （l1下） ４ 最後の要素を 強制的に根へ l1 ４ （l２上） ２ （l4下） ３ ６ （l４上） ７ （l1上） ３ （l３上） (5,3) 走査線 l2 ２ l3 (7,2) (1,2) ２分探索木 T （走査線上の線分のx座標を保持） １ (3,1) (4,1) l2 l3 x ０ １ ２ ３ ４ ５ ６ ７

34 l4 l1 l2 l3 交点列挙アルゴリズム実行例 y 走査線を移動させ，探索実行 While Hが空でない do 下端点，上端点，交点に
場合わけして交点探索処理 (6,7) ７ (3,6) ６ ヒープ H （次に走査線が停止するy座標を保持） ５ 走査線の停止位置は y=2とわかったので ヒープの根を削除してヒープを再構成 l4 (1,4) 大小（上下）関係不整合 →子の小さい方と交換 ４ l1 ３ （l3下） （場合によっては， さらに下方向へ交換することもある） ４ （l２上） ２ （l4下） ３ ６ （l４上） ７ （l1上） (5,3) 走査線 l2 ２ l3 (7,2) (1,2) ２分探索木 T （走査線上の線分のx座標を保持） １ (3,1) (4,1) l2 l3 x ０ １ ２ ３ ４ ５ ６ ７

35 l4 l1 l2 l3 交点列挙アルゴリズム実行例 y 走査線を移動させ，探索実行 While Hが空でない do 下端点，上端点，交点に
場合わけして交点探索処理 (6,7) ７ (3,6) ６ ヒープ H （次に走査線が停止するy座標を保持） ５ 走査線の停止位置は y=2とわかったので ヒープの根を削除してヒープを再構成 l4 (1,4) ４ l1 ２ （l4下） ４ （l２上） ３ （l3下） ３ ６ （l４上） ７ （l1上） (5,3) 走査線 l2 ヒープ再構成完了！ ２ l3 （場合によっては，下方向へ交換することもある） (7,2) (1,2) ２分探索木 T （走査線上の線分のx座標を保持） １ (3,1) (4,1) l2 l3 x ０ １ ２ ３ ４ ５ ６ ７

36 l4 l1 l2 l3 交点列挙アルゴリズム実行例 y 走査線を移動させ，探索実行 While Hが空でない do 下端点，上端点，交点に
場合わけして交点探索処理 (6,7) ７ (3,6) ６ ヒープ H （次に走査線が停止するy座標を保持） ５ 走査線の停止位置は y=2とわかったので ヒープの根を削除してヒープを再構成 l4 (1,4) ４ 交点のy座標を追加 l1 ２ （l4下） ３ （l１とl２） ４ （l２上） ３ （l3下） ３ ６ （l４上） ７ （l1上） (5,3) 走査線 l2 ２ l3 (7,2) (1,2) ２分探索木 T （走査線上の線分のx座標を保持） １ (3,1) (4,1) l1を追加 l2 l1 l3 x ０ １ ２ ３ ４ ５ ６ ７ 両隣の線分と交差の可能性あり →チェック→交点をヒープに追加

37 l4 l1 l2 l3 交点列挙アルゴリズム実行例 y 走査線を移動させ，探索実行 While Hが空でない do 下端点，上端点，交点に
場合わけして交点探索処理 (6,7) ７ (3,6) ６ ヒープ H （次に走査線が停止するy座標を保持） ５ 走査線の停止位置は y=2とわかったので ヒープの根を削除してヒープを再構成 l4 (1,4) ４ 交点のy座標を追加 l1 ２ （l4下） ４ （l２上） ３ （l3下） ３ ６ （l４上） ７ （l1上） ３ （l１とl２） (5,3) 走査線 l2 ヒープ再構成完了！ ２ l3 （場合によっては，下方向へ交換することもある） (7,2) (1,2) ２分探索木 T （走査線上の線分のx座標を保持） １ (3,1) (4,1) l2 l1 l3 x ０ １ ２ ３ ４ ５ ６ ７

38 l4 l1 l2 l3 交点列挙アルゴリズム実行例 y 走査線を移動させ，探索実行 While Hが空でない do 下端点，上端点，交点に
場合わけして交点探索処理 (6,7) ７ (3,6) ６ ヒープ H （次に走査線が停止するy座標を保持） ５ 走査線の停止位置は y=2とわかったので ヒープの根を削除してヒープを再構成 l4 (1,4) ２ （l４下） ４ 交点のy座標を追加 最後の要素を 強制的に根へ l1 ４ （l２上） ３ （l3下） ３ ６ （l４上） ７ （l1上） ３ （l１とl２） (5,3) 走査線 l2 ２ l3 (7,2) (1,2) ２分探索木 T （走査線上の線分のx座標を保持） １ (3,1) (4,1) l2 l1 l3 x ０ １ ２ ３ ４ ５ ６ ７

39 l4 l1 l2 l3 交点列挙アルゴリズム実行例 y 走査線を移動させ，探索実行 While Hが空でない do 下端点，上端点，交点に
場合わけして交点探索処理 (6,7) ７ (3,6) ６ ヒープ H （次に走査線が停止するy座標を保持） ５ 走査線の停止位置は y=2とわかったので ヒープの根を削除してヒープを再構成 l4 (1,4) ４ 交点のy座標を追加 l1 ３ （l１とl２） ４ （l２上） ３ （l3下） ３ ６ （l４上） ７ （l1上） (5,3) 走査線 l2 ヒープ再構成完了！ ２ l3 （場合によっては，下方向へ交換することもある） (7,2) (1,2) ２分探索木 T （走査線上の線分のx座標を保持） １ (3,1) (4,1) l2 l1 l3 x ０ １ ２ ３ ４ ５ ６ ７

40 l4 l1 l2 l3 交点列挙アルゴリズム実行例 y 走査線を移動させ，探索実行 While Hが空でない do 下端点，上端点，交点に
場合わけして交点探索処理 (6,7) ７ (3,6) ６ ヒープ H （次に走査線が停止するy座標を保持） ５ 走査線の停止位置は y=2とわかったので ヒープの根を削除してヒープを再構成 l4 (1,4) ４ 交点のy座標を追加 l1 ３ （l１とl２） ４ （l２上） ３ （l3下） ３ ６ （l４上） ７ （l1上） (5,3) 走査線 l2 ヒープ再構成完了！ ２ l3 （場合によっては，下方向へ交換することもある） (7,2) (1,2) ２分探索木 T （走査線上の線分のx座標を保持） １ (3,1) (4,1) l4を追加 l2 l1 l3 x l４ ０ １ ２ ３ ４ ５ ６ ７ 交点で線分の左右関係を入替 →隣接線分との交差チェック

41 l4 l1 l2 l3 交点列挙アルゴリズム実行例 y 走査線を移動させ，探索実行 While Hが空でない do 下端点，上端点，交点に
場合わけして交点探索処理 (6,7) ７ (3,6) ６ ヒープ H （次に走査線が停止するy座標を保持） ５ 走査線の停止位置は y=3とわかったので ヒープの根を削除してヒープを再構成 l4 (1,4) ４ 交点のy座標を追加 ３ （l１とl２） l1 ４ （l２上） ３ （l3下） 走査線 ３ 最後の要素を 強制的に根へ ６ （l４上） ７ （l1上） (5,3) l2 ２ l3 (7,2) (1,2) ２分探索木 T （走査線上の線分のx座標を保持） １ (3,1) (4,1) l2 l1 l3 x l４ ０ １ ２ ３ ４ ５ ６ ７

42 l4 l1 l2 l3 交点列挙アルゴリズム実行例 y 走査線を移動させ，探索実行 While Hが空でない do 下端点，上端点，交点に
場合わけして交点探索処理 (6,7) ７ (3,6) ６ ヒープ H （次に走査線が停止するy座標を保持） ５ 走査線の停止位置は y=3とわかったので ヒープの根を削除してヒープを再構成 l4 (1,4) 大小（上下）関係不整合 →子の小さい方と交換 ４ l1 ７ （l1上） （場合によっては， さらに下方向へ交換することもある） ４ （l２上） ３ （l3下） 走査線 ３ ６ （l４上） (5,3) l2 ２ l3 (7,2) (1,2) ２分探索木 T （走査線上の線分のx座標を保持） １ (3,1) (4,1) l2 l1 l3 x l４ ０ １ ２ ３ ４ ５ ６ ７

43 l4 l1 l2 l3 交点列挙アルゴリズム実行例 y 走査線を移動させ，探索実行 While Hが空でない do 下端点，上端点，交点に
場合わけして交点探索処理 (6,7) ７ (3,6) ６ ヒープ H （次に走査線が停止するy座標を保持） ５ 走査線の停止位置は y=3とわかったので ヒープの根を削除してヒープを再構成 l4 (1,4) ４ l1 ３ （l３上） ４ （l２上） ７ （l１下） 走査線 ３ ６ （l４上） (5,3) l2 ヒープ再構成完了！ ２ l3 （場合によっては，下方向へ交換することもある） (7,2) (1,2) ２分探索木 T （走査線上の線分のx座標を保持） １ (3,1) (4,1) l2 l1 l3 x l４ ０ １ ２ ３ ４ ５ ６ ７

44 l4 l1 l2 l3 交点列挙アルゴリズム実行例 y 走査線を移動させ，探索実行 While Hが空でない do 下端点，上端点，交点に
場合わけして交点探索処理 (6,7) ７ (3,6) ６ ヒープ H （次に走査線が停止するy座標を保持） ５ 走査線の停止位置は y=3とわかったので ヒープの根を削除してヒープを再構成 l4 (1,4) ４ l1 ３ （l３上） ４ （l２上） ７ （l１下） 走査線 ３ ６ （l４上） (5,3) l2 ２ l3 (7,2) (1,2) ２分探索木 T （走査線上の線分のx座標を保持） １ (3,1) (4,1) l2 l1 l3 x l４ ０ １ ２ ３ ４ ５ ６ ７ 交点で線分の左右関係を入替 →隣接線分との交差チェック

45 l4 l1 l2 l3 交点列挙アルゴリズム実行例 y 走査線を移動させ，探索実行 While Hが空でない do 下端点，上端点，交点に
場合わけして交点探索処理 (6,7) ７ (3,6) ６ ヒープ H （次に走査線が停止するy座標を保持） ５ 走査線の停止位置は y=3とわかったので ヒープの根を削除してヒープを再構成 l4 (1,4) ４ l1 ３ （l３上） ４ （l２上） ７ （l１下） 走査線 ３ ６ （l４上） (5,3) l2 ２ l3 (7,2) (1,2) ２分探索木 T （走査線上の線分のx座標を保持） １ (3,1) (4,1) l1 完了！ l2 l3 x l４ ０ １ ２ ３ ４ ５ ６ ７

46 l4 l1 l2 l3 交点列挙アルゴリズム実行例 y 走査線を移動させ，探索実行 While Hが空でない do 下端点，上端点，交点に
場合わけして交点探索処理 (6,7) ７ (3,6) ６ ヒープ H （次に走査線が停止するy座標を保持） ５ 走査線の停止位置は y=3とわかったので ヒープの根を削除してヒープを再構成 l4 (1,4) ３ （l３下） ４ l1 ４ （l２上） ７ （l１下） 走査線 ３ 最後の要素を 強制的に根へ ６ （l４上） (5,3) l2 ２ l3 (7,2) (1,2) ２分探索木 T （走査線上の線分のx座標を保持） １ (3,1) (4,1) l1 l2 l3 x l４ ０ １ ２ ３ ４ ５ ６ ７

47 l4 l1 l2 l3 交点列挙アルゴリズム実行例 y 走査線を移動させ，探索実行 While Hが空でない do 下端点，上端点，交点に
場合わけして交点探索処理 (6,7) ７ (3,6) ６ ヒープ H （次に走査線が停止するy座標を保持） ５ 走査線の停止位置は y=3とわかったので ヒープの根を削除してヒープを再構成 l4 (1,4) 大小（上下）関係不整合 →子の小さい方と交換 ４ l1 ６ （l４上） （場合によっては， さらに下方向へ交換することもある） ４ （l２上） ７ （l１下） 走査線 ３ (5,3) l2 ２ l3 (7,2) (1,2) ２分探索木 T （走査線上の線分のx座標を保持） １ (3,1) (4,1) l1 l2 l3 x l４ ０ １ ２ ３ ４ ５ ６ ７

48 l4 l1 l2 l3 交点列挙アルゴリズム実行例 y 走査線を移動させ，探索実行 While Hが空でない do 下端点，上端点，交点に
場合わけして交点探索処理 (6,7) ７ (3,6) ６ ヒープ H （次に走査線が停止するy座標を保持） ５ 走査線の停止位置は y=3とわかったので ヒープの根を削除してヒープを再構成 l4 (1,4) 大小（上下）関係不整合 →子の小さい方と交換 ４ l1 ６ （l４上） （場合によっては， さらに下方向へ交換することもある） ４ （l２上） ７ （l１下） 走査線 ３ (5,3) l2 ２ l3 (7,2) (1,2) ２分探索木 T （走査線上の線分のx座標を保持） １ (3,1) (4,1) l1 l2 l3 x l４ l４ ０ １ ２ ３ ４ ５ ６ ７

49 l4 l1 l2 l3 交点列挙アルゴリズム実行例 y 走査線を移動させ，探索実行 While Hが空でない do 下端点，上端点，交点に
場合わけして交点探索処理 (6,7) ７ (3,6) ６ ヒープ H （次に走査線が停止するy座標を保持） ５ 走査線の停止位置は y=3とわかったので ヒープの根を削除してヒープを再構成 l4 (1,4) ４ l1 ４ （l２上） ６ （l４上） ７ （l１下） 走査線 ３ (5,3) l2 ヒープ再構成完了！ ２ l3 （場合によっては，下方向へ交換することもある） (7,2) (1,2) ２分探索木 T （走査線上の線分のx座標を保持） １ (3,1) (4,1) l1 l2 l3 x l４ ０ １ ２ ３ ４ ５ ６ ７

50 隣接線分の交差チェック→l1とl4の交点をヒープへ追加
交点列挙アルゴリズム実行例 y 走査線を移動させ，探索実行 While Hが空でない do 下端点，上端点，交点に 場合わけして交点探索処理 (6,7) ７ (3,6) ６ ヒープ H （次に走査線が停止するy座標を保持） ５ 走査線の停止位置は y=3とわかったので ヒープの根を削除してヒープを再構成 l4 (1,4) ４ 交点のy座標を追加 l1 ４ （l２上） ５ （l１とl４） ６ （l４上） ７ （l１下） 走査線 ３ (5,3) l2 ２ l3 (7,2) (1,2) ２分探索木 T （走査線上の線分のx座標を保持） １ (3,1) (4,1) l3を削除 l1 × l2 l3 x l４ ０ １ ２ ３ ４ ５ 上端点なのでl3を削除 隣接線分の交差チェック→l1とl4の交点をヒープへ追加 ６ ７

51 隣接線分の交差チェック→l1とl4の交点をヒープへ追加
交点列挙アルゴリズム実行例 y 走査線を移動させ，探索実行 While Hが空でない do 下端点，上端点，交点に 場合わけして交点探索処理 (6,7) ７ (3,6) ６ ヒープ H （次に走査線が停止するy座標を保持） ５ 走査線の停止位置は y=3とわかったので ヒープの根を削除してヒープを再構成 l4 (1,4) ４ l1 ４ （l２上） ６ （l４上） ７ （l１下） 走査線 ３ ５ （l１とl４） 大小（上下）関係不整合 →親と交換 (5,3) l2 ２ l3 (7,2) (1,2) ２分探索木 T （走査線上の線分のx座標を保持） １ (3,1) (4,1) l3を削除 l1 × l2 l3 x l４ ０ １ ２ ３ ４ ５ 上端点なのでl3を削除 隣接線分の交差チェック→l1とl4の交点をヒープへ追加 ６ ７

52 隣接線分の交差チェック→l1とl4の交点をヒープへ追加
交点列挙アルゴリズム実行例 y 走査線を移動させ，探索実行 While Hが空でない do 下端点，上端点，交点に 場合わけして交点探索処理 (6,7) ７ (3,6) ６ ヒープ H （次に走査線が停止するy座標を保持） ５ 走査線の停止位置は y=3とわかったので ヒープの根を削除してヒープを再構成 l4 (1,4) ４ l1 ４ （l２上） ５ （l１とl４） ７ （l１下） 走査線 ３ ６ （l４上） (5,3) l2 ヒープ再構成完了！ ２ l3 （場合によっては，下方向へ交換することもある） (7,2) (1,2) ２分探索木 T （走査線上の線分のx座標を保持） １ (3,1) (4,1) l3を削除 l1 × l2 l3 x l４ ０ １ ２ ３ ４ ５ 上端点なのでl3を削除 隣接線分の交差チェック→l1とl4の交点をヒープへ追加 ６ ７

53 l4 l1 l2 l3 交点列挙アルゴリズム実行例 y 走査線を移動させ，探索実行 While Hが空でない do 下端点，上端点，交点に
場合わけして交点探索処理 (6,7) ７ (3,6) ６ ヒープ H （次に走査線が停止するy座標を保持） ５ 走査線の停止位置は y=3とわかったので ヒープの根を削除してヒープを再構成 l4 (1,4) ４ l1 ４ （l２上） ５ （l１とl４） ７ （l１下） 走査線 ３ ６ （l４上） (5,3) l2 ヒープ再構成完了！ ２ l3 （場合によっては，下方向へ交換することもある） (7,2) (1,2) ２分探索木 T （走査線上の線分のx座標を保持） １ (3,1) (4,1) l1 完了！ l2 l4 x ０ １ ２ ３ ４ ５ ６ ７

54 l4 l1 l2 l3 交点列挙アルゴリズム実行例 y 走査線を移動させ，探索実行 While Hが空でない do 下端点，上端点，交点に
場合わけして交点探索処理 (6,7) ７ (3,6) ６ ヒープ H （次に走査線が停止するy座標を保持） ５ 走査線の停止位置は y=4とわかったので ヒープの根を削除してヒープを再構成 l4 (1,4) 走査線 ４ （l2下） ４ l1 ５ （l１とl４） ７ （l１下） ３ ６ （l４上） 最後の要素を 強制的に根へ (5,3) l2 ２ l3 (7,2) (1,2) ２分探索木 T （走査線上の線分のx座標を保持） １ (3,1) (4,1) l1 l2 l4 x ０ １ ２ ３ ４ ５ ６ ７

55 × l4 l1 l2 l3 交点列挙アルゴリズム実行例 y 走査線を移動させ，探索実行 While Hが空でない do
下端点，上端点，交点に 場合わけして交点探索処理 (6,7) ７ (3,6) ６ ヒープ H （次に走査線が停止するy座標を保持） ５ 走査線の停止位置は y=4とわかったので ヒープの根を削除してヒープを再構成 l4 (1,4) 走査線 ４ l1 ６ （l４上） ５ （l１とl４） ７ （l１下） ３ 大小（上下）関係不整合 →子の小さい方と交換 (5,3) l2 （場合によっては， さらに下方向へ交換することもある） ２ l3 (7,2) (1,2) ２分探索木 T （走査線上の線分のx座標を保持） １ (3,1) (4,1) l2を削除 l1 × l2 l4 x ０ １ ２ ３ ４ ５ ６ 上端点なのでl2を削除 隣接線分の交差があればヒープへ追加 ７

56 × l4 l1 l2 l3 交点列挙アルゴリズム実行例 y 走査線を移動させ，探索実行 While Hが空でない do
下端点，上端点，交点に 場合わけして交点探索処理 (6,7) ７ (3,6) ６ ヒープ H （次に走査線が停止するy座標を保持） ５ 走査線の停止位置は y=4とわかったので ヒープの根を削除してヒープを再構成 l4 (1,4) 走査線 ４ l1 ５ （l１とl４） ６ （l４上） ７ （l１下） ３ (5,3) l2 ヒープ再構成完了！ ２ l3 （場合によっては，下方向へ交換することもある） (7,2) (1,2) ２分探索木 T （走査線上の線分のx座標を保持） １ (3,1) (4,1) l2を削除 l1 × l2 l4 x ０ １ ２ ３ ４ ５ ６ 上端点なのでl2を削除 隣接線分の交差があればヒープへ追加 ７

57 l4 l1 l2 l3 交点列挙アルゴリズム実行例 y 走査線を移動させ，探索実行 While Hが空でない do 下端点，上端点，交点に
場合わけして交点探索処理 (6,7) ７ (3,6) ６ ヒープ H （次に走査線が停止するy座標を保持） 走査線 ５ 走査線の停止位置は y=5とわかったので ヒープの根を削除してヒープを再構成 l4 (1,4) ４ ５ （l１とl４） l1 ６ （l４上） ７ （l１下） ３ 最後の要素を 強制的に根へ (5,3) l2 ２ l3 (7,2) (1,2) ２分探索木 T （走査線上の線分のx座標を保持） １ (3,1) (4,1) l1 l4 x ０ １ ２ ３ ４ ５ ６ ７

58 l4 l1 l2 l3 交点列挙アルゴリズム実行例 y 走査線を移動させ，探索実行 While Hが空でない do 下端点，上端点，交点に
場合わけして交点探索処理 (6,7) ７ (3,6) ６ ヒープ H （次に走査線が停止するy座標を保持） 走査線 ５ 走査線の停止位置は y=5とわかったので ヒープの根を削除してヒープを再構成 l4 (1,4) ４ l1 ７ （l１下） ６ （l４上） ３ 大小（上下）関係不整合 →子の小さい方と交換 (5,3) （場合によっては， さらに下方向へ交換することもある） l2 ２ l3 (7,2) (1,2) ２分探索木 T （走査線上の線分のx座標を保持） １ (3,1) (4,1) l1 l4 x ０ １ ２ ３ ４ ５ ６ ７

59 l4 l1 l2 l3 交点列挙アルゴリズム実行例 y 走査線を移動させ，探索実行 While Hが空でない do 下端点，上端点，交点に
場合わけして交点探索処理 (6,7) ７ (3,6) ６ ヒープ H （次に走査線が停止するy座標を保持） 走査線 ５ 走査線の停止位置は y=5とわかったので ヒープの根を削除してヒープを再構成 l4 (1,4) ４ l1 ６ （l４下） ７ （l１上） ３ (5,3) l2 ヒープ再構成完了！ ２ l3 （場合によっては，下方向へ交換することもある） (7,2) (1,2) ２分探索木 T （走査線上の線分のx座標を保持） １ (3,1) (4,1) l1 l4 x 交点で線分の左右関係を入替 →隣接線分との交差チェック ０ １ ２ ３ ４ ５ ６ ７

60 l4 l1 l2 l3 交点列挙アルゴリズム実行例 y 走査線を移動させ，探索実行 While Hが空でない do 下端点，上端点，交点に
場合わけして交点探索処理 (6,7) ７ (3,6) ６ ヒープ H （次に走査線が停止するy座標を保持） 走査線 ５ 走査線の停止位置は y=5とわかったので ヒープの根を削除してヒープを再構成 l4 (1,4) ４ l1 ６ （l４下） ７ （l１上） ３ (5,3) l2 ヒープ再構成完了！ ２ l3 （場合によっては，下方向へ交換することもある） (7,2) (1,2) ２分探索木 T （走査線上の線分のx座標を保持） １ (3,1) (4,1) l4 完了！ l1 x ０ １ ２ ３ ４ ５ ６ ７

61 l4 l1 l2 l3 交点列挙アルゴリズム実行例 y 走査線を移動させ，探索実行 While Hが空でない do 下端点，上端点，交点に
場合わけして交点探索処理 (6,7) ７ (3,6) 走査線 ６ ヒープ H （次に走査線が停止するy座標を保持） ５ 走査線の停止位置は y=6とわかったので ヒープの根を削除してヒープを再構成 l4 (1,4) ６ （l4下） ４ l1 ７ （l１上） 最後の要素を 強制的に根へ ３ (5,3) l2 ２ l3 (7,2) (1,2) ２分探索木 T （走査線上の線分のx座標を保持） １ (3,1) (4,1) l4 完了！ l1 x ０ １ ２ ３ ４ ５ ６ ７

62 × l4 l1 l2 l3 交点列挙アルゴリズム実行例 y 走査線を移動させ，探索実行 While Hが空でない do
下端点，上端点，交点に 場合わけして交点探索処理 (6,7) ７ (3,6) 走査線 ６ ヒープ H （次に走査線が停止するy座標を保持） ５ 走査線の停止位置は y=6とわかったので ヒープの根を削除してヒープを再構成 l4 (1,4) ４ l1 ７ （l１上） ３ (5,3) l2 ヒープ再構成完了！ ２ l3 （場合によっては，下方向へ交換することもある） (7,2) (1,2) ２分探索木 T （走査線上の線分のx座標を保持） １ × (3,1) (4,1) l4を削除 l4 l1 x ０ １ ２ ３ ４ ５ ６ ７ 上端点なのでl4を削除 隣接線分の交差があればヒープへ追加

63 l4 l1 l2 l3 交点列挙アルゴリズム実行例 y 走査線を移動させ，探索実行 While Hが空でない do 下端点，上端点，交点に
場合わけして交点探索処理 走査線 (6,7) ７ (3,6) ６ ヒープ H （次に走査線が停止するy座標を保持） ５ 走査線の停止位置は y=6とわかったので ヒープの根を削除してヒープを再構成 l4 (1,4) ７ （l１下） ４ l1 ３ (5,3) l2 ヒープ再構成完了！ ２ l3 （場合によっては，下方向へ交換することもある） (7,2) (1,2) ２分探索木 T （走査線上の線分のx座標を保持） １ (3,1) (4,1) l1 完了！ x ０ １ ２ ３ ４ ５ ６ ７

64 × l4 l1 l2 l3 交点列挙アルゴリズム実行例 y 走査線を移動させ，探索実行 While Hが空でない do
下端点，上端点，交点に 場合わけして交点探索処理 走査線 (6,7) ７ (3,6) ６ ヒープ H （次に走査線が停止するy座標を保持） ５ 走査線の停止位置は y=7とわかったので ヒープの根を削除してヒープを再構成 l4 (1,4) ４ l1 ３ ヒープ Hが空になった！ (5,3) l2 ２ l3 (7,2) (1,2) ２分探索木 T （走査線上の線分のx座標を保持） １ × (3,1) (4,1) l1を削除 l1 x ０ １ ２ ３ ４ ５ ６ ７ 上端点なのでl１を削除 隣接線分の交差があればヒープへ追加

65 l4 l1 l2 l3 交点列挙アルゴリズム実行例 アルゴリズム 終了！ y 走査線を移動させ，探索実行 While Hが空でない do
下端点，上端点，交点に 場合わけして交点探索処理 走査線 (6,7) ７ (3,6) ６ ヒープ H （次に走査線が停止するy座標を保持） ５ 走査線の停止位置は y=7とわかったので ヒープの根を削除してヒープを再構成 l4 (1,4) ４ l1 ３ ヒープ Hが空になった！ (5,3) l2 ２ l3 (7,2) (1,2) ２分探索木 T （走査線上の線分のx座標を保持） １ アルゴリズム 終了！ (3,1) (4,1) 2分探索木も空になった！ x ０ １ ２ ３ ４ ５ ６ ７