A Plane Sweep Trapezoidal Decomposition Algorithm

We imagine a horizontal line (the sweep line) passing through each vertex in turn, where the vertices are in increasing y-order. At each such vertex, one or more trapezia are output.

For any sweep line the edges are kept in ascending order of intersection, and there will always be an even number of edges for each sweep line position. The edges should be considered as neighbouring pairs. When the sweep line reaches a vertex, there are six possible cases shown above. Each case represents a pair of neighbouring edges. (The names in italics are used in the C code).

• Case A TrapRight: The sweep line forms a trapezium by intersecting with the edge to the right.
• Case B TrapLeft: The sweep line forms a trapezium by interesecting with the edge to the left.
• Case C TrapTop: The sweep line forms a trapezium, in the case where the neighbouring edges have each reached their top.
• Case D TrapTop: Another example of the same situation, except that here there are no additional edges to take the place of the completed ones.
• Case E TrapTop: We do not distinguish between triangles and trapezia here, so this is identical to the previous case (though the trapezium that is output is 'degenerate').
• Case F Trap: In this case the sweep line is caused by one or more vertices that are between another pair. These vertices will always be local minima.

The Edge Table (ET)

Each original polygon edge is represented by its two vertices (x1, y1) and (x2,y2), organised so that always y1<y2 (with horizontal edges ignored). In addition the reciprocal of the slope dx/dy is kept with each edge. In C:-

/*defines an edge, with lower x at x1, upper y at y2, and dx/dy*/
typedef struct{
     int y1, y2;
	    double x1, x2, dxdy;
} Edge;

The Edge Table, is an array of lists of edges, such that ET[y] is a sorted list of all edges which have lower y-coordinate at y. In other words the ET is a 'bucket' sort of the edges, with the sorting criteria being the y1 coordinate of the edge. (ET will be a sparse array of course).

The lists are created in sorted order from left to right. The sorting within each list is based on the x1-coordinate, or where these are the same on the angle between the edge and the positive x-axis, where the edge with the greatest angle is prior to the one with the smallest angle. Keeping the ET entries sorted is not entirely necessary, but can save some computation in sorting the active edge table.

The Active Edge Table (AET)

The AET is a list of those edges currently intersecting the sweep line. As it moves 'up' the polygon reaching a new vertex, there will be an analysis of each pair of edges in the AET, to see which of A to E occurs. We consider case A:

We label the left and right edges as edge0 and edge1. Suppose the sweep line is at y, then we find the intersection of y with edge1 (say at (xi,y)). Then in clockwise order the trapezium is output:

(edge0.x1,edge0.y1), (edge0.x2,y), (xi,y), (edge1.x1,edge1.y1) where edge0.y1==edge1.y1.

Next we update the right edge by replacing its lower vertex:
edge1.x1 = xi, edge1.y1 = y.

Case B is symmetric in the two edges, Case C is similar again except that there are no intersections to compute, and similarly with Cases D and E.

Next the Edge Table entries at y are checked to see if case F occurs, i.e., are there any edges in ET[y] with lower vertex in between two surviving edges in the AET. By a surviving edge we mean one that has y1<y and y2>y (an edge that will not be deleted from the AET by this sweep line). If so then the corresponding trapezia are output.

Next the AET is traversed and all entries with y2 == y are removed, since these have now been passed by the sweep line, and no more trapezia can depend on them.

Finally, the ET[y] edges are insert sorted into the AET, where the sorting criteria is, of course the x1-coordinate. (ET[y] may be empty of course).

This process continues until the sweep line has reached the global maximum of the polygon.

Mel Slater, November 1997.