線分の交差 ラインスウィープ 平面幾何 マンハッタン幾何

線分交差 | ラインスウィープアルゴリズム

線分交差 | ラインスウィープアルゴリズム
Feb. 2, 2020, 1:52 p.m.

目次

用途

x軸あるいはy軸に平行な線分(それぞれ水平線分、垂直線分)が複数与えられてその交点を求める.

アルゴリズム

  • すべての点に以下の情報を加える

    • 垂直線分の上下(UP, DOWN)、水平線分の左右(LEFT, RIGHT)のどれに属するか type

    • 自身が作る線分の長さ length (水平線分のみで使用)

  • すべての点を以下に基づいてソートする

    • y昇順

    • yが同点の場合はtypeで次の順: DOWN -> LEFT -> UP -> RIGHT

    • typeが同点の場合はx昇順

  • カウンタcounterを0で初期化する
  • 先頭からすべての点について以下を実行する

    • typeがUPの場合) 二分探索木BTにx座標を追加

    • typeがLEFTの場合) x座標とx座標+lengthの範囲に収まるBTに収まる要素数をcounterに加える

    • typeがDOWNの場合) BTからx座標を取り除く

計算量

点のソートに$O(N \log N)$.

その後、setに対する挿入、削除、検索すべてが$O(\log N)$.
それを点の数$N$だけ繰り返す.

$O(N \log N)$

コード

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
enum PointType {
  DOWN, LEFT, UP, RIGHT // The order matters.
};

class Point {
public:
  Vector2 coord;
  PointType type;
  Int length;

  bool operator < (const Point &p) {
    // if y is a tie, use type.
    return (p.coord.y == coord.y && type != p.type)
      ? type < p.type
      : coord < p.coord;
  }

  bool operator == (const Point &p) {
    return coord == p.coord && type == p.type;
  }
};

Int line_sweep() {
  set<Int> BT;
  Int count = 0;
  sort(span_all(points));

  for (auto p: points) {
    switch (p.type) {
      case DOWN:
        BT.insert(p.coord.x);
        break;
      case LEFT:
        count += distance(
          lower_bound(span_all(BT), p.coord.x),
          upper_bound(span_all(BT), p.coord.x + p.length)
        );
        break;
      case UP:
        BT.erase(p.coord.x);
        break;
      case RIGHT:
        // do nothing
        break;
    }
  }
  return count;
}