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.
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
starshaped 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 stepbystep. 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 illbehaved 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.
Main Page
 Abstract
 Introduction
 Algorithm
 Results
 Applet
 References
 Comments