ホーム > libalgo

凸多角形の切断

概要

多角形を直線で切り,新しく出来た2つの多角形を求める.

使い方

左側のみ返している.

実装

//@require intersection.cc
G convex_cut(const G& pol, const L& l) {
    G res;
    int n = pol.size();
    for (int i = 0; i < n; ++i) {
        P A = pol[i], B = pol[(i + 1) % n];
        if (ccw(l[0], l[1], A) != -1) res.push_back(A);
        if (ccw(l[0], l[1], A) * ccw(l[0], l[1], B) < 0) res.push_back(crosspointLL(L(A, B), l));
    }
    return res;
}