/* 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;
}