Weiler–Atherton clipping algorithm: Difference between revisions

Revision as of 23:31, 6 January 2007

Revision as of 16:38, 21 January 2007

Line 1:

{{Cleanup|January 2006}}

'''Weiler-Atherton''' [[clipping]] algorithm used in [[Computer graphics]].

It allows clipping of a ''subject polygon'' by an arbitrarily shaped ''clip polygon''. It is generally applicable only in [[2D]].

'''== Draft Description''' ==

It allows clipping of a ''subject polygon'' by an arbitrarily shaped ''clip polygon''.

It is generally applicable only in 2D.

'''Draft Description'''

Requires polygons to be clockwise and not re-enterant (self intersecting)

Line 19 ⟶ 14:

If there are no intersections then one of three situations exist:

2)#1 BA is inside AB - return BA for clipping, AB for merging.

1)#2 AB is inside BA - return AB for clipping, BA for merging.

#3) A and B do not overlap - return None for clipping or A & B for merging.

2) B is inside A - return B for clipping, A for merging.

3) A and B do not overlap - return None for clipping or A & B for merging.

A list of inbound intersections is then generated. Each intersection in the list is then followed clockwise around the linked lists until the start position is found. One or more concave polygons may produce more than one intersecting polygon. Convex polygons will only have one intersecting polygon.

Line 34 ⟶ 26:

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

== References ==

*See HIDDEN SURFACE REMOVAL USING POLYGON AREA SORTING - Kevin Weiler and Peter Atherton [http://www.cs.drexel.edu/~david/Classes/CS430/HWs/p214-weiler.pdf]

*[1] http://www.cs.drexel.edu/~david/Classes/CS430/HWs/p214-weiler.pdf