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




 
open window 400, 400
backcolor 0,0,0
clear window
 
DPOL = 8
DREC = 3
CX = 1 : CY = 2
 
dim poligono(DPOL, 2)
dim rectang(DREC, 2)
dim clipped(DPOL + DREC, 2)
 
for n = 0 to DPOL : read poligono(n, CX), poligono(n, CY) : next n
DATA 50,150, 200,50, 350,150, 350,300, 250,300, 200,250, 150,350, 100,250, 100,200
for n = 0 to DREC : read rectang(n, CX), rectang(n, CY) : next n
DATA 100,100, 300,100, 300,300, 100,300
 
 
color 255,0,0
dibuja(poligono(), DPOL)
color 0,0,255
dibuja(rectang(), DREC)
 
nvert = FNsutherland_hodgman(poligono(), rectang(), clipped(), DPOL + DREC)
color 250,250,0
dibuja(clipped(), nvert - 1)
 
 
sub dibuja(figura(), i)
	local n
 
	print
	new curve
	for n = 0 to i
		line to figura(n, CX), figura(n, CY)
		print figura(n, CX), ", ", figura(n, CY)
	next n
	close curve
end sub
 
 
sub FNsutherland_hodgman(subj(), clip(), out(), n)
	local i, j, o, tclip, p1(2), p2(2), s(2), e(2), p(2), inp(n, 2)
 
	FOR o = 0 TO arraysize(subj(), 1) : out(o, CX) = subj(o, CX) : out(o, CY) = subj(o, CY) : NEXT o
 
	tclip = arraysize(clip(),1)
	p1(CX) = clip(tclip, CX) : p1(CY) = clip(tclip, CY)
 
	FOR i = 0 TO tclip
	    p2(CX) = clip(i, CX) : p2(CY) = clip(i, CY)
	    FOR n = 0 TO o - 1 : inp(n, CX) = out(n, CX) : inp(n, CY) = out(n, CY) : NEXT n : o = 0
	  	IF n >= 2 THEN
	            s(CX) = inp(n - 1, CX) : s(CY) = inp(n - 1, CY)
 
	    	    FOR j = 0 TO n - 1
	      		e(CX) = inp(j, CX) : e(CY) = inp(j, CY)
	      		IF FNside(e(), p1(), p2()) THEN
	        		IF NOT FNside(s(), p1(), p2()) THEN
	          			PROCintersection(p1(), p2(), s(), e(), p())
	          			out(o, CX) = round(p(CX)) : out(o, CY) = round(p(CY))
	          			o = o + 1
	        		ENDIF
	        		out(o, CX) = round(e(CX)) : out(o, CY) = round(e(CY))
	        		o = o + 1
	      		ELSE
	        		IF FNside(s(), p1(), p2()) THEN
	          			PROCintersection(p1(), p2(), s(), e(), p())
	          			out(o, CX) = round(p(CX)) : out(o, CY) = round(p(CY))
	          			o = o + 1
	        		ENDIF
	      		ENDIF
	      		s(CX) = e(CX) : s(CY) = e(CY)
	    	    NEXT j
	  	ENDIF
	  	p1(CX) = p2(CX) : p1(CY) = p2(CY)
	NEXT i
	return o
end sub
 
 
sub FNside(p(), p1(), p2())
	return  (p2(CX) - p1(CX)) * (p(CY) - p1(CY)) > (p2(CY) - p1(CY)) * (p(CX) - p1(CX))
end sub
 
 
sub PROCintersection(p1(), p2(), p3(), p4(), p())
	LOCAL a(2), b(2), k, l, m
 
	a(CX) = p1(CX) - p2(CX) : a(CY) = p1(CY) - p2(CY)
	b(CX) = p3(CX) - p4(CX) : b(CY) = p3(CY) - p4(CY)
	k = p1(CX) * p2(CY) - p1(CY) * p2(CX)
	l = p3(CX) * p4(CY) - p3(CY) * p4(CX)
	m = 1 / (a(CX) * b(CY) - a(CY) * b(CX))
	p(CX) =  m * (k * b(CX) - l * a(CX))
	p(CY) =  m * (k * b(CY) - l * a(CY))
 
end sub
 
 
sub round(n)
	return int(n + .5)
end sub