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.

• Detail toggles the vertex numbers, edge weights, and canonical triangulation.
• Animate toggles some animation of partial computation (only visibility edges, at the moment)
• Update is the button you push when the input is ready
• Clear All and Delete Last give minimalist editing.

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 zipped file with source code is also available for the curious. Code by Jack Snoeyink, University of North Carolina

Back to Jack's Computational Geometry Demo page.