Weiler–Atherton clipping algorithm: Difference between revisions

Revision as of 18:34, 23 July 2015

Revision as of 18:38, 23 July 2015

Line 5:

== Description ==

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

TheBefore applying to any polygon, the algorithm requires several preconditions to be fulfilled.

- Candidate polygons need to to be oriented clockwise.

- andCandidate polygons should not reentrantbe (self intersecting (i.e. re-entrant).

- The algorithm can support holes (as counter-clockwise polygons wholly inside their parent polygon), but requires additional algorithms to decide which polygons are holes.

Merging of polygons can also be performed by a variant of the algorithm.

Two lists are created from the coordinates of each polygons A and B, where A is the clip region and B is the polygon to be clipped.

Line 11 ⟶ 19:

The list entries are labelled as either inside or outside the other polygon. Various strategies can be used to improve the speed of this labelling, and to avoid needing to proceed further.

All the polygon intersections are then found and are inserted into both lists, linking the lists at the intersections. Care will be needed where the polygonspolygandidate ons share an edge.

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