平面走査法

交点列挙問題

平面上の線分の集合を入力してに属すすべての交点の座標を吐きだすようなアルゴリズムを考えます。
一番素朴な方法っていうのはこの個の線分の対を選択して、それらが交点を持ってるのかを調べる方法ですね。
線分対の数は、つまりとなります。

この問題に対するもう一つのアプローチの仕方として平面走査法っていうものがあります。
なんで前の素朴な方法がダメかというと、要するに無駄な処理をたくさんしているからです。

『交点をすべて列挙』は至上命題（この使い方は誤用らしい）なので、少なくとも交点の数の分だけの線分対は調査しないといけません。
逆に言えば、交点が少なければ、絶対に調査が必要な線分対も減るということになります。
『交点はすべて列挙』であっても、交点を持たない『線分対は調査しただけ時間のロス』なのです。

平面走査法（イメージ）

大まかなイメージを図でつかみましょう。

まず図で点線に描かれているようなy軸に垂直な走査直線を置きます。どこに置くかというと線分が存在しないぐらい左の方（言い換えるならx座標が十分に小さい方）に置きます。
そしてこの走査直線を、右の方へ（x座標が大きくなる方へ）ぴょんぴょんと飛ばします。
『飛ばします』ということは着陸する地点があるということで、その着陸地点の事をイベントと言います。

このイベントっていうのは以下のようなところにセッティングされています。
(1)線分の左端。図で言うなら1とか2とか3のところ。
(2)線分の右端。図で言うなら4とか。
(3)線分の交点。図で言うなら5。
（注：例えばAの右端とかも書いてませんがイベントです。）

このイベントの地点において、他に用意したというデータ列を操作してやります。
というのは『今走査直線がクロスしている線分を、その交点が上にある方から（y座標が大きい方から）順に入れたデータ列』です。
分かりにくいので例を出すと、例えば走査直線が3の時点では『BCA』という風にデータ列Aに入れられているということになります。
またというのはこの先に発生するイベントがどこでおこるか（イベントが起こるx座標はどこか）を格納したものになります。
つまりは図で言うところの「1,2,3,4,5」だとか、Aの右端だとかDの左端だとかのx座標が入っているということになります。

平面走査法の具体的なアルゴリズム

じゃあ実際にアルゴリズムを描いてみます。

1)A=φ, B←すべての『端点』のx座標
2)Bから、x座標が最小の点pを取り出す。
if pが線分lの左端 then lをリストAに、y座標順に整列するように挿入する。そしてlとlの前後の線分とが交点を持つか否かを判定し、交点をもてばBにそれを格納する。
else if pが線分lの右端 then lをリストAから取り除く。取り除いた結果、新しくリスト列上で隣り合ったような線分同士があればその交点をしらべ、見つかればBに格納する。
else if pがlとl'の交点 then 交点を出力する。リストAのlとl'の順番を交換する。交換した結果、新しくリスト列上で隣り合ったような線分同士があればその交点をしらべ、見つかればBに格納する。
3)pをBから取り除く。
4)B=φなら終了。Bにイベントがまだあれば2に戻る。

順を追って説明します。
まず1)はそのまま、『まだ走査直線にクロスしている線分はない』ということと、『イベントは線分の両端』ということを言っているだけです。
ちょっと待てと、イベントは『交点も』じゃないのかと思われたかもしれませんが、初めから交点が分かっているならばそもそもこんなアルゴリズムをする必要がないですね。
というわけで今現在知り得る「入力」に関するイベント情報だけを最初に入れておきます。

2)はイベントへのジャンプです。x座標が最小、つまり一番左側にあるイベントから回収していきます。
そしてそのイベントの種類によって処理が分かれるというわけですね。

pがlの左端のとき。今からlとの交差が始まるのでこのlをAの中に格納しないといけませんね。
次がこのアルゴリズムの要です。直線とのクロスが始まった時、その直線の『上もしくは下』（リスト上でいえば前と後ろ）"だけ"を調査して、交点を持っていないか調べます。
この『上もしくは下だけ』が肝。例えばy座標が遠く離れたような線分対は一切調べる必要がなくなり、初めに考えた素朴な方法より調査対象の線分対が少なくなるのです。

pがlの左端のとき。今からlとの交差が終わるのでlはAから排除しなければいけませんね。
電車に座ってて、隣の人が下車したらそのもう一つ隣の人がお隣さんになりますので、新しくできたお隣さんとも交点を持ってないか調査する必要があります。

さて、これら右端および左端のイベントで交点が見つかった時Bにイベントとして交点が格納されます。
この交点のイベントはまず『交点の出力』から始まります。まあこれはいいですね。
次に、『上下の逆転』です。クロスしたということはクロスしている同士の位置関係が変わるということですので逆転の必要がありますね。
図で言うならば、5の前では「DB」という順序ですが、5の後では「BD」になっているはずです。
また、順序を変更すればやっぱりまたお隣さんとの交点探しを始めないといけませんね。

3)はイベントが終わったのでイベントを消すっていう処理です。
4)はイベントが枯渇してたらそれで終了、そうでなければまたイベントジャンプしましょうという処理になります。

javascript plugin Error : このプラグインで利用できない命令または文字列が入っています。