ei1333's page

凸包

説明

凸包を Andrew's Monotone Chain によって求める。

アルゴリズムの概要は以下の通り。

1. 点を x 座標の昇順でソートする。 x が同じ場合は y 座標の昇順で比較する。
2. 上側凸包を求める。
• 凸包の点をスタックで管理することとし, x 座標の昇順にスタックに点を $1$ つずつ追加していく。点を含めると凸でなくなる場合(点の進行方向 ccw を用いて判定) は凸になるまでスタックから点を取り除く。
3. 下側凸包を求める。

計算量

$O(N \log N)$

実装例

Polygon Convex_Hull(Polygon& p){
  int n = p.size(), k = 0;
  if(n >= 3){
    sort(p.begin(), p.end());
    vector< Point > ch(2 * n);
    for(int i = 0; i < n; ch[k++] = p[i++]){
      while(k >= 2 && cross(ch[k - 1] - ch[k - 2], p[i] - ch[k - 1]) < 0) --k;
    }
    for(int i = n - 2, t = k + 1; i >= 0; ch[k++] = p[i--]){
      while(k >= t && cross(ch[k - 1] - ch[k - 2], p[i] - ch[k - 1]) < 0) --k;
    }
    ch.resize(k - 1);
    return ch;
  } else {
    return p;
  }
}