Weiler–Atherton clipping algorithm: Difference between revisions

Revision as of 19:24, 23 July 2015

Revision as of 20:12, 23 July 2015

Line 26:

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

== Conclusion ==
One or more concave polygons may produce more than one intersecting polygon. Convex polygons will only have one intersecting polygon.

The same algorithm can be used for merging two polygons by starting at the outbound intersections rather than the inbound ones. However this can produce counter-clockwise holes.

Line 34 ⟶ 37:

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.

== Conclusion ==

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.