折れ線の自己交差

N点のXY座標を順に繋いだ折れ線が、自己交差してるかどうかを調べたい。

要は「多角形の自己交差判定」の「始点と終点を結ぶ線が無いバージョン」なので、参考になるかと思い多角形の自己交差で調べてみたが、「辺を全て別々の線分と見なした上で、全線分対の交差判定」というものしか見つからなかった。（探し方が下手なだけ）

それでもいいんだけど、やっぱり全ての線分は2つずつ繋がっているということを利用すれば、計算量減らせるんじゃ無いかという思いもある。

全線分対の交差判定は、Bentley-Ottmannのアルゴリズムがある。

• Bentley–Ottmann algorithm
  • 平面上にn本の線分があったとき、全ての交点を発見するアルゴリズム
  • 愚直にやると組み合わせの総当たりで$O(n^2)$のところ、$O((n+k)\log{n})$でできる。kは交点数
  • いくつかの前提をおく必要がある
    • 全ての2つの線分の端点と交点は異なるx座標にある
      • 端点で交わらないし、垂直線は存在しない
    • 3つ以上の線分が1つの点で交差しない
  • bentley-ottmannアルゴリズム - Panda Noir
  • 計算幾何学特論→テーマ5：平面走査法(pdf)

前提を回避する方法はあるが、端点を微少にずらすとか泥臭い実装が必要になる。ただし、「全ての交点を発見する」でなく、「交点の存在有無を発見し、最初に見つかった1点を返す」だけなら、交点と端点、交点同士が同一x座標にあってはいけないという問題は無視できる。

これの応用でできそう？

• イベントリストQを用意
  • Qには“イベント”を登録。イベントは種類とxy座標を持ち、1～2本の線分が紐付けられる
  • 後述の種類に従って折れ線の端点・節点を元に作成後、x座標でソート
• 二分探索木Tを用意
  • Tには“線分”を登録。線分は自身の両端点の座標を持つ
    • y軸に平行な掃引線Lをx座標の小さい方から動かしていき、Lに現在交わる線分を管理するイメージ
  • y座標で順位付けする
  • 初期値は空
• イベントは、以下の4種類。(括弧)内は、イベントに紐付ける線分の数
  1. 始点(1): Sの始点。または垂直線が存在したとき、それに繋がる線分がx座標の増加する方向に続く場合、その始点
  2. 終点(1): Sの終点。または垂直線が存在したとき、それに繋がる線分がx座標の減少する方向に続く場合、その始点
  3. 節点(2): Sの節点。2本の線分が同一の点で繋がる場所
     • 線分の一方または両方が垂直線の場合は該当せず、4.垂直線および1.始点, 2.終点に登録する
     • つながり方によって、更に3通りに分類
     1. 節点が2つとも線分の左端の点（“<“みたいな状態）
     2. 節点が2つとも線分の右端の点（”>“みたいな状態）
     3. 左端と右端が1つずつ（”–“みたいな状態）
  4. 垂直線(1): 困ったちゃん

• Qを順にイテレートし、イベントの種類によって以下の処理を行う
  • イベントに紐付けられた線分をh(またはh1,h2)とする
  1. 始点の場合
     • xy座標を元にTから直上・直下の線分t, rを取得
     • hとt、hとrの交差判定を行う
     • hをTに挿入する
  2. 終点の場合
     • xy座標を元にTから直上・直下の線分t, rを取得
     • tとrの交差判定を行う
     • hをTから削除する
  3. 節点の場合
     1. 節点が2つとも左端の場合
        • xy座標を元にTから直上・直下の線分t, rを取得
        • h1,h2で、より上に位置する方をh1、下に位置する方をh2とする
        • h1とt、h2とrの交差判定
        • h1,h2をTに挿入する
     2. 節点が2つとも右端の場合
        • xy座標を元にTから直上・直下の線分t, rを取得
        • tとrの交差判定
        • h1,h2をTから削除する
     3. 節点が左右1つずつの場合
        • 現在の点が右端点である方の線分をh1、左端点である方の線分をh2とする
          • Tにはh1が存在し、h2が存在していない状態である
        • xy座標を元にTから直上・直下の線分t, rを取得
        • h2とt、h2とrの交差判定
        • Tからh1のノードを見つけ、値をh2に書き換える
  4. 垂直線の場合
     • 端点のy座標を小さい方からy1,y2とする
     • Tから、y1～y2の間に線分が存在するか調べる
  • 交差の有無を判定するだけなので、交差が見つかったら即breakする前提。全ての交点は見つけない

節点や始終点が他の線分上にあった場合にも正しく動作するよう気をつけるべきことはまだ整理できていない。

全ての交点を見つけるBentley–Ottmannアルゴリズムでは、交点というイベントを追加するため、Qは優先付きキューである必要があるが、1点見つかったら終了する今回のアルゴリズムではイベントは追加しないため、初期化時に1回ソートすればよく、リストでよい

二分探索木は、線分を「掃引線Lと各線分の交点のy座標」順に管理する。

今回の処理では、交点が見つかったらbreakする、つまり全ての線分はその時点までは交わっていない。線分の上下の順序は交差したときのみ入れ替わるため、あるx座標における線分の”順序”は、xを動かしても保たれているといえる。

しかし、“値”(y座標)はx座標毎に当然、変化する。挿入したり、ある点の直上直下の線分を探索する場合は、「現在のx座標でのy座標」を基準に参照しなければならない。

また、折れ線なので「同一端点から始まる2本の線分」が存在する。もしこの2本が同時にTに存在するとき（“<“のような形）、上になる方と下になる方の位置関係が正しく挿入されなければならない。それには端点のy座標だけを基準にしては不足で、y座標が同じ場合は傾きの大きさも比較対象にする必要がある。

二分探索時の比較ごとにx座標を与えて演算する必要があるため、固定値で比較する単純な二分探索木と比べて、若干コストが重くなる。

この辺上手くする方法はないかな。