JHAVÉ Java-Hosted Algorithm Visualization Environment

### Objectives

To understand the Sutherland Hodgman Clipping Algorithm

### Algorithm Description

Generally, the operation of clipping is described as reducing a polygonal surface by removing portions of the surface which extend beyond some boundary.  The Sutherland Hodgman clipping algorithm describes a method of clipping using two polygons. The first polygon, the clipping polygon, is defined in terms of a series of edges. The second polygon, the subject polygon, is defined as a series of vertices. The subject polygon may be convex or concave whereas the clipping polygon must be convex. A polygon is convex if a line that is drawn between any two vertices defining the polygon will be contained inside the polygon.  This algorithm uses the clipping polygon to bound the subject polygon, in effect the subject polygon will be "clipped" against the clipping polygon.

For each edge, an infinite straight line is defined for it. The algorithm proceeds by traversing over consecutive pairs of vertices of the subject polygon, starting with the last vertex and the first vertex defining the subject polygon. The first element in the pair is defined as the starting vertex (s) and the second element is known as the ending vertex (p). Each pair of vertices is compared to the edge under consideration, and are determined to be either inside or outside the given edge. A vertex v is inside an edge if v falls on the same "side" of the edge line as another point on the clipping polygon. Outside is defined to be the opposite of inside. For each comparison with an edge, the algorithm defines certain vertices to be added to the final output. With the following definitions, there are four possibilities for a given starting vertex, ending vertex and edge.

Case 1: Both the starting vertex and ending vertex fall inside the edge.

For this case, the algorithm adds the ending vertex to the final output. Case 2: The starting vertex is inside and the ending vertex is outside.

For this case, the algorithm computes the intersection point between the line defined by
the starting vertex and ending vertex and the edge. In this case only the computed intersection point
is added to the final output. Case 3: Both the starting vertex and ending vertex fall outside the edge
For this case, nothing is added to the final output Case 4: The ending vertex is inside and the starting vertex is outside.

For this case, the algorithm computes the intersection point between the line defined by the
the starting vertex and ending vertex and the edge. In this case the computed intersection point and
the ending vertex is added to the final output. To complete the clipping operation, traverse over all edges of the clipping polygon and, when the final output is produced for a given edge, this output becomes the input for the next edge to be considered. Once all the edges have been traversed in this fashion, the final output will be the subject polygon fit within the bounds of the clipping polygon.

### Pseudo Code

For Each Edge in clipping polygon
create plane for edge

For Each Vertex pair in subject polygon
determine case number from starting vertex, ending vertex, and edge
perform case operation
End For Each
update subject polygon with new vertices

End For Each

### Java Implementation

public static void sutherland_hodgman_clipping(ArrayList<Point> subjectPolygon,
ArrayList<Edge> clippingPolygon)
{
ArrayList<Edge> edges = clippingPolygon;
ArrayList<Point> input = subjectPolygon;
ArrayList<Point> output = new ArrayList<Point>();
int casenum = 0;
for(int i = 0; i < edges.size(); ++i) {
Edge e = edges.get(i);
Point r = edges.get( (i + 2) % edges.size()).getP1();
Point s = input.get(input.size() - 1);
for(int j = 0; j < input.size(); ++j) {
Point p = input.get(j);
if(Edge.isPointInsideEdge(e,r,p)) {
if(Edge.isPointInsideEdge(e,r,s)) {
casenum = 1;
}else{
casenum = 4;
}
} else {
if(Edge.isPointInsideEdge(e,r,s)) {
casenum = 2;
}else{
casenum = 3;
}
}
switch (casenum) {
case 1:
break;
case 2:
Point pi = e.computeIntersection(s, p);
break;
case 3: //Do nothing
break;
case 4:
Point pa = e.computeIntersection(s, p);
break;
}
s = p;
}//End of For
input = (ArrayList<Point>)output.clone();
output.clear();
}//End of For
}

### Algorithm within JHAVE

For a video of this visualization that will provide an overview of its use, please click the following link.
Use case video

This visualization supports three different modes.  The first of which is known as standard mode.  In this mode, the system will generate polygons to be used in the clipping algorithm.  These polygons will showcase all aspects of the algorithm.  To view the algorithm in standard mode click the following link.

Standard Mode
(Note this might take a few moments to load)

You will now be brought to a window with the visualization. To step through the visualization use the right and left arrows in the bottom of the window. If this is your first time viewing this visualization, we suggest disabling questions under the Options Menu. Once you feel comfortable with the algorithm, enable questions and proceed through the visualization. Once you are able to correctly answer a majority of the questions, you should proceed to the second mode of the visualization (Exercises).

### Exercises

This visualization supports a series of exercises designed to test user understanding of the Sutherland Hodgman Clipping Algorithm.  Once you click any of the following links for a particular exercise, you will need to click in a data set that satisfies the requirements of the selected exercise. Initially the clipping polygon is selected; simply click in points in the Click Area. The window automatically will close your polygon; you can drag a point and see the resulting polygon. Use the Undo button to undo the last click. Similarly select the Subject Polygon and click in points. You can only click in up to 8 points per polygon.

The exercise list is as follows: