The   Sutherland-Hodgman clipping algorithm   finds the polygon that is the intersection between an arbitrary polygon (the “subject polygon”) and a convex polygon (the “clip polygon”).

It is used in computer graphics (especially 2D graphics) to reduce the complexity of a scene being displayed by eliminating parts of a polygon that do not need to be displayed.



Task

Take the closed polygon defined by the points:

 



[
(
50
,
150
)
,
(
200
,
50
)
,
(
350
,
150
)
,
(
350
,
300
)
,
(
250
,
300
)
,
(
200
,
250
)
,
(
150
,
350
)
,
(
100
,
250
)
,
(
100
,
200
)
]


{\displaystyle [(50,150),(200,50),(350,150),(350,300),(250,300),(200,250),(150,350),(100,250),(100,200)]}


and clip it by the rectangle defined by the points:

 



[
(
100
,
100
)
,
(
300
,
100
)
,
(
300
,
300
)
,
(
100
,
300
)
]


{\displaystyle [(100,100),(300,100),(300,300),(100,300)]}


Print the sequence of points that define the resulting clipped polygon.



Extra credit

Display all three polygons on a graphical surface, using a different color for each polygon and filling the resulting polygon.

(When displaying you may use either a north-west or a south-west origin, whichever is more convenient for your display mechanism.)




#include <iostream>
 
using namespace std;
 
struct point2D { float x, y; };
 
const int   N = 99; // clipped (new) polygon size
 
// check if a point is on the LEFT side of an edge
bool inside(point2D p, point2D p1, point2D p2)
{
    return (p2.y - p1.y) * p.x + (p1.x - p2.x) * p.y + (p2.x * p1.y - p1.x * p2.y) < 0;
}
 
// calculate intersection point
point2D intersection(point2D cp1, point2D cp2, point2D s, point2D e)
{
    point2D dc = { cp1.x - cp2.x, cp1.y - cp2.y };
    point2D dp = { s.x - e.x, s.y - e.y };
 
    float n1 = cp1.x * cp2.y - cp1.y * cp2.x;
    float n2 = s.x * e.y - s.y * e.x;
    float n3 = 1.0 / (dc.x * dp.y - dc.y * dp.x);
 
    return { (n1 * dp.x - n2 * dc.x) * n3, (n1 * dp.y - n2 * dc.y) * n3 };
}
 
// Sutherland-Hodgman clipping
void SutherlandHodgman(point2D *subjectPolygon, int &subjectPolygonSize, point2D *clipPolygon, int &clipPolygonSize, point2D (&newPolygon)[N], int &newPolygonSize)
{
    point2D cp1, cp2, s, e, inputPolygon[N];
 
    // copy subject polygon to new polygon and set its size
    for(int i = 0; i < subjectPolygonSize; i++)
        newPolygon[i] = subjectPolygon[i];
 
    newPolygonSize = subjectPolygonSize;
 
    for(int j = 0; j < clipPolygonSize; j++)
    {
        // copy new polygon to input polygon & set counter to 0
        for(int k = 0; k < newPolygonSize; k++){ inputPolygon[k] = newPolygon[k]; }
        int counter = 0;
 
        // get clipping polygon edge
        cp1 = clipPolygon[j];
        cp2 = clipPolygon[(j + 1) % clipPolygonSize];
 
        for(int i = 0; i < newPolygonSize; i++)
        {
            // get subject polygon edge
            s = inputPolygon[i];
            e = inputPolygon[(i + 1) % newPolygonSize];
 
            // Case 1: Both vertices are inside:
            // Only the second vertex is added to the output list
            if(inside(s, cp1, cp2) && inside(e, cp1, cp2))
                newPolygon[counter++] = e;
 
            // Case 2: First vertex is outside while second one is inside:
            // Both the point of intersection of the edge with the clip boundary
            // and the second vertex are added to the output list
            else if(!inside(s, cp1, cp2) && inside(e, cp1, cp2))
            {
                newPolygon[counter++] = intersection(cp1, cp2, s, e);
                newPolygon[counter++] = e;
            }
 
            // Case 3: First vertex is inside while second one is outside:
            // Only the point of intersection of the edge with the clip boundary
            // is added to the output list
            else if(inside(s, cp1, cp2) && !inside(e, cp1, cp2))
                newPolygon[counter++] = intersection(cp1, cp2, s, e);
 
            // Case 4: Both vertices are outside
            else if(!inside(s, cp1, cp2) && !inside(e, cp1, cp2))
            {
                // No vertices are added to the output list
            }
        }
        // set new polygon size
        newPolygonSize = counter;
    }
}
 
int main(int argc, char** argv)
{
    // subject polygon
    point2D subjectPolygon[] = {
	{50,150}, {200,50}, {350,150},
        {350,300},{250,300},{200,250},
        {150,350},{100,250},{100,200}
    };
    int subjectPolygonSize = sizeof(subjectPolygon) / sizeof(subjectPolygon[0]);
 
    // clipping polygon
    point2D clipPolygon[] = { {100,100}, {300,100}, {300,300}, {100,300} };
    int clipPolygonSize = sizeof(clipPolygon) / sizeof(clipPolygon[0]);
 
    // define the new clipped polygon (empty)
    int newPolygonSize = 0;
    point2D newPolygon[N] = { 0 };
 
    // apply clipping
    SutherlandHodgman(subjectPolygon, subjectPolygonSize, clipPolygon, clipPolygonSize, newPolygon, newPolygonSize);
 
    // print clipped polygon points
    cout << "Clipped polygon points:" << endl;
    for(int i = 0; i < newPolygonSize; i++)
        cout << "(" << newPolygon[i].x << ", " << newPolygon[i].y << ")" << endl;
 
    return 0;
}
 