Content deleted Content added
No edit summary |
m Open access bot: doi added to citation with #oabot. |
||
| (3 intermediate revisions by 2 users not shown) | |||
Line 8:
| title = Efficient clipping of arbitrary polygons
| journal = ACM Transactions on Graphics
| year = 1998
|
| doi-access = free
}}</ref> It performs better than the [[Vatti clipping algorithm]], but cannot handle [[Degeneracy (mathematics)|degeneracies]].<ref>{{Cite web
| title = Efficient Clipping of Arbitrary Polygons
Line 18:
}}</ref> It can process both self-intersecting and non-convex polygons. It can be trivially generalized to compute other [[Boolean operations on polygons]], such as union and difference.
The algorithm is based on the definition of the "inside" of a polygon based on the [[winding number]]. It considers regions with odd winding number to be inside the polygon; this is known as the [[even–odd rule]]. It takes two lists of polygons as input
In its original form, the algorithm is divided into three phases:
| |||