Vatti clipping algorithm
Encyclopedia
The Vatti clipping
algorithm 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. Even complex (self-intersecting) polygons, and polygons with holes can be processed. This algorithm is generally applicable only in 2D space
.
operations: difference, where the clipping polygons remove overlapping regions from the subject; union, where clipping returns the regions covered by either subject or clip polygons, and; xor, where clipping returns the regions cover by either subject or clip polygons except where they are covered by both subject and clip polygons.
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 sweep line approach divides the problem space by scanlines, imaginary horizontal lines that pass through every vertex of the participating polygons. These scanlines outline scanbeams - the spaces between adjacent scanlines. These scanbeams are processed in turn, starting with the lowest scanbeam, with the algorithm adding points of intersection within these scanbeams into the solution polygons.
Clipping (computer graphics)
Any procedure which identifies that portion of a picture which is either inside or outside a picture is referred to as a clipping algorithm or clipping.The region against which an object is to be clipped is called clipping window.-Examples:...
algorithm is used in computer graphics
Computer graphics
Computer graphics are graphics created using computers and, more generally, the representation and manipulation of image data by a computer with help from specialized software and hardware....
. 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. Even complex (self-intersecting) polygons, and polygons with holes can be processed. This algorithm is generally applicable only in 2D space
2D computer graphics
2D computer graphics is the computer-based generation of digital images—mostly from two-dimensional models and by techniques specific to them...
.
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 clippingBoolean operations on polygons
Boolean operations on polygons are a set of Boolean operations operating on one or more sets of polygons in computer graphics...
operations: difference, where the clipping polygons remove overlapping regions from the subject; union, where clipping returns the regions covered by either subject or clip polygons, and; xor, where clipping returns the regions cover by either subject or clip polygons except where they are covered by both subject and clip polygons.
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 sweep line approach divides the problem space by scanlines, imaginary horizontal lines that pass through every vertex of the participating polygons. These scanlines outline scanbeams - the spaces between adjacent scanlines. These scanbeams are processed in turn, starting with the lowest scanbeam, with the algorithm adding points of intersection within these scanbeams into the solution polygons.
See also
- Sutherland–Hodgman clipping algorithm
- Weiler–Atherton clipping algorithm
- Boolean operations on polygonsBoolean operations on polygonsBoolean operations on polygons are a set of Boolean operations operating on one or more sets of polygons in computer graphics...