Home > libalgo > 凸包

凸包

概要

点集合に対して,それを全て覆う最小の凸多角形を凸包といいます.釘打たれた木の板の外側に,外側から輪ゴムをかけたときにできる凸多角形です.

使い方

while の条件式について,同一直線上に 3 点以上存在する場合に ==CW なら全て含め,!=CCW なら両端以外を除きます.

実装

//@require intersection.cc
G andrewScan(G ps) {
    int N = ps.size(), k = 0;
    std::sort(ps.begin(), ps.end());
    G res(N * 2);
    for (int i = 0; i < N; i++) {
        while (k >= 2 && ccw(res[k - 2], res[k - 1], ps[i]) == CW) k--;
        res[k++] = ps[i];
    }
    int t = k + 1;
    for (int i = N - 2; i >= 0; i--) {
        while (k >= t && ccw(res[k - 2], res[k - 1], ps[i]) == CW) k--;
        res[k++] = ps[i];
    }
    res.resize(k - 1);
    return res;
}

参考文献

Spagetti Source