Thorsten's Weblog

Introduction

Beside the problem of general polygon clipping, which has been thoroughly researched in the past twenty or so years, it is sometimes the case that only rectangular areas have to be clipped against each other. Two very prominent examples are the calculation of redraw areas in a GUI application – widget and application content areas are, because of performance and simplicity, often represented as rectangles, and quick, approximative spatial indexing, e.g. for GIS data.

It turns out that constraining clip calculations to axis-aligned bounding boxes (aka AABB) allows for noticeable simplifications in the algorithm – regarding code and time complexity, as well as numerical stability.

The algorithm

For clipping a set of AABBs against each other, the common sweep line algorithm is employed, in this case sweeping a vertical line from the leftmost box over to the rightmost. Therefore, each box B_i contributes two sweep line events E_l_i and E_r_i to the algorithm, one for its left and one for its right edge. After sorting those events in ascending order, a line is swept horizontally across all boxes:

Each time a box’s left edge is hit by the sweep line, two horizontal edges H_u_i and H_l_i are inserted into a list of currently-active horizontal segments. This list is kept sorted with ascending y values, and every vertical edge event is checked against intersection with all active horizontal edge segments.

At the core of every polygon clipping algorithm, mutual edge intersections need to be computed. Fortunately, as rectangles are convex polygons and free of self-intersections, a lot of the more complicated preprocessing steps involved for generic polygon clipping can be avoided. One of the most notable aspects is the fact that this algorithm is numericable stable also when performing intersection calculations with finite-precision floating-point math, because no precision-reducing operations need to be performed (this is in contrast to general polygon clipping, which gets notoriously instable under floating-point math, since the (sometimes repeated) calculation of intersection points introduces round-off errors – obvious for oblique edges).

For intersection calculations of AABBs, no calculations whatsoever are necessary on the coordinate elements, the resulting intersection vertices are just element-wise merged input coordinates.

Basically, four cases of edge intersections can be distinguished:

Note that, since the sweep line is vertical, it is always a right or a left edge of a rectangle, that needs to be intersected with either an upper or a lower edge. Degenerate cases, such as rectangles with zero height or width, or two exactly identical rectangles, are handled in a defined, but consistent way without affecting the general algorithm.

For each sweep line event (being either a left or a right rectangle edge), all currently active horizontal edge segments are processed, starting with the one with the smallest y value. Each left edge sweep line event creates a polygon, into which intersecting horizontal edges are merged. Therefore, when processing the horizontal edge segments, the sweep line will carry a current polygon P_c. The sweep line’s current polygon may change, naturally, as it intersects horizontal edges, taking up the associated polygon of the intersecting edge and in turn passing the current polygon to that horizontal edge:

For the sake of clarity, I have omitted symmetric cases here, which you get when polygon orientation is reversed (denoting reversed inside and outside areas). Those follow rather straight-forward. A version of the algorithm that handles those cases, and is thus able to perform the usual boolean operations on AABB-defined polygons, is implemented in c++, and used in OpenOffice.org’s graphic subsystem. A standalone version can be found here.