**Sutherland-Hodgeman Polygon Clipping Algorithm**

**Sutherland-Hodgeman Polygon Clipping Algorithm:** This algorithm was purposed by Sutherland and Hodgeman in 1974 to determine which portions of the polygon were visible within a window and clipping out the portions that are outside the window.

This algorithm accepts as input a series of polygon vertices, V_{1}, V_{2}, …. V_{n}. These vertices define polygon edges from V_{i}, to V_{i+1} and from V_{n} to V_{1}.

The algorithm clips a polygon by processing the polygon boundary as a whole against each window edge. It means all the vertices are processed for clipping against** each individual clip boundary** of clipping window one by one.

It means starting with the initial set of vertices, the polygon is first clipped against left window boundary and a new set of vertices is produced.

This set is given as input to next clipping boundary and the polygon is clipped against right clipping boundary to produce a new set of vertices and is then clipped against bottom and top clipping boundary to produce final set of vertices . **[Left-Right-Bottom-Top]**

Thus, at each step a new set of output vertices is generated and is passed to the next window boundary clipper.

When all the vertices of a given polygon are processed against any clipping side, there could be any one of the following four possibilities for a successive pair of two vertices of polygon:

### Case 1: out → in :

If the starting vertex is outside the window boundary and ending vertex is inside then we preserve or save both point of intersection of polygon edge with window boundary and ending vertex in the output vertex list.

**Case 2 : in → in :**

If both the starting and ending vertices are inside the window boundary then only the ending vertex is preserved or saved in output vertex list.

**Case 3: in → out :**

If the starting vertex is inside the window and ending vertex is outside then only the point of intersection of polygon edge with window boundary is saved in output list.

**Case 4: out → out :**

If both the starting and ending vertices are outside the window boundary then nothing is added or saved in the output vertex list.

Case |
Output |

Out → In | A’ B [2 Vertices, Point of intersect with window and ending edge] |

In → In | C [1 ending vertex ] |

In → Out | D’ [Point of intersect with window] |

Out → Out | N/A [Nothing is included] |

### Example of Sutherland-Hodgeman Polygon Clipping Algorithm

Let us consider a polygon with vertices P1, P2, P3, P4, P5. Inside in a viewing window. Applying Sutherland-Hodgeman Polygon Clipping Algorithm on this polygon, we get:

**Clipping polygon engaged left window boundary:**

Here the input vertex list is P1, P2, P3, P4 P5 and the edges are P1P2, P2P3, P3P4, P4P5 and P5P1. Now, consider all the edge with respect to (w.r.t.) left window boundary.

Edge |
Type |
Output |

P1P2 | Out → In | P1’P2 |

P2P3 | In → In | P3 |

P3P4 | In → In | P4 |

P4P5 | In → In | P5 |

P5P1 | In → Out | P5′ |

**Clipping polygon engaged right window boundary:**

Here the input vertex list is P1′, P2, P3, P4, P5, P5′ and the edges are P1’P2, P2P3, P3P4, P4P5, P5P5′ and P5’P1′. Now, consider all the edge with respect to (w.r.t.) right window boundary. There will be **no changes** because all edges lies inside the right clipping window.

Edge |
Type |
Output |

P1’P2 | In → In | ‘P2 |

P2P3 | In → In | P3 |

P3P4 | In → In | P4 |

P4P5 | In → In | P5 |

P5P5′ | In → In | P5′ |

P5’P1′ | In → In | P1′ |

**Clipping polygon engaged bottom window boundary:**

Here the input vertex list is P1′, P2, P3, P4, P5, P5′ and the edges are P1’P2, P2P3, P3P4, P4P5 and P5P5′. Now, consider all the edge with respect to (w.r.t.) bottom window boundary.

Edge |
Type |
Output |

P1’P2 | In → In | P2 |

P2P3 | In → In | P3 |

P3P4 | In → In | P4 |

P4P5 | In → Out | P4′ |

P5P5′ | Out → Out | N/A |

P5’P1′ | Out → In | P5” |

**Clipping polygon engaged top window boundary:**

Here the input vertex list is P1′, P2, P3, P4, P4′, P5” and the edges are P1’P2, P2P3, P3P4, P4P4′, P4’P5” and P5”P1. Now, consider all the edge with respect to (w.r.t.) top window boundary. Here the input vertex list is P1′, P2, P3, P4, P5, P5′ and the edges are P1’P2, P2P3, P3P4, P4P5, P5P5′ and P5’P1′. Now, consider all the edge with respect to (w.r.t.) right window boundary. There will be **no changes** because all edges lies inside the top clipping window.

Edge |
Type |
Output |

P1’P2 | In → In | P2 |

P2P3 | In → In | P3 |

P3P4 | In → In | P4 |

P4P4′ | In → In | P4′ |

P4’P5” | In → In | P5” |

P5”P1′ | In → In | P1′ |

**Final output using Sutherland-Hodgeman Polygon Clipping Algorithm will be:**

### Limitations of Sutherland-Hodgeman Polygon Clipping Algorithm

- In some concave polygons, the theorem creates extra edges while clipping.

#### Related posts:-

[su_posts template=”templates/list-loop.php” posts_per_page=”3″ taxonomy=”link_category” tax_operator=”NOT IN” order=” desc”]