Interactive Applet

The applet requires Java 1.1, available in most modern browsers.

You can manipulate the polygon before executing the algorithm step-by-step, iteration-by-iteration, or all at once. See below for more detailed instructions and the source code.

Start by modifying the polygon to be convex. You can add points by clicking on an edge, and move them by dragging them with the mouse. The shaded area indicates where the selected point can be moved while preserving monotonicity. To undo a modification, use the '<' button. An empty circle represents a point that is colinear with it's neighbors.

After having created the desired polygon, the algorithm can be executed step-by-step, iteration by iteration or all at once, with the '>', '>>' and '>>|' buttons respectively. The polygon can still be modified at any point during execution of the algorithm.

The '+', '-' and 'Fit' buttons can be used zoom the polygon.

Finally, to start again with the initial quadrangle, use the 'Reset' button.

The source code is available here. Some of the parts directly relating to the algorithm are less-that-perfectly documented, but I tried to create a reusable structure for writing an animated applet which is commented and should be easily understood. See the README file for details.