Characterizing and Efficiently Computing Quadrangulations of Planar Point Sets 

Demonstration Java Applet

This Java Applet demonstrates computing a quadrangulation of a set of input points specified by the user.  Click on the button below to bring up the applet.  Instructions on using the applet follow.

Your browser doesn't understand the <APPLET> tag. Here's a picture of the window you'd see if you were using a Java-compatible browser:


Steps of the algorithm

For a more mathematical description of the steps taken in realizing this algorithm, please see the accompanying web page, or the paper itself.

Here is a description of the steps taken in the algorithm, that you will see while running the Java Applet:


The applet works in two modes:

        1) Entering input points
        2) Observing the computation of the algorithm

To exit the applet, click on menu "File" -> "Exit".

Mode "Entering input points"

Clicking on the canvas allows the user to enter some input points directly. Furthermore, points can be generated automatically by the commands in the "Points" menu.  You can generate either a Uniform, Gaussian or (approximate) Poisson distribution of 25 or 100 points.

The "Clear" button in the toolbar on the left allows you to remove all the inputs points on the canvas.  This command is also available in the "File" menu.

Mode "Observing the computation"

In this mode, the user doesn't change the input points and observes each step of the algorithm.  Pressing the "Start" button (which then becomes a "Next" button) begins executing the algorithm step-by-step.  The current step that has been accomplished is shown in the message area at the bottom of the window. Pressing the "End" button allows one to interrupt completion of the algorithm and to modify ill-behaved points at any stage of the algorithm.  The "Clear Edges" command in the "File" menu allows you to clear any constructed edges in the triangulation without removing the points.

Other Functions

Other functions are provided, because they were implemented as part of doing the algorithm.  Those are found in the "Functions" menu. Again, the edges thus created can be cleared by using the "File" -> "Clear Edges" menu entry.


Main Page | Abstract | Introduction | Algorithm | Results | Applet | References | Comments