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.)




F clip(subjectPolygon, clipPolygon)
   F inside(p, cp1, cp2)
      R (cp2.x - cp1.x) * (p.y - cp1.y) > (cp2.y - cp1.y) * (p.x - cp1.x)
 
   F computeIntersection(s, e, cp1, cp2)
      V dc = cp1 - cp2
      V dp = s - e
      V n1 = cp1.x * cp2.y - cp1.y * cp2.x
      V n2 = s.x * e.y - s.y * e.x
      V n3 = 1.0 / (dc.x * dp.y - dc.y * dp.x)
      R ((n1 * dp.x - n2 * dc.x) * n3, (n1 * dp.y - n2 * dc.y) * n3)
 
   V outputList = subjectPolygon
   V cp1 = clipPolygon.last
 
   L(clipVertex) clipPolygon
      V cp2 = clipVertex
      V inputList = outputList
      outputList.clear()
      V s = inputList.last
 
      L(subjectVertex) inputList
         V e = subjectVertex
         I inside(e, cp1, cp2)
            I !inside(s, cp1, cp2)
               outputList.append(computeIntersection(s, e, cp1, cp2))
            outputList.append(e)
         E I inside(s, cp1, cp2)
            outputList.append(computeIntersection(s, e, cp1, cp2))
         s = e
      cp1 = cp2
   R (outputList)
 
V subjectp = [(50.0, 150.0), (200.0, 50.0), (350.0, 150.0), (350.0, 300.0), (250.0, 300.0), (200.0, 250.0), (150.0, 350.0), (100.0, 250.0), (100.0, 200.0)]
V clipp = [(100.0, 100.0), (300.0, 100.0), (300.0, 300.0), (100.0, 300.0)]
print_elements(clip(subjectp, clipp), sep' "\n")