Sutherland –hodgeman polygon clipping algorithm

Polygon:

Polygon is a representation of the surface. It is primitive which is closed in nature. It is formed using a collection of lines. It is also called as many-sided figure. The lines combined to form polygon are called sides or edges. The lines are obtained by combining two vertices.

Types of Polygons

1. Concave
2. Convex

A polygon is called convex of line joining any two interior points of the polygon lies inside the polygon. A non-convex polygon is said to be concave. A concave polygon has one interior angle greater than 180°. So that it can be clipped into similar polygons. 

Sutherland –hodgeman polygon clipping algorithm

---

Introduction: We can correctly clip a polygon by processing the polygon boundary as a whole against each window edge. This could be accomplished by processing all polygon vertices against each clip rectangle boundary in turn. Beginning with the initial set of polygon vertices, we could first clip the polygon against the left rectangle boundary to produce a new sequence of vertices. The new set of vertices could then k successively passed to a right boundary clipper, a bottom boundary clipper, and a top boundary clipper, as in Fig. 6-19. At each step, a new sequence of output vertices is generated and passed to the next window boundary clipper.

It is often necessary, particularly in graphics applications, to "clip" a given polygon with another. Figure 1 shows an example. In the figure, the clipping polygon is drawn with a dashed line, the clipped polygon with a regular line, and the resulting polygon is drawn with a heavy line. In this article we'll look at the particular case where the clipping polygon is a rectangle which is oriented parallel with the axes. For this case, the Sutherland-Hodgeman algorithm is often employed. This is the algorithm that we will explore.

 

 

The Sutherland-Hodgeman Algorithm

The Sutherland-Hodgeman polygon clipping algorithm is relatively straightforward and is easily implemented in C. It does have some limitations, which we'll explore later. First, let's see how it works. For each of the four sides of the clipping rectangle, consider the line L through the two points which define that side. For each side, this line creates two planes, one which includes the clipping rectangle and one which does not. We'll call the one which does not the "clipping plane" (Figure 2).

 

 

For each of the four clipping planes, we must remove any vertices of the clipped polygon which lie inside the plane and create new points where the segments associated with these vertices cross the lineL (Figure 3).

After clipping each of the four planes, we are left with the clipped polygon.

Limitations :   

This algorithm always produces a single output polygon, even if the clipped polygon is concave and arranged in such a way that multiple output polygons might reasonably be expected. Instead, the polygons will be linked with overlapping segments along the edge of the clipping rectangle (Figure 4). This may or may not be the desired result, depending on your application