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




--
-- demo\rosetta\Sutherland_Hodgman_polygon_clipping.exw
-- ====================================================
--
with javascript_semantics
enum X,Y

function inside(sequence cp1, cp2, p)
    return (cp2[X]-cp1[X])*(p[Y]-cp1[Y])>(cp2[Y]-cp1[Y])*(p[X]-cp1[X])
end function

function intersect(sequence cp1, cp2, s, e)
    atom {dcx,dcy} = {cp1[X]-cp2[X],cp1[Y]-cp2[Y]},
         {dpx,dpy} = {s[X]-e[X],s[Y]-e[Y]},
         n1 = cp1[X]*cp2[Y]-cp1[Y]*cp2[X],
         n2 = s[X]*e[Y]-s[Y]*e[X],
         n3 = 1/(dcx*dpy-dcy*dpx)
    return {(n1*dpx-n2*dcx)*n3,(n1*dpy-n2*dcy)*n3}
end function

function sutherland_hodgman(sequence subjectPolygon, clipPolygon)
    sequence cp1 = clipPolygon[$],
      outputList = subjectPolygon
    for i=1 to length(clipPolygon) do
        sequence cp2 = clipPolygon[i],
           inputList = outputList,
                   s = inputList[$]
        outputList = {}
        for j=1 to length(inputList) do
            sequence e = inputList[j]
            if inside(cp1,cp2,e) then
                if not inside(cp1,cp2,s) then
                    outputList = append(outputList,intersect(cp1,cp2,s,e))
                end if
                outputList = append(outputList,e)
            elsif inside(cp1,cp2,s) then
                outputList = append(outputList,intersect(cp1,cp2,s,e))
            end if
            s = e
        end for
        cp1 = cp2
    end for
    return outputList
end function

constant subjectPolygon = {{50, 150}, {200, 50}, {350, 150}, {350, 300},
                           {250, 300}, {200, 250}, {150, 350}, {100, 250},
                           {100, 200}},
         clipPolygon = {{100, 100}, {300, 100}, {300, 300}, {100, 300}}

sequence clippedPolygon = sutherland_hodgman(subjectPolygon,clipPolygon)

include pGUI.e

Ihandle dlg, canvas
cdCanvas cddbuffer, cdcanvas

procedure draw_poly(sequence poly)
    cdCanvasBegin(cddbuffer,CD_FILL)
    for i=1 to length(poly) do
        atom {x,y} = poly[i]
        cdCanvasVertex(cddbuffer,x,y)
    end for
    cdCanvasEnd(cddbuffer)
end procedure

function redraw_cb(Ihandle /*ih*/)
    cdCanvasActivate(cddbuffer)
    cdCanvasClear(cddbuffer)
    cdCanvasSetForeground(cddbuffer, CD_CYAN)
    draw_poly(subjectPolygon)
    cdCanvasSetForeground(cddbuffer, CD_MAGENTA)
    draw_poly(clipPolygon)
    cdCanvasSetForeground(cddbuffer, CD_ORANGE)
    draw_poly(clippedPolygon)
    cdCanvasFlush(cddbuffer)
    return IUP_DEFAULT
end function

function map_cb(Ihandle ih)
    cdcanvas = cdCreateCanvas(CD_IUP, ih)
    cddbuffer = cdCreateCanvas(CD_DBUFFER, cdcanvas)
    cdCanvasSetBackground(cddbuffer, CD_WHITE)
    cdCanvasSetForeground(cddbuffer, CD_GRAY)
    return IUP_DEFAULT
end function

procedure main()
    IupOpen()
    canvas = IupCanvas("RASTERSIZE=400x400")
    IupSetCallbacks(canvas, {"MAP_CB", Icallback("map_cb"),
                             "ACTION", Icallback("redraw_cb")})
    dlg = IupDialog(canvas, "RESIZE=NO")
    IupSetAttribute(dlg, "TITLE", "Sutherland-Hodgman polygon clipping")
    IupShow(dlg)
    if platform()!=JS then
        IupMainLoop()
        IupClose()
    end if
end procedure

main()
