Vatti clipping algorithm

The Vatti clipping algorithm[1] is used in computer graphics.

It allows clipping of any number of arbitrarily shaped 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.

The Vatti algorithm involves processing both subject and clipping polygon edges in an orderly fashion, starting with the lowermost edges and working towards the top; this is conceptually similar to the Bentley–Ottmann algorithm.

This sweep line approach divides the problem space by scanlines, imaginary horizontal lines that pass through every vertex of the participating polygons.