/* Polygon Clipping Algorithm
 * ==========================
 * (c) 2003 Robert Andersson <robert@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;
}