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




 
Type Point
      As Double x,y
End Type
 
Type Line
      As Point s,f'start/finish
End Type
 
Function isleft(L As Line,p As Point) As Long
      Return  -Sgn((L.s.x-L.f.x)*(p.y-L.f.y)-(p.x-L.f.x)*(L.s.y-L.f.y))
End Function
 
Function segmentintersections(L1 As Line,L2 As Line) As Long
      If isleft(L2,L1.s) = isleft(L2,L1.f) Then Return 0 
      If isleft(L1,L2.s) = isleft(L1,L2.f) Then Return 0
      Return 1
End Function
 
Function allintersections(l1 As Line,l2 As Line,_out As Point) As Long
      Const tolerance=.01
      Var p1=l1.s, p2=l1.f, p3=l2.s, p4=l2.f
      Var x12=p1.x-p2.x, x34=p3.x-p4.x, y12=p1.y-p2.y, y34=p3.y-p4.y
      Var c=x12*y34-y12*x34
      If Abs(c)<tolerance Then Return 0
      Var a=p1.x*p2.y-p1.y*p2.x, b=p3.x*p4.y-p3.y*p4.x
      _out.x = (a*x34-b*x12)/c
      _out.y = (a*y34-b*y12)/c
      Return 1
End Function
 
Dim As Point p1(...)={(50,150),(200,50),(350,150),(350,300),(250,300),(200,250), _
                     (150,350),(100,250),(100,200)}
 
Dim As Point p2(...)={(100,100),(300,100),(300,300),(100,300)}
'get the line segments around the polygons
Dim As Line L1(...)={(p1(0),p1(1)),(p1(1),p1(2)),(p1(2),p1(3)),(p1(3),p1(4)),(p1(4),p1(5)),_
                    (p1(5),p1(6)),(p1(6),p1(7)),(p1(7),p1(8)),(p1(8),p1(0))}
 
Dim As Line L2(...)={(p2(0),p2(1)),(p2(1),p2(2)),(p2(2),p2(3)),(p2(3),p2(0))}
 
'would normally draw these lines now, but not here.
Dim As Point x
For n1 As Long=Lbound(L1) To Ubound(L1)
      For n2 As Long=Lbound(L2) To Ubound(L2)
            If allintersections(L1(n1),L2(n2),x) And segmentintersections(L1(n1),L2(n2)) Then 
                  Print x.x,x.y
            End If
      Next
Next
 
Sleep
 