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.
Buttons
-
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.
-
Clear: Draw a new polygon.
-
Restart: Reset the Algorithm.
-
Step: Single-step through the algorithm.
-
Go: Run the algorithm. You can pause the execution during the run
with the "Pause" button.
-
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.
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:
Definitions:
-
reference vertex - a vertex which is either a notch or the first/last
vertex.
-
valid subpolygon (i,j) - a polygon which contains the vertices (i,i+1,...,j-1,j)
where at least one of i,j is a reference vertex.
-
base triangle (of a subpolygon (i,j)) - a triangle with vertices
(i,m,j) where each of (i,m),(m,j) is either a base edge of a valid subpolygon
or an original side of the polygon.
Preprocessing:
-
Determine which vertices are reference vertices.
-
Find visibility pairs which define valid subpolygons.
-
Sort the visibility pairs (i,j) in ascending order of the size measure
j-i.
-
For each valid subpolygon form the set of base triangles.
DP Procedure (for each valid subpolygon in the order computed before):
-
Construct Sets of MDs (Minimal Decompositions) for this subpolygon, group d
and sorted by their ability to merge with base triangles of a larger subpolygon.
-
This is done by considering each base triangle (i,m,j) of the current subpolygon,
and trying to merge it from the left or from the right with MDs of the
subpolygons (i,m) and (m,j) respectively.
-
Remove unnecessary MDs from the sets constructed above, to improve efficiency.
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.
