Sutherland-Hodgman Polygon Clipping Algorithm

Sutherland-Hodgman Algorithm:

Sutherland-Hodgman Algorithm is one such standard method for clipping arbitrarily shaped polygons with a rectangular clipping window. Sutherland-Hodgman clipper actually follows a divide & conquer strategy. It decomposes the problem of polygon-clipping against a clip window into identical sub-problems.

A sub-problem is to clip all polygon edges (pair of vertices) in succession against a single infinite clip edge. The output is a set of clipped edges or pairs of vertices that fall on the visible side of that edge.
Now, let us see in steps what exactly happens while clipping our initial arrow-shaped quadrilateral against a rectangular clip window following the above rules:

Step1 – Clip against Left edge
Input vertex list [V1, V2, V3, V4]
Edge V1-> V2 : output V1
Edge V2-> V3 : output V2‘, V3
Edge V3-> V4 : output V4
Edge V4-> V1 : output V1
Output vertex list [V1‘, V2‘, V3, V4, V1]

Sutherland-Hodgman Polygon Clipping Algorithm

Step2 – Clip against Bottom edge
Input vertex list [V1‘, V2‘, V3, V4, V1]
Edge V1‘-> V2‘ : output V2
Edge V2‘-> V3 : output V2
Edge V3-> V4 : output V3‘, V4
Edge V4-> V1 : output V1
Edge V1-> V1‘ : output V1
Output vertex list [V2‘, V2‘, V2”, V3‘, V4, V1, V1‘]

Sutherland-Hodgman Polygon Clipping

Step3 – Clip against Right edge
Input vertex list [V2‘, V2”, V3‘, V4, V1, V1]
Edge V2‘-> V2” : output V2
Edge V2”-> V3‘ : output V2”’
Edge V3‘-> V4 : output V3”, V4
Edge V4-> V1 : output V4
Edge V1-> V1‘ : output V1”, V1
Edge V1‘-> V2‘ : output V2
Output vertex list [V2”, V2”’, V3”, V4, V4‘, V1”, V1‘, V2‘]

Sutherland-Hodgman Polygon Clipping Step3

Step4 – Clip against Top edge
Input vertex list [V2”, V2”’, V3”, V4‘, V1”, V1‘, V2‘]
Edge V2‘-> V2”’ : output V2”’
Edge V2”’-> V3” : output V3
Edge V3”-> V4 : output V4
Edge V4‘-> V4‘ : output V4
Edge V4‘-> V1” : output V4
Edge V1”-> V1‘ : output V1”’, V1
Edge V1‘-> V2‘ : output V2
Edge V2‘-> V2” : output V2
Output vertex list [V2”’, V3”, V4, V4‘, V4”, V1”’, V1‘, V2‘, V2”]

Sutherland-Hodgman Polygon Clipping Step4

Step5 – The Final Clipped Polygon
Output vertex list [V2”’, V3”, V4, V4‘, V1”’, V1‘, V2‘, V2”]

Sutherland-Hodgman Polygon Clipping final step