Spaghetti Source logo

凸多角形の切断

説明

凸多角形をある直線で切断し,その左側だけ残す.

直線よりも左側にあるものと,交差するときはその交点を出力として吐いている.

何度も切断を繰り返す場合,誤差が積み重なるため,切りそこねが発生することがある.端点を切り落とさないようにあらかじめ多角形を摂動すると対処できるかもしれない.

計算量

ソースコード

// !CAUTION! number は有理数以上
#define curr(P, i) P[i]
#define next(P, i) P[(i+1)%P.size()]
polygon convex_cut(const polygon& P, const line& l) {
  polygon Q;
  for (int i = 0; i < P.size(); ++i) {
    point A = curr(P, i), B = next(P, i);
    if (ccw(l[0], l[1], A) != -1) Q.push_back(A);
    if (ccw(l[0], l[1], A)*ccw(l[0], l[1], B) < 0)
      Q.push_back(crosspoint(line(A, B), l));
  }
  return Q;
}

Verified

前原 貴憲(maehara@prefield.com).

Last Modified: 2007.05.27 11:56:29.