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




import sequtils, strformat
 
type
  Vec2 = tuple[x, y: float]
  Edge = tuple[p, q: Vec2]
  Polygon = seq[Vec2]
 
 
func `-`(a, b: Vec2): Vec2 = (a.x - b.x, a.y - b.y)
 
func cross(a, b: Vec2): float = a.x * b.y - a.y * b.x
 
func isInside(p: Vec2; edge: Edge): bool =
  (edge.q.x - edge.p.x) * (p.y - edge.p.y) > (edge.q.y - edge.p.y) * (p.x - edge.p.x)
 
 
func intersection(sEdge, cEdge: Edge): Vec2 =
  let
    dc = cEdge.p - cEdge.q
    dp = sEdge.p - sEdge.q
    n1 = cEdge.p.cross(cEdge.q)
    n2 = sEdge.p.cross(sEdge.q)
    n3 = 1 / dc.cross(dp)
  result = ((n1 * dp.x - n2 * dc.x) * n3, (n1 * dp.y - n2 * dc.y) * n3)
 
 
func edges(poly: Polygon): seq[Edge] =
  (poly[^1] & poly).zip(poly)
 
 
func clip(subjectPolygon, clipPolygon: Polygon): Polygon =
  assert subjectPolygon.len > 1
  assert clipPolygon.len > 1
 
  result = subjectPolygon
  for clipEdge in clipPolygon.edges:
    let inputList = move(result)
    result.reset()
    for inEdge in inputList.edges:
      if inEdge.q.isInside(clipEdge):
        if not inEdge.p.isInside(clipEdge):
          result.add intersection(inEdge, clipEdge)
        result.add inEdge.q
      elif inEdge.p.isInside(clipEdge):
        result.add intersection(inEdge, clipEdge)
 
 
proc saveEpsImage(filename: string; subject, clip, clipped: Polygon) =
  let eps = open(filename, fmWrite)
  eps.write "%%!PS-Adobe-3.0\n%%%%BoundingBox: 40 40 360 360\n/l {lineto} def\n/m {moveto} def\n",
            "/s {setrgbcolor} def\n/c {closepath} def\n/gs {fill grestore stroke} def\n"
 
  eps.write &"0 setlinewidth {clip[0].x} {clip[0].y} m "
  for i in 1..clip.high:
    eps.write &"{clip[i].x} {clip[i].y} l "
  eps.writeLine "c 0.5 0 0 s gsave 1 0.7 0.7 s gs"
 
  eps.write &"{subject[0].x} {subject[0].y} m "
  for i in 1..subject.high:
    eps.write &"{subject[i].x} {subject[i].y} l "
  eps.writeLine "c 0 0.2 0.5 s gsave 0.4 0.7 1 s gs"
 
  eps.write &"2 setlinewidth [10 8] 0 setdash {clipped[0].x} {clipped[0].y} m "
  for i in 1..clipped.high:
    eps.write &"{clipped[i].x} {clipped[i].y} l "
  eps.writeLine &"c 0.5 0 0.5 s gsave 0.7 0.3 0.8 s gs"
 
  eps.writeLine "%%%%EOF"
  eps.close()
  echo &"File “{filename}” written."
 
 
when isMainModule:
 
  let
    subjectPolygon = @[(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)]
    clippingPolygon = @[(100.0, 100.0), (300.0, 100.0), (300.0, 300.0), (100.0, 300.0)]
 
    clipped = subjectPolygon.clip(clippingPolygon)
 
  for point in clipped:
    echo &"({point.x:.3f}, {point.y:.3f})"
  saveEpsImage("sutherland_hodgman_clipping_out.eps", subjectPolygon, clippingPolygon, clipped)