This applet demonstrates the Algorithm of Minimal Convex Polygon Decomposition.
The Algorithm uses a Dynamic Programming approach to the problem. We minimally decompose sub-polygons of our polygon and then try to merge the smaller decompositions to form a decomposition of the bigger polygon.

The Algorithm runs in O( N² n log n ) time, where n is the total number of vertices and N is the number of notches.


The demo won't let you create intersections by mistake, and will adjust your polygon to be clockwise if it's not (The algorithm requires the points to be clockwise on it's boundary).

The Algorithm, in short:


Preprocessing: DP Procedure (for each valid subpolygon in the order computed before): The last subpolygon that will be considered in the DP Procedure will be the original polygon (subpolygon (0,n-1)).
Any one of the MDs in it's MD sets is a solution to our original problem of finding a Minimal Convex Decomposition.