線分串刺し直線

説明

線分の集合が与えられる．これらをすべて貫く直線の有無を判定する問題を線分串刺し直線問題（Stabbing Line Problem）という．

この問題は，ナイーブには線分の端点を通るような直線について全探索することで O(n^3) では解ける．しかし，双対変換を用いて求める直線をパラメタ表示すれば O(n^2) でも解くことができる．

線分は点の集合なので，「線分と直線が交わる」ことを双対変換すると，「直線の集合に点が含まれる」になる．特に，線分の双対が作る直線の集合は，一点で交わる「くさび形」になる．「すべての線分と交わる直線」は双対変換すると，「すべてのくさび形に含まれる点」になるので，くさび形の共通部分を求めればよい．

図形 X とくさび形 W の共通部分 Y は，W の境界の直線を l,m としたとき，Y = (X を l で切った上側をさらに m で切った下側) ∪ (X を l で切った下側を m で切った上側) と書ける．最初の X として全空間を取れば，凸多角形の切断が凸多角形であることから，各段階で X は単純な凸多角形の集まりになる．そのため，凸多角形の切断を繰り返し適用し，残った領域を調べるだけでよい．

凸多角形の切断を繰り返すことから，精度はあまり出ない．以下の実装では，線分を伸張して一点で交わる状況を排除している．

ToDo

• どこかで Verify．ただし，手元のテストでは，shrink をうまく調節しないと間違えることがあった．よりロバストな凸切断が必要か．

ソースコード

segment shrink(const segment &s) {
  point d = s[1] - s[0]; d /= abs(d); d *= 10;
  return segment(s[0]-eps*d, s[1]+eps*d);
}
bool stabbing_line(const vector<segment> &segs) {
  vector<polygon> regions(1);
  regions[0].push_back( point(-inf,-inf) );
  regions[0].push_back( point(+inf,-inf) );
  regions[0].push_back( point(+inf,+inf) );
  regions[0].push_back( point(-inf,+inf) );
  for (int i = 0; i < segs.size(); ++i) {
    vector<polygon> next;
    segment s = shrink(segs[i]);
    line l = dual(s[0]), m = dual(s[1]);
    line la(l[0], l[1]), lb(l[1], l[0]);
    line ma(m[0], m[1]), mb(m[1], m[0]);
    for (int k = 0; k < regions.size(); ++k) {
      polygon Rab = convex_cut(convex_cut(regions[k], la), mb);
      polygon Rba = convex_cut(convex_cut(regions[k], lb), ma);
      if (Rab.size() > 0) next.push_back( Rab );
      if (Rba.size() > 0) next.push_back( Rba );
    }
    regions.swap( next );
  }
  return regions.size() > 0; // (a,b) \in region -> (a,b)* is stabber
}

Verified