CS-460/560, Week 9A
Spring, 1998
R. Eckert


Clip a polygon to a rectangular clip area whose boundaries are
parallel to the x-y coordinate system axes.

Input: an ordered list of polygon vertices (nin, vin[]) and the
clip region boundary coordinates (xmin, ymin, xmax, ymax).

Output: an ordered list of clipped polygon vertices (nout, vout[]).
Here vin[] and vout[] could be an arrays of POINTs. (In the following,
vertex variables that begin with upper case letters represent single 
vertex points. Lower case vertex variables represent arrays of points.)

Approach: clip all edges of the polygon with respect to each clipping
boundary. Do four passes. On each pass, traverse the polygon and clip with
respect to one of the four boundaries. Assemble the output polygon as you
go. The output polygon of the clipping with respect to boundary i will
become the input polygon with respect to boundary i+1. In other words:

vin[] --> Clip Left --> vtemp1[] --> Clip Right --> vtemp2[] -->
Clip Bottom --> vtemp3[] --> Clip Top --> vout[]

As we traverse the polygon on any of these four passes, the clipping
boundary divides the plane into an "in" side half-plane and an "out" side
half-plane. For any given edge (characterized by vertices i and i+1),
during the traversal, there are four possibilities:

vertex i   vertex i+1    Action
   in       in         Add vertex i+1 to output list
   out      out        Add no vertex to the output list
   in       out        Add intersection pt with edge to output list
   out      in         Add intersection pt with edge to ouput list
                       as well as vertext i+1

Here we assume that vertex i was taken care of when the previous edge was 

We want to implement a function sh_clip() that will clip an input polygon
(ni, vi[]) with respect to a given boundary (bndry), generating an output
polygon (no, vo[]). We will enumerate the boundaries as LEFT, RIGHT,

   sh_clip(ni, vi[], no, vo[], xmin, ymin, xmax, ymax, bndry);

Here vi[] and vo[] could both be arrays of POINTs, and ni, no are the
numbers of points in each array. xmin, ymin, xmax, ymax are the clip
region boundary coordinates.

In order to clip the input polygon (nin, vin[]), to the clip region
(xmin, xmax, ymin, ymax), generating the output polygon (nout, vout[]), 
we would make four calls to sh_clip():

sh_clip(nin, vin[], ntemp1, vtemp1[], xmin, ymin, xmax, ymax, LEFT);
sh_clip(ntemp1, vtemp1[], ntemp2, vtemp2[], xmin, ymin, xmax, ymax, RIGHT);
sh_clip(ntemp2, vtemp2[], ntemp3, vtemp3[], xmin, ymin, xmax, ymax, BOTTOM);
sh_clip(ntemp3, vtemp3[], nout, vout[], xmin, ymin, xmax, ymax, TOP);

To facilitate the development of sh_clip(), assume we have the following
three helper functions:

BOOL inside(V, xmin, ymin, xmax, ymax, Bndry)  -- 
     Returns TRUE if vertex point V is on the "in" side of boundary Bndry.

VOID intersect(V1, V2, xmin, ymin, xmax, ymax, Bndry, Vnew) -- 
     Computes the intersection point of the edge whose endpoints are V1 and 
     V2 with boundary Bndry and returns the resulting point in Vnew.

VOID output(V, n, vout[]) -- 
     Adds vertex point V to the polygon (n, v[]). Here n will be incremented 
     by 1 and vertex V added to the end of the polygon's vertex list v[].

PSEUDO-CODE FOR sh_clip() --

sh_clip(ni, vi[], no, vo[], bndry)
   no = 0                         // output list begins empty
   First_V = vi[0]                // current edge's first vertex (i)
   For (j=0 to ni-1)              // traverse the polygon
      Second_V = v[(j+1) MOD ni]  // current edge's second vertex (i+1)
      If (inside(first_V, bndry)
         If (inside(Second_V, bndry)   // "in-in" case
            output(Second_V, no, vo)
         Else                          // "in-out" case
            intersect(First_V, Second_V, bndry, Vtemp)
            output (Vtemp, no, vo)
         If (inside(Second_V, bndry)   // "out-in" case
            intersect(First_V, Second_V, bndry, Vtemp)
            output(Vtemp, no, vo)
            output(Second_V, no, vo)   // note empty Else ("out-out" case)
      First_V = Second_V               // prepare for next edge

Note that this works fine with convex polygons, but can have problems with
some concave polygons. In some cases extraneous edges along the clip
boundary may be generated as a part of the output polygon. One way to
solve this problem would be to add a postprocessing step in which we check
the output vertex list for multiple vertex points along any clip boundary
and correctly join pairs of vertices. A better approach is to use a more
general clipping algorithm, such as the Weiler-Atherton polygon clipper.


Clips a "Subject Polygon" to a "Clip Polygon" giving one or
more output polygons that lie entirely inside the clip polygon.
Both polygons can be of any shape.

1. Set up the vertex list for the subject and clip polygons.

   (The ordering should be such that as you move down each list
   the inside of the polygon is always on the right side.)

2. Compute all intersection points between subject polygon and
   clip polygon edges; insert them into each polygon's list; mark
   as intersection points.

   Mark those intersection points in which the subject polygon
   edge is moving from outside of the clip polygon to inside.
   (outside/inside tests on subject polygon edge endpoints.)

3. Do until all intersection points have been visited:

   Traverse the subject polygon list until you find a non-visited
   intersection point; output the point to a new output list.

   Make the subject polygon list be the active list.

   Do until a vertex is revisited:

      Get the next vertex from the active list and output.

      If vertex is an intersection point, make the other list active.

   End the current output polygon list.