Vatti clipping algorithm

The Vatti clipping algorithm is used in computer graphics. It allows clipping of any number of subject polygons by any number of arbitrarily shaped clip polygons. Unlike the Sutherland–Hodgman and Weiler–Atherton polygon clipping algorithms, the Vatti algorithm does not restrict the types of polygons that can be used as subjects or clips. Even complex (self-intersecting) polygons, and polygons with holes can be processed. This algorithm is generally applicable only in 2D space.

Description

Clipping is defined as the interaction of subject and clip polygons. While clipping usually involves finding the intersections (or regions of overlap) of subject and clip polygons, clipping algorithms can also be applied to the other boolean clipping operations: difference, where the clipping polygons remove overlapping regions from the subject; union, where clipping returns the regions covered by either polygon, and; xor, where clipping returns the regions cover by either polygon except where they are covered by both subject and clipping polygons.

The Vatti algorithm works by processing all edges, from both the subject and clipping polygons, in an orderly fashion starting with the the lowermost edges and working towards the top. The problem space is divided by horizontal lines passing through all the vertices of the participating polygons. These lines make up scanbeams (ie the spaces between adjacent horizontal lines). These scanbeams are processed in turn, starting with the lowest scanbeam. As each scanbeam is processed, the algorithm adds points of edge intersections into the solution polygons.

See also

• Sutherland–Hodgman clipping algorithm
• Weiler–Atherton clipping algorithm
• Boolean operations on polygons

External Links

• Clipper, an open-source freeware implementation of the Vatti algorithm
• General Polygon Clipper, another implementation of the Vatti algorithm