# 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]

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‘]

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‘]

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”]

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