可視グラフ

説明

注目頂点のリストと障害物のリストが与えられたとき，次のグラフを作成する．

• 注目頂点をグラフの頂点として持ち，
• 二頂点を結ぶ線分が障害物に遮られないときに辺を張る．

このように，見える頂点対に辺を張ったグラフのことを可視グラフという．二次元平面上の二点間最短経路は，可視グラフ上の最短経路と一致する．

計算量

O(n^3)．

TODO

• 嘘 Sweepline を実装？

ソースコード

#define curr(P, i) P[i]
#define next(P, i) P[(i+1)%P.size()]
bool block_off(const point &a, const point &b, const polygon &obj) {
  point m = (a+b)/2.0;
  bool on = false, in = false;
  for (int j = 0; j < obj.size(); ++j) {
    point c = curr(obj,j), d = next(obj,j);
    if (imag(d) < imag(c)) swap(c, d);
    if (cross(a-c,b-c) * cross(a-d,b-d) < 0 &&    // strictly intersect.
        cross(c-a,d-a) * cross(c-b,d-b) < 0) return true;
    if (cross(a-c,b-c) == 0 && dot(a-c,b-c) < 0) return true;
    if (imag(c) <= imag(m) && imag(m) < imag(d))  // strictly contain.
      if (cross(c-m,d-m) < 0) in = !in;
    if (cross(c-m,d-m) == 0 && dot(c-m,d-m) <= 0) on = true;
  }
  return !on && in;
}
graph visibility_graph(const vector<point> &pt,
    const vector<polygon> &objs) {
  graph g(pt.size());
  for (int i = 0; i < pt.size(); ++i) {
    for (int j = i+1; j < pt.size(); ++j) {
      for (int k = 0; k < objs.size(); ++k)
        if (block_off(pt[i], pt[j], objs[k])) goto SKIP;
      g[i].push_back( edge(i, j, abs(pt[i]-pt[j])) );
      g[j].push_back( edge(j, i, abs(pt[i]-pt[j])) );
SKIP:;
    }
  }
  return g;
}

Verified

• PKU 2678 (Mothy), 265 MS, 356 KB