Weiler–Atherton clipping algorithm: Difference between revisions

Revision as of 05:37, 30 March 2017

Latest revision as of 05:51, 4 July 2023

(6 intermediate revisions by 6 users not shown)

Line 1:

{{Short description|Polygon clipping algorithm}}

The '''Weiler–Atherton''' is a polygon-[[Clipping (computer graphics)|clipping]] [[algorithm]]. It is used in areas like [[computer graphics]] and games development where clipping of polygons is needed. It allows clipping of a ''subject or candidate polygon'' by an arbitrarily shaped ''clipping polygon/area/region''.

It is generally applicable only in [[2D computer graphics|2D]]. However, it can be used in [[3D computer graphics|3D]] through visible surface determination and with improved efficiency through [[Z-order]]ing.<ref>Foley, James, Andries van Dam, Steven Feiner, and John Hughes. "Computer Graphics: Principle and Practice". Addison-Wesley Publishing Company. Reading, Massachusetts: 1987. pages 689-693</ref>

== PreludePreconditions ==

[[image:Weiler-Atherton subdivision.svg|thumb|upright=1.2|Subdivision with the Weiler-Atherton algorithm]]

Before being applied to a polygon, the algorithm requires several preconditions to be fulfilled:

Line 11 ⟶ 12:

* The algorithm can support holes (as counter-clockwise polygons wholly inside their parent polygon), but requires additional algorithms to decide which polygons are holes, after which merging of the polygons can be performed using a variant of the algorithm.

== The Algorithm ==

Given polygon A as the clipping region and polygon B as the subject polygon to be clipped, the algorithm consists of the following steps:

# List the vertices of the clipping-region polygon A and those of the subject polygon B.

Line 31 ⟶ 32:

Some polygon combinations may be difficult to resolve, especially when holes are allowed.

Points very close to the edge of the other polygon may be considered as both in and out until their status can be confirmed after all the intersections have been found and verified,; however, this increases the complexity.

Various strategies can be used to improve the speed of this labeling, and to avoid needing to proceed further. Care will be needed where the polygons share an edge.