Home Bookmarks Papers Blog

Minimal Convex Polygon Decomposition Demo

By: Ofer Belinsky


The problem

Given a simple polygon in the plane, one would like to decompose it into a minimal number of convex polygons. Why? There are problmes where the first stage is to break a polygon into convex parts. For example, if your polygon represents an art gallery, then you can put one gaurd inside each convex polygon to gaurd the whole convex regions. A minimal number of convex polygons in your decomposition impolies that you need less gaurds for the polygon.

This applet demonstrates the Algorithm of Minimal Convex Polygon Decomposition.
It is based on the article "Decomposing a Polygon into Simpler Components" by J.M.~Keil.

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 Applet


How to use this demo:

Draw a polygon by clicking the mouse in the applet area several times.
When you want to close the polygon, click near the first point.
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).

Click the "Clear" button to draw a new polygon.
Click the "Restart" button to reset the Algorithm.

Set the "Detail" checkbox if you want a detailed execution, or clear the box for a quick & simple demonstration.
The Detailed execution shows:
- In the PreProcessing stage: all the Visibility pairs which define valid subpolygons.
- In the DP Procedure stage: the base triangles - checking and merging with sub-MDs if possible.

Click the "Step" button to single-step through the algorithm.
Click the "Go" button to run the algorithm. You can pause the execution during the run with the "Pause" button.

The Algorithm, in short:

Definitions:

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.
 

Links

Another applet that demonstrates decomposition into convex polygons is found here. It is based on a recent paper by Keil and Snoeyink.

Source Code

The complete applet

Back to the Workshop home page