/* Polygon Clipping Algorithm
 * ==========================
 * (c) 2003 Robert Andersson <robert on profundis. se>
 */

#include <list>


// A simple vertex class for demonstration purposes
template<typename T>
class Vertex2d
{
public:
    Vertex2d(T p_x, T p_y) : x(p_x), y(p_y) {}
    T x, y;
};


// A simple polygon class for demonstration purposes
template<typename T>
class Polygon : public std::list<Vertex2d<T> >
{
};


// Sub-function used by the main function
template<typename T>
Polygon<T>::iterator PolygonClipByRegion(int region, Polygon<T> &vertices, Polygon<T>::iterator vertex, T clip);


/* Parameters:
 *  T(ype)
 *      Must/should be a floating point type, or some weird fixed point
 *      type that overloads the * and / operators.
 *  vertices
 *      A polygon class or a simple list of vertices. Must contains
 *      at least 3 vertices. Will be modified.
 *  min_x, min_y, max_x, max_y
 *      The clip rectangle. Note that vertices may be equal to max_x
 *      or max_y, not necessarily lesser.
 */
template<typename T>
void PolygonClip(Polygon<T> &vertices, T min_x, T min_y, T max_x, T max_y)
{
    // We want at least 3 vertices
    if(vertices.size() < 3) return;

    // We make the vertex list cyclic so we can generalize tests
    vertices.push_front(vertices.back());
    vertices.push_back(*(++vertices.begin()));

    // Process each real vertex. That is, skip the temporary inserted at front and back
    for(Polygon<T>::iterator vertex = ++vertices.begin(); vertex != --vertices.end(); ) {

        // vertex is our current vertex, and will always point to the vertex after
        // those that has been processed and are verified to be inside the clip rectangle.

        // Test the vertex against each side of the clip rectangle, and if it is outside
        // any, we call the PolygonClipByRegion() on that vertex
             if(vertex->y < min_y) vertex = PolygonClipByRegion<T>(1, vertices, vertex, min_y);
        else if(vertex->y > max_y) vertex = PolygonClipByRegion<T>(2, vertices, vertex, max_y);
        else if(vertex->x < min_x) vertex = PolygonClipByRegion<T>(3, vertices, vertex, min_x);
        else if(vertex->x > max_x) vertex = PolygonClipByRegion<T>(4, vertices, vertex, max_x);
        else {
            // We have "fallen through" all tests and can move on to the next vertex
            vertex++;
        }
    }

    // Remove the temporary inserted vertices
    vertices.pop_front();
    vertices.pop_back();
}


// This function generalize the clipping process for all clip regions. This is 
// unoptimized as there is lots of conditionals. An optimized version of this
// algorithm should implement a specific version for each clip region.
template<typename T>
Polygon<T>::iterator PolygonClipByRegion(int region, Polygon<T> &vertices, Polygon<T>::iterator vertex, T clip)
{
    // Initialize iterators to our neighbors
    Polygon<T>::iterator vertex_prev;
    Polygon<T>::iterator vertex_next;
    (vertex_prev = vertex)--;
    (vertex_next = vertex)++;

    // Find out if our neighbors are inside or outside
    bool is_prev_outside;
    bool is_next_outside;
    switch(region) {
    case 1: is_prev_outside = vertex_prev->y <= clip; is_next_outside = vertex_next->y <= clip; break;
    case 2: is_prev_outside = vertex_prev->y >= clip; is_next_outside = vertex_next->y >= clip; break;
    case 3: is_prev_outside = vertex_prev->x <= clip; is_next_outside = vertex_next->x <= clip; break;
    case 4: is_prev_outside = vertex_prev->x >= clip; is_next_outside = vertex_next->x >= clip; break;
    }

    // If both neighbors are outside, we can sefely remove this vertex
    if(is_prev_outside && is_next_outside) {
        vertex = vertices.erase(vertex);
    }
    else {

        // Here we split the vertex into two equal ones. There is room for
        // optimization by checking before hand if either is going to be removed
        // anyway. We only really need to split if both are inside the clip region.
        vertex = vertices.insert(vertex, *vertex);

        // We test each sub-vertex against the neighbors, and remove or retrace them.
        for(int i = 0; i < 2; i++) {
            if(i ? is_next_outside : is_prev_outside)
                vertex = vertices.erase(vertex);
            else {
                Polygon<T>::iterator sub_next = i ? vertex_next : vertex_prev;
                if(region == 1 || region == 2) {
                    vertex->x += (clip - vertex->y) * ((sub_next->x - vertex->x) / (sub_next->y - vertex->y));
                    vertex->y = clip;
                }
                else if(region == 3 || region == 4) {
                    vertex->y += (clip - vertex->x) * ((sub_next->y - vertex->y) / (sub_next->x - vertex->x));
                    vertex->x = clip;
                }
                vertex++;
            }
        }

        // This makes sure the current vertex really is the current, regardless of what happened above
        (vertex = vertex_prev)++;
    }

    // Keep the cyclic list consistent. Necessary, if first "real" element has been changed
    if(vertex == ++vertices.begin()) {
        vertices.back().x = vertex->x;
        vertices.back().y = vertex->y;
    }

    // Return the current vertex
    return vertex;
}


int main(void)
{
    Polygon<float> poly;
    poly.push_back(Vertex2d<float>(6.0f, 1.0f));
    poly.push_back(Vertex2d<float>(9.0f, 4.0f));
    poly.push_back(Vertex2d<float>(1.0f, 6.0f));
    poly.push_back(Vertex2d<float>(2.0f, 4.0f));

    PolygonClip<float>(poly, 3.0f, 2.0f, 8.0f, 5.0f);

    // 0: 4.67,2.00 
    // 1: 7.00,2.00
    // 2: 8.00,3.00
    // 3: 8.00,4.25
    // 4: 5.00,5.00
    // 5: 3.00,5.00
    // 6: 3.00,3.25

    return 0;
}