Introduction

Due to the many applications, breaking down a non-convex polygon into simpler subsets has been a recurring theme in the literature. For instance, it is of great interest in object representation since complex geometric structures are more easily handled when decomposed into simpler structures.

Other examples are pattern recognition, database systems and graphics. In this assignment, we implement an algorithm for dividing polygons into convex polygons without adding additional vertices as well as a method that can be used to eliminate extra edges from any division.

---

About the algorithm

The procedure MP1 is used to partition a simple polygon into convex polygons. The vertices of the next convex polygon are stored in a list and the polygon is generated by adding consecutive adjacent vertices of the polygon to the list, removing some if necessary, and drawing the diagonal between the first and last vertices. The procedure stops when all vertices of the polygon are in the list or a vertex fails to meet certain conditions.

The final partition consists of all convex polygons generated except for the diagonal edges that are not considered polygons. To save time, a method is needed to check if vertices of the polygon are inside the convex polygon generated by the diagonal. If a notch is found to be inside the polygon generated by L, vertices are removed until no notch is inside the polygon. If L has more than two vertices, it generates one of the polygons of the partition. The process is repeated until all vertices of P are in L or a vertex fails a condition.