多角形の摂動変形

説明

反時計回りの多角形の各辺を len だけ右に平行移動した多角形を作る．位相的破綻に弱いアルゴリズムの補強用に用いると便利．

計算量

O(n)．

使い方

P は反時計回りにしておく．このとき len は右方向のずらし量になる．ずらしすぎると摂動変形自体が位相的に破綻するので len は十分小さく取ること．

ソースコード

polygon shrink_polygon(const polygon &P, number len) {
  polygon res;
  for (int i = 0; i < P.size(); ++i) {
    point a = prev(P,i), b = curr(P,i), c = next(P,i);
    point u = (b - a) / abs(b - a);
    double th = arg((c - b)/ u) * 0.5;
    res.push_back( b + u * point(-sin(th), cos(th)) * len / cos(th) );
  }
  return res;
}

Verified

• PKU 2678 (Mothy), 1843MS, 384KB