The Vatti clipping algorithm
[Bala R. Vatti]
"A generic solution to polygon clipping"
Communications of the ACM, Vol 35, Issue 7 (July 1992) pp. 56–63. is used in
computer graphics
Computer graphics deals with generating images with the aid of computers. Today, computer graphics is a core technology in digital photography, film, video games, cell phone and computer displays, and many specialized applications. A great de ...
. It allows
clipping
Clipping may refer to:
Words
* Clipping (morphology), the formation of a new word by shortening it, e.g. "ad" from "advertisement"
* Clipping (phonetics), shortening the articulation of a speech sound, usually a vowel
* Clipping (publications) ...
of any number of arbitrarily shaped ''subject
polygon
In geometry, a polygon () is a plane figure that is described by a finite number of straight line segments connected to form a closed ''polygonal chain'' (or ''polygonal circuit''). The bounded plane region, the bounding circuit, or the two to ...
s'' 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. The 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 (regions of overlap) of subject and clip polygons, clipping algorithms can also be applied with other
boolean clipping 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 covered 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 is conceptually similar to the
Bentley–Ottmann algorithm In computational geometry, the Bentley–Ottmann algorithm is a sweep line algorithm for listing all ''crossings'' in a set of line segments, i.e. it finds the ''intersection points'' (or, simply, ''intersections'') of line segments. It extends the ...
. This
sweep line
In computational geometry, a sweep line algorithm or plane sweep algorithm is an algorithmic paradigm that uses a conceptual ''sweep line'' or ''sweep surface'' to solve various problems in Euclidean space. It is one of the key techniques in compu ...
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
*
Martinez-Rueda_clipping_algorithm
*
Greiner–Hormann clipping algorithm The Greiner-Hormann algorithm is used in computer graphics for polygon clipping. It performs better than the Vatti clipping algorithm, but cannot handle degeneracies. It can process both self-intersecting and non-convex polygons. It can be triviall ...
*
Sutherland–Hodgman clipping algorithm
*
Weiler–Atherton clipping algorithm
*
Boolean operations on polygons
References
External links
Clipper, an open-source freeware implementation of the Vatti algorithm
Polygon clipping algorithms
{{compu-graphics-stub