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:

Instructions

Algorithm
Functionality

Mode "Entering input points"
Mode "Observing the computation"

Other functions
Help

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:

Step 1: Validating the input vertices for general position
Step 2: Computing a spiral polygonal chain by using the rotating calipers method.
Step 3: Closing the polygonal chain at the starting end of it.
Step 4: Determining a center/inner star-shaped region and triangulating it.
Step 5: Triangulating the spiral from the inner polygon towards the outer part of the spiral.
Step 6: Removing one out of 2 diagonals from the center to obtain quadrilaterals.
Step 7: Optionnally adding a Steiner point to complete the last polygon of the chain, which may be a triangle at that point.
(Step 8): The quadrangulation is complete.

Functionality

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.

Button 1 : Enter new points OR move existing point (drag)
Button 2 : Delete a point
Button 3 : Delete a rectangle of points (note that the rectangle may not be drawn here)

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.

Compute the convex hull of the set of input points.
Compute the spiral of the set of input points.

Again, the edges thus created can be cleared by using the "File" -> "Clear Edges" menu entry.

Help

The "Help" -> "Manual" menu brings up this help file.
The "Help" -> "About" menu brings up an about dialog box.