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 [V₁, V₂, V₃, V₄]
Edge V₁-> V₂ : output V₁‘
Edge V₂-> V₃ : output V₂‘, V₃
Edge V₃-> V₄ : output V₄
Edge V₄-> V₁ : output V₁
Output vertex list [V₁‘, V₂‘, V₃, V₄, V₁]

Step2 – Clip against Bottom edge
Input vertex list [V₁‘, V₂‘, V₃, V₄, V₁]
Edge V₁‘-> V₂‘ : output V₂‘
Edge V₂‘-> V₃ : output V₂”
Edge V₃-> V₄ : output V₃‘, V₄
Edge V₄-> V₁ : output V₁
Edge V₁-> V₁‘ : output V₁‘
Output vertex list [V₂‘, V₂‘, V₂”, V₃‘, V₄, V₁, V₁‘]

Step3 – Clip against Right edge
Input vertex list [V₂‘, V₂”, V₃‘, V₄, V₁, V₁]
Edge V₂‘-> V₂” : output V₂”
Edge V₂”-> V₃‘ : output V₂”’
Edge V₃‘-> V₄ : output V₃”, V₄
Edge V₄-> V₁ : output V₄‘
Edge V₁-> V₁‘ : output V₁”, V₁‘
Edge V₁‘-> V₂‘ : output V₂‘
Output vertex list [V₂”, V₂”’, V₃”, V₄, V₄‘, V₁”, V₁‘, V₂‘]

Step4 – Clip against Top edge
Input vertex list [V₂”, V₂”’, V₃”, V₄‘, V₁”, V₁‘, V₂‘]
Edge V₂‘-> V₂”’ : output V₂”’
Edge V₂”’-> V₃” : output V₃”
Edge V₃”-> V₄ : output V₄
Edge V₄‘-> V₄‘ : output V₄‘
Edge V₄‘-> V₁” : output V₄”
Edge V₁”-> V₁‘ : output V₁”’, V₁‘
Edge V₁‘-> V₂‘ : output V₂‘
Edge V₂‘-> V₂” : output V₂”
Output vertex list [V₂”’, V₃”, V₄, V₄‘, V₄”, V₁”’, V₁‘, V₂‘, V₂”]

Step5 – The Final Clipped Polygon
Output vertex list [V₂”’, V₃”, V₄, V₄‘, V₁”’, V₁‘, V₂‘, V₂”]