Sutherland-Hodgeman Polygon Clipping Algorithm

Sutherland-Hodgeman Polygon Clipping Algorithm: This algorithm was purposed by Sutherland and Hodgeman in 1974 to determine which portions of the polygon were visible within a window and clipping out the portions that are outside the window.

This algorithm accepts as input a series of polygon vertices, V₁, V₂, …. V_n. These vertices define polygon edges from V_i, to V_i+1 and from V_n to V₁.

The algorithm clips a polygon by processing the polygon boundary as a whole against each window edge. It means all the vertices are processed for clipping against each individual clip boundary of clipping window one by one.

It means starting with the initial set of vertices, the polygon is first clipped against left window boundary and a new set of vertices is produced.

This set is given as input to next clipping boundary and the polygon is clipped against right clipping boundary to produce a new set of vertices and is then clipped against bottom and top clipping boundary to produce final set of vertices . [Left-Right-Bottom-Top]

Thus, at each step a new set of output vertices is generated and is passed to the next window boundary clipper.

When all the vertices of a given polygon are processed against any clipping side, there could be any one of the following four possibilities for a successive pair of two vertices of polygon:

Case 1: out → in :

If the starting vertex is outside the window boundary and ending vertex is inside then we preserve or save both point of intersection of polygon edge with window boundary and ending vertex in the output vertex list.

Case 2 : in → in :

If both the starting and ending vertices are inside the window boundary then only the ending vertex is preserved or saved in output vertex list.

Case 3: in → out :

If the starting vertex is inside the window and ending vertex is outside then only the point of intersection of polygon edge with window boundary is saved in output list.

Case 4: out → out :

If both the starting and ending vertices are outside the window boundary then nothing is added or saved in the output vertex list.

Case	Output
Out → In	A’ B [2 Vertices, Point of intersect with window and ending edge]
In → In	C [1 ending vertex ]
In → Out	D’ [Point of intersect with window]
Out → Out	N/A [Nothing is included]

Example of Sutherland-Hodgeman Polygon Clipping Algorithm

Let us consider a polygon with vertices P1, P2, P3, P4, P5. Inside in a viewing window. Applying Sutherland-Hodgeman Polygon Clipping Algorithm on this polygon, we get:

Clipping polygon engaged left window boundary:

Here the input vertex list is P1, P2, P3, P4 P5 and the edges are P1P2, P2P3, P3P4, P4P5 and P5P1. Now, consider all the edge with respect to (w.r.t.) left window boundary.

Edge	Type	Output
P1P2	Out → In	P1’P2
P2P3	In → In	P3
P3P4	In → In	P4
P4P5	In → In	P5
P5P1	In → Out	P5′

Clipping polygon engaged right window boundary:

Here the input vertex list is P1′, P2, P3, P4, P5, P5′ and the edges are P1’P2, P2P3, P3P4, P4P5, P5P5′ and P5’P1′. Now, consider all the edge with respect to (w.r.t.) right window boundary. There will be no changes because all edges lies inside the right clipping window.

Edge	Type	Output
P1’P2	In → In	‘P2
P2P3	In → In	P3
P3P4	In → In	P4
P4P5	In → In	P5
P5P5′	In → In	P5′
P5’P1′	In → In	P1′

Clipping polygon engaged bottom window boundary:

Here the input vertex list is P1′, P2, P3, P4, P5, P5′ and the edges are P1’P2, P2P3, P3P4, P4P5 and P5P5′. Now, consider all the edge with respect to (w.r.t.) bottom window boundary.

Edge	Type	Output
P1’P2	In → In	P2
P2P3	In → In	P3
P3P4	In → In	P4
P4P5	In → Out	P4′
P5P5′	Out → Out	N/A
P5’P1′	Out → In	P5”

Clipping polygon engaged top window boundary:

Here the input vertex list is P1′, P2, P3, P4, P4′, P5” and the edges are P1’P2, P2P3, P3P4, P4P4′, P4’P5” and P5”P1. Now, consider all the edge with respect to (w.r.t.) top window boundary. Here the input vertex list is P1′, P2, P3, P4, P5, P5′ and the edges are P1’P2, P2P3, P3P4, P4P5, P5P5′ and P5’P1′. Now, consider all the edge with respect to (w.r.t.) right window boundary. There will be no changes because all edges lies inside the top clipping window.

Edge	Type	Output
P1’P2	In → In	P2
P2P3	In → In	P3
P3P4	In → In	P4
P4P4′	In → In	P4′
P4’P5”	In → In	P5”
P5”P1′	In → In	P1′

Final output using Sutherland-Hodgeman Polygon Clipping Algorithm will be:

Limitations of Sutherland-Hodgeman Polygon Clipping Algorithm

In some concave polygons, the theorem creates extra edges while clipping.