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. 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. 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.

gollark: Can you still feel other pain-related things like pressure, temperature, water, etc?
gollark: Memetics.
gollark: Look it up elsewhere?
gollark: Which probably implies interesting things of some sort.
gollark: I did read that while different languages have different syllable rates and different amounts of information per syllable, they all have very similar information transmission rates.

See also

References
  1. Bala R. Vatti. "A generic solution to polygon clipping", Communications of the ACM, Vol 35, Issue 7 (July 1992) pp. 56–63.


This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.