Content deleted Content added
No edit summary |
Added book publication date |
||
| (4 intermediate revisions by 3 users not shown) | |||
Line 1:
{{Short description|Algorithm for clipping polygons}}
The '''Sutherland–Hodgman algorithm''' is an [[algorithm]] used for [[Clipping (computer graphics)|clipping]] [[polygon]]s. It works by extending each line of the [[convex polygon|convex]] ''clip polygon'' in turn and selecting only vertices from the ''subject polygon'' that are on the visible side.
Line 41 ⟶ 42:
The vertices of the clipped polygon are to be found in ''outputList'' when the algorithm terminates. Note that a point is defined as being ''inside'' an edge if it lies on the same side of the edge as the remainder of the polygon. If the vertices of the clip polygon are consistently listed in a counter-clockwise direction, then this is equivalent to testing whether the point lies to the left of the line (left means ''inside'', while right means ''outside''), and can be implemented simply by using a [[cross product]].
''ComputeIntersection'' is a function, omitted here for clarity, which returns the intersection of a line segment and an infinite edge. Note that
==Implementations==
A Python implementation of the Sutherland-Hodgman can be found [https://github.com/mdabdk/sutherland-hodgman here].
==See also==
Line 53 ⟶ 58:
== References==
* Mel Slater, Anthony Steed, Yiorgos Chrysanthou: ''Computer Graphics and Virtual Environments: From Realism to Real-Time.'' Addison Wesley, 2002. {{ISBN|0-201-62420-6}}.
* [[Ivan Sutherland]], Gary W. Hodgman: ''Reentrant Polygon Clipping.'' [[Communications of the ACM]], vol. 17, pp. 32–42, 1974
| |||