Digital Mobile Map

1. Line Clipping

This section treats clipping of lines against rectangles. Although there are specialized algorithms for rectangle and polygon clipping, it is important to note that other graphic primitives can be clipped by repeated application of the line clipper.

1.1 Clipping Individual Points

Before we discuss clipping lines, let’s look at the simpler problem of clipping individual points.

If the x coordinate boundaries of the clipping rectangle are Xmin and Xmax, and the y coordinate boundaries are Ymin and Ymax, then the following inequalities must be satisfied for a point at (X,Y) to be inside the clipping rectangle:

Xmin < X < Xmax and Ymin < Y < Ymax

If any of the four inequalities does not hold, the point is outside the clipping rectangle.

1.2 Solve Simultaneous Equations

To clip a line, we need to consider only its endpoints, not its infinitely many interior points. If both endpoints of a line lie inside the clip rectangle, the entire line lies inside the clip rectangle and can be trivially accepted. If one endpoint lies inside and one outside(eg CD), the line intersects the clip rectangle and we must compute the intersection point. If both endpoints are outside the clip rectaangle, the line may or may not intersect with the clip rectangle (EF, GH, and IJ), and we need to perform further calculations to determine whether there are any intersections.

The brute-force approach to clipping a line that cannot be trivially accepted is to intersect that line with each of the four clip-rectangle edges to see whether any intersection points lie on those edges; if so, the line cuts the clip rectangle and is partially inside. For each line and clip-rectangle edge, we therefore take the two mathematically infinite lines that contain them and intersect them. Next, we test whether this intersection point is “interior” — that is, whether it lies within both the clip rectangle edge and the line; if so, there is an intersection with the clip rectangle. In the first example, intersection points G’ and H’ are interior, but I’ and J’ are not.

1.3 The Cohen-Sutherland Line-Clipping Algorithm

The more efficient Cohen-Sutherland Algorithm performs initial tests on a line to determine whether intersection calculations can be avoided.

Steps for Cohen-Sutherland algorithm

End-points pairs are check for trivial acceptance or trivial rejected using the outcode.

If not trivial-accepance or trivial-rejected, divided into two segments at a clip edge.

Iteratively clipped by testing trivial-acceptance or trivial-rejected, and divided into two segments until completely inside or trivial-rejected.

Trivial acceptance/reject test

To perform trivial accept and reject tests, we extend the edges of the clip rectangle to divide the plane of the clip rectangle into nine regions. Each region is assigned a 4-bit code deteermined by where the region lies with respect to the outside halfplanes of the clip-rectangle edges. Each bit in the outcode is set to either 1 (true) or 0 (false); the 4 bits in the code correspond to the following conditions:

1. • Bit 1 : outside halfplane of top edge, above top edge
     Y > Ymax

   • Bit 2 : outside halfplane of bottom edge, below bottom edge
     Y < Ymin

   • Bit 3 : outside halfplane of right edge, to the right of right edge
     X > Xmax

   • Bit 4 : outside halfplane of left edge, to the left of left edge
     X < Xmin

Conclusion

In summary, the C-S algorithm is efficient when outcode testing can be done cheaply (for example, by doing bitwise operations in assembly language) and trivial acceptance or rejection is applicable to the majority of line segments .(For example, large windows - everything is inside , or small windows - everything is outside).

Pseudo-code of Cohen-Sutherland Algorithm.

procedure CohenSutherlandLineClipAndDraw(
x0,y0,x1,y1,xmin,xmax,ymin,ymax : real ; value: integer);
/* Cohen-Sutherland clipping algorithm for line P0=(x1,y0) to P1=(x1,y1) and clip rectangle with diagonal from (xmin,ymin) to (xmax,ymax).*/

type
edge = (LEFT,RIGHT,BOTTOM,TOP);
outcode = set of edge;
var
accept,done : boolean;
outcode0,outcode1,outcodeOut : outcode;
/*Outcodes for P0,P1, and whichever point lies outside the clip rectangle*/
x,y : real;
procedure CompOutCode(x,y: real; var code:outcode);
/*Compute outcode for the point (x,y) */
begin
code := [];
if y > ymax then code := [TOP]
else if y < ymin then code := [BOTTOM];
if x > xmax then code := code +[RIGHT]
else if x < xmin then code := code +[LEFT]
end;

begin
accept := false;  done := false;
CompOutCode (x0,y0,outcode0); CompOutCode (x1,y1,outcode1);
repeat
if(outcode0=[]) and (outcode1=[]) then /*Trivial accept and exit*/
begin accept := true; done:=true end
else if (outcode0*outcode1) <> [] then
done := true    /*Logical intersection is true, so trivial reject and exit.*/
else
/*Failed both tests, so calculate the line segment to clip;
from an outside point to an intersection with clip edge.*/
begin
/*At least one endpoint is outside the clip rectangle; pick it.*/
if outcode0 <> [] then
outcodeOut := outcode0 else outcodeOut := outcode1;
/*Now find intersection point;
use formulas y=y0+slope*(x-x0),x=x0+(1/slope)*(y-y0).*/
if TOP in outcodeOut then
begin     /*Divide line at top of clip rectangle*/
x := x0 + (x1 - x0) * (ymax - y0) / (y1 - y0);
y := ymax
end
if BOTTOM in outcodeOut then
begin     /*Divide line at bottom of clip rectangle*/
x := x0 + (x1 - x0) * (ymin - y0) / (y1 - y0);
y := ymax
end
else if RIGHT in outcodeOut then
begin     /*Divide line at right edge of clip rectangle*/
y := y0 + (y1 - y0) * (xmax - x0) / (x1 - x0);
x := xmax
end
else if LEFT in outcodeOut then
begin     /*Divide line at left edge of clip rectangle*/
y := y0 + (y1 - y0) * (xmin - x0) / (x1 - x0);
x := xmin
end;
/*Now we move outside point to intersection point to clip, and get ready for next pass.*/
if (outcodeOut = outcode0) then
begin
x0 := x; y0 := y; CompOutCode(x0,y0,outcode0)
end
else
begin
x1 := x; y1 := y; CompOutCode(x1,y1,outcode1);
end
end   /*subdivide*/
until done;
if accept then MidpointLineReal(x0,y0,x1,y1,value) /*Version for real coordinates*/
end; /*CohenSutherlandLineClipAndDraw*/

2. Polygon Clipping

An algorithm that clips a polygon must deal with many different cases. The case is particularly note worthy in that the concave polygon is clipped into two separate polygons. All in all, the task of clipping seems rather complex. Each edge of the polygon must be tested against each edge of the clip rectangle; new edges must be added, and existing edges must be discarded, retained, or divided. Multiple polygons may result from clipping a single polygon. We need an organized way to deal with all these cases.

The following example illustrate a simple case of polygon clipping:

The following example illustrate a complex case of polygon clipping:

Sutherland and Hodgman’s polygon-clipping algorithm uses a divide-and-conquer strategy: It solves a series of simple and identical problems that, when combined, solve the overall problem. The simple problem is to clip a polygon against a single infinite clip edge. Four clip edges, each defining one boundary of the clip rectangle, successively clip a polygon against a clip rectangle.

Note the difference between this strategy for a polygon and the Cohen-Sutherland algorithm for clipping a line: The polygon clipper clips against four edges in succession, whereas the line clipper tests the outcode to see which edge is crossed, and clips only when necessary.

Steps of Sutherland-Hodgman’s polygon-clipping algorithm

• Polygons can be clipped against each edge of the window one at a time. Windows/edge intersections, if any, are easy to find since the X or Y coordinates are already known.

• Vertices which are kept after clipping against one window edge are saved for clipping against the remaining edges.

• Note that the number of vertices usually changes and will often increases.

• We are using the Divide and Conquer approach.

Four Cases of polygon clipping against one edge

The clip boundary determines a visible and invisible region. The edges from vertex i to vertex i+1 can be one of four types:

• Case 1 : Wholly inside visible region - save endpoint

Points=[B]

• Case 2 : Exit visible region - save the intersection

Points=[B, B']

• Case 3 : Wholly outside visible region - save nothing

Points=[B, B']

• Case 4 : Enter visible region - save intersection and endpoint

Points=[B, B', C', A]

Because clipping against one edge is independent of all others, it is possible to arrange the clipping stages in a pipeline. The input polygon is clipped against one edge and any points that are kept are passed on as input to the next stage of the pipeline. This way four polygons can be at different stages of the clipping process simultaneously. This is often implemented in hardware.

Sutherland-Hodgman uses a divide-and-conquer strategy to attack the problem. First, it clips the polygon against the right clipping boundary. The resulting, partly clipped polygon is then clipped against the top boundary, and then the process is repeated for the two remaining boundaries. (Of course, it also works in another order.) In a way, it is the most natural thing to do. If you had to clip a paper polygon with a pair of scissors, you would probably proceed the same way.

Sutherland-Hodgman’s divide-and-conquer strategy. To clip a polygon against a rectangular boundary window, successively clip against each boundary.

To clip against one boundary, the algorithm loops through all polygon vertices. At each step, it considers two of them, called ‘previous’ and ‘current.’ First, it determines whether these vertices are inside or outside the clipping boundary. This, of course, is simply a matter of comparing the horizontal or vertical position to the boundary’s position.

Then, it applies the following simple rules:

	If ‘previous’ and ‘current’ are both inside: Output ‘current.’
	If ‘previous’ is inside, and ‘current’ is outside: Output the intersection point of the corresponding edge and the clipping boundary.
	If ‘previous’ and ‘current’ are both outside: Do nothing.
	If ‘previous’ is outside, and ‘current’ is inside: Output the intersection point, and then output ‘current.’

This way, you get a new polygon, clipped against one boundary, and ready to be clipped against the next boundary. The method works, but has one disadvantage: To clip against all four boundaries, you have to store the intermediate, partly clipped polygons. It’s evident that this is a costly operation.

Luckily, there are ways to avoid the intermediate storage. Instead of storing an output point, you can send it to the next stage immediately, where it can be clipped against the next boundary.

The classical way to do this is to make one general boundary-clipping function, which calls itself recursively to put a vertex to the next stage. An extra parameter tells the function which boundary to use for clipping. Inside the function, a few switch statements account for the differences.

A somewhat faster option is to create separate functions for the four boundaries, thus eliminating the nasty switch statements. However, this means developing and debugging four very similar functions, which is an open invitation for all kinds of trouble.

Pseudo-Code of Sutherland and Hodgman’s polygon-clipping Algorithm.

type
vertex = point;    /*point hold real x,y*/
edge = array[1..2] of vertex;
vertexArray = array[1..MAX] of vertex; /*MAX is a declared constant*/

procedure SutherlandHodgmanPolygoClip (
inVertexArray : vertexArray;          /*Input vertex array*/
var outVertexArray : vertexArray;  /*Output vertex array*/
inLength : integer;                   /*Number of entries in inVertexArray*/
var outLength : integer;           /*Number of entries in outVertexArray*/
clipBoundary : edge);              /*Edge of clip polygon*/
var
s,p,                            /*Start, end point of current polygon edge*/
i : vertex;                   /*Intersection point with a clip boundary*/
j : integer;                  /*Vertex loop counter*/

procedure Output(
newVertex : vertex; var outLength : integer; var outVertexArray : vertexArray);
/*Adds newVertex to outVertexArray and then updates outLength */
begin
…
end;

function Inside(testVertex : vertex; clipBoundary : edge):boolean;
/*Checks whether the vertex lies inside the clip edge or not*/
begin
…
end;

procedure Intersect(first,second:vertex; clipBoundary:edge; var intersectPt:vertex);
/*Clips polygon edge (first,second) against clipBoundary, outputs the new point*/
begin
…
end;

begin
outLength := 0;
s := inVertexArray[inLength];
/*Start with the last vertex in inVertexArray*/
for j := 1 to inLength do
begin
p := inVertexArray[j]; /*Now s and p correspond to the vertices in Fig. 3.48*/
if Inside(p,clipBoundary) then       /*Cases 1 and 4*/
if Inside(s, clipBoundary) then
Output(p, outLength, outVertexArray)    /*Case 1*/
else
begin
Intersect(s, p, clipBoundary, i);
Output(i, outLength, outVertexArray);
Output(p, outLength, outVertexArray)
end
else                                        /*Cases 2 and 3*/
if Inside(s, clipBoundary) then           /*Cases 2*/
begin
Intersect(s, p, clipBoundary, i);
Output(i, outLength, outVertexArray)
end;                           /*No action for case 3*/
s := p                             /*Advance to next pair of vertices*/
end /*for*/
end; /*SutherlandHodgmanPolygonClip*/

Authors: Huiling Yang, Haowei Hsieh and Sjaak Priester