Add Planar Face Extraction

[ssk4988]

Is this a good enough implementation?

[tylerm390]

Nah here is the one I have from SER 20XX: Funhouse

template<class P>
vector<vector<P>> extract_faces(vvi &adj, vector<P> &pts) {
    int n = sz(pts);
    rep(i, 0, n)
        sort(all(adj[i]), [&](int pi, int qi) -> bool {
            P p = pts[pi] - pts[i], q = pts[qi] - pts[i];
            bool sideP = p.y < 0 || (p.y == 0 && p.x < 0);
            bool sideQ = q.y < 0 || (q.y == 0 && q.x < 0);
            if(sideP != sideQ) return sideP;
            return p.cross(q) > 0;
        });

    vii edges;
    rep(i, 0, n) for(int j: adj[i])
        edges.emplace_back(i, j);
    sort(all(edges));

    auto get_idx = [&](int i, int j) -> int {
        return lower_bound(all(edges), pii(i, j)) - begin(edges);
    };

    vector<vector<P>> faces;
    vi used(sz(edges));
    rep(i, 0, n) for(int j: adj[i]) {
        if(used[get_idx(i, j)])
            continue;
        used[get_idx(i, j)] = true;

        vector<P> face = {pts[i]};
        int prv = i, cur = j;
        while(cur != i) {
            face.push_back(pts[cur]);

            auto it = lower_bound(all(adj[cur]), prv, [&](int pi, int qi) -> bool {
                P p = pts[pi] - pts[cur], q = pts[qi] - pts[cur];
                bool sideP = p.y < 0 || (p.y == 0 && p.x < 0);
                bool sideQ = q.y < 0 || (q.y == 0 && q.x < 0);
                if(sideP != sideQ) return sideP;
                return p.cross(q) > 0;
            });

            if(it == begin(adj[cur]))
                it = prev(end(adj[cur]));
            else
                it = prev(it);

            prv = cur;
            cur = *it;
            used[get_idx(prv, cur)] = true;
        }

        faces.push_back(face);
    }

    return faces;
}