Vatti clipping algorithm

The Vatti clipping algorithm is a method from computer graphics for clipping polygons, which means finding where one set of polygons overlaps, or is otherwise combined with, another set. It was proposed by Bala R. Vatti, who worked at Calcomp and Hewlett-Packard, in a 1992 paper in the Communications of the ACM. Its main distinction is generality: it accepts any number of arbitrarily shaped subject polygons and any number of arbitrarily shaped clip polygons, including self-intersecting polygons and polygons with holes, which the older Sutherland-Hodgman and Weiler-Atherton algorithms do not allow. Besides intersection it supports the boolean operations of difference, union and xor. It works by sweeping upward from the lowest edges, with imaginary horizontal scanlines through every vertex dividing the plane into scanbeams that are processed in turn, an approach conceptually similar to the Bentley-Ottmann algorithm. The algorithm applies generally only in two dimensions.