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




class P{	// point
   fcn init(_x,_y){ var [const] x=_x.toFloat(), y=_y.toFloat() }
   fcn __opSub(p) { self(x - p.x, y - p.y) }
   fcn cross(p)   { x*p.y - y*p.x          }
   fcn toString   { "(%7.2f,%7.2f)".fmt(x,y) }
   var [const,proxy] ps=fcn{ T(x.toInt(),y.toInt()) };    // property
}
fcn shClipping(clip,polygon){
   inputList,outputList,clipEdge:=List(), polygon.copy(), List(Void,clip[-1]);
   foreach p in (clip){
      clipEdge.del(0).append(p);
      inputList.clear().extend(outputList);
      outputList.clear();
      S:=inputList[-1];
      foreach E in (inputList){
         if(leftOf(clipEdge,E)){
	    if(not leftOf(clipEdge,S))
	       outputList.append(intersection(S,E,clipEdge));
	    outputList.append(E);
	 }
	 else if(leftOf(clipEdge,S))
	         outputList.append(intersection(S,E,clipEdge));
	 S=E;
      }
   }
   outputList
}
fcn leftOf(line,p){ //-->True (p is left of line), direction of line matters
   p1,p2:=line;		// line is (p1,p2)
   (p2-p1).cross(p-p2)>0;
}
fcn intersection(p1,p2, line){	//-->Point of intersection or False
   p3,p4:=line;
   dx,dy,d:=p2-p1, p3-p4, p1-p3;
   // x0 + a dx = y0 + b dy ->
   // x0 X dx = y0 X dx + b dy X dx ->
   // b = (x0 - y0) X dx / (dy X dx)
   dyx:=dy.cross(dx);
   if(not dyx) return(False);  // parallel lines, could just throw on next line
   dyx=d.cross(dx)/dyx;
   P(p3.x + dyx*dy.x, p3.y + dyx*dy.y);
}
fcn drawPolygon(ppm,listOfPoints,rgb){
   foreach n in (listOfPoints.len()-1){
      ppm.line(listOfPoints[n].ps.xplode(),listOfPoints[n+1].ps.xplode(),rgb);
   }
   ppm.line(listOfPoints[0].ps.xplode(),listOfPoints[-1].ps.xplode(),rgb);
}