Minimum Convex Decomposition

Enter a vertices of a SIMPLE polygon in CCW order. After clicking Update, a decomposition by diagonals into a minimum number of convex pieces is shown.

Known bugs: The polygon is not checked for simplicity or orientation, so entering a non-simple, or CW oriented polygon will cause strange results and error messages on the Java console. (I think I catch all infinite loops.)

More testing is needed to make sure I got this right in all cases.

You can run minimum weight triangulation or visibility polygon on the same point set. (At least this works in Netscape).

My co-author, Mark Keil, presented "On the time bound for convex decomposition of simple polygons" at the 10th Canadian Conference on Computational Geometry, Aug 1998. The full version of the paper is available. A gzipped tar file with source code is also available for the curious. Code by Jack Snoeyink, University of British Columbia.

Back to Jack's Computational Geometry Demo page.