/*
    Read

        http://z0b.kapsi.fi/snippets.php

    before using this code. Thank you.
*/

// A generic polygon splitter. This works with 3D polygons, but it can be modified to work
// in 2D if you change the plane to a line (and supports the required methods).

// 'math::vec3' is just a generic 3D vertex type, substitute you own; it needs normal add,
// subtract and assignment operators, plus dot and cross product member functions.
// Can split texture coordinates, etc. too if your vertex class supports them.

class polygon {
public:
    std::vector<math::vec3> vertex;

    ...

    bool split(const math::plane &p, polygon &front, polygon &back) const;
}

bool polygon::split(const math::plane &p, polygon &front, polygon &back) const
{
    if (vertex.size() < 3)
        return false;

    // split epsilon, for countering floating-point inaccuracies
    static constexpr float EPSILON = 0.001f;

    // splits an edge origin->dir by plane p (or line l if you want)
    auto splitter = [] (const math::vec3 &origin, const math::vec3 &dir, const math::plane &p)
    {
        return origin + (dir * -(p.distance(origin) / p.normal.dot(dir)));
    };

    std::vector<math::vec3> &fv = front.vertex,
                            &bv = back.vertex;

    fv.clear();
    bv.clear();

    math::vec3 vtxA = vertex[vertex.size() - 1];
    float sideA = l.distance(vtxA);

    for (size_t i = 0, j = vertex.size(); i < j; i++) {
        math::vec3 vtxB = vertex[i];
        float sideB = l.distance(vtxB);

        if (sideB > EPSILON) {
            if (sideA < -EPSILON) {
                // split the edge
                const math::vec3 v = splitter(vtxA, vtxB - vtxA, l);

                fv.push_back(v);
                bv.push_back(v);
            }

            fv.push_back(vtxB);
        } else if (sideB < -EPSILON) {
            if (sideA > EPSILON) {
                // split the edge
                const math::vec3 v = splitter(vtxA, vtxB - vtxA, l);

                fv.push_back(v);
                bv.push_back(v);
            }

            bv.push_back(vtxB);
        } else {
            // the point sits on the plane, so put it in both halves
            fv.push_back(vtxB);
            bv.push_back(vtxB);
        }

        vtxA = vtxB;
        sideA = sideB;
    }

    return true;
}