Sutherland-Hodgeman algorithm for clipping polygon


Applet Sutherland-Hodgeman algorithm for clipping polygon Authors: Marek Sivčo and Michal Stanko

Specification of applet

This applet was created for course Webovská grafika (Web Graphics). Applet should implement Sutherland-Hodgeman algorithm for clipping polgyon according to rectangle.

Definition of project:

Sutherland-Hodgeman Polygon Clipping

  • Create a polygon using mouse clicked points
  • Choose a rectangular window area to clip the polygon
  • Demonstrate algorithm functionality

Algorithm is based on in clipping of polygon step by step in four phases. It clippes according to given rectangle, always from one side at the time.

Algorithm is as follows:

In i-iteration we take i and i+1 point of (not yet clipped) polygon.
Always according to one co-ordinate of clipping area may 4 cases occur:

  • Case 1: points i and i+1 are outside of clipping area. Then no point is written.
  • Case 2: points i and i+1 are inside. Write point "i" into points of new (clipped) polygon.
  • Case 3: point "i" is is inside, i+1 is outside. Write point "i" into points of clipped polygon and calculate intersection of segment (i,i+1) with clipping line of clipping side and write this intersection into points of new polygon.
  • Case 4: "i" is is outside, i+1 is inside, again calculate intersection and write only him to points of new polygon.

We repeat these steps for entire sequence of points according to every side of clipping area (rectangle). After end of loop, we overwrite original sequence of points of polygon with new (clipped) sequence of points of polygon. When algorithm ends polygon is clipped.

This algorithm is used in this applet. Selection of what polygon side will be clipped at first is up to user. Functionality and result of algorithm is not depending on side from which is polygon clipped.

Two persons work on this project. Me (Marek Sivčo) and Michal Stanko. Link to site of my colleague:

Source code