Poly Decomp


Poly Decomp is a set of algorithms used for decomposing polygons into convex regions, and is written in C++. Given a simple polygon P, the goal is to divide P into a minimal number of convex regions as quickly as possible. Unfortunately, there is a trade off between speed and optimality, so I have written two programs. My implementation of Keil's algorithm is slow (O(n4)), but optimal, whereas my custom solution is much faster (O(n4)), but not optimal in all cases.