Instructions

Here are the instructions for my convex hull applet.

Display canvas

Dragging with the left mouse button lets you look at the hull from different directions. If you release the mouse button while dragging the hull will start spinning. You can stop it spinning by clicking on it. Dragging with the middle mouse button (or holding down Meta and dragging) lets you slide the image around, while dragging with the right mouse button (or holding down Alt and dragging) lets you zoom in or out.

The triangle colours have the following meanings:

The checkboxes that appear when you click twice on "More Controls" can be used to make triangles of any particular colour transparent.

Main Menu

Dimension Choice

2D
Show algorithms for two-dimensional convex hull.
3D
Show algorithms for three-dimensional convex hull.

Algorithm Choice

Incremental
Add points to hull one at a time updating the hull as we go.
Gift Wrap
Construct hull one edge (or face) at a time, moving from one edge to an adjacent one.
Divide and Conquer
Divide the points into two equal sized subsets, recursively hull each subset and then merge them together.
QuickHull
A variation on he incremental algoritm where each point is associated with a face that it can see.

Point Distribution Choice

For a 3D hull, you have the following choices for the distribution of the points:
In Sphere
The points are chosen uniformly from inside a sphere.
On Sphere
The points are chosen uniformly from the surface of a sphere. Note that all the points will be vertices of the convex hull.
In Cube
The points are chosen uniformly from inside a cube.
On Paraboloid
The points are chosen on the paraboloid z=x2+y2. This distribution is interesting because the projection of the lower part of the convex hull onto the XY plane is the Delaunay triangulation.
Gaussian
The points are chosen from a three-dimensional Gaussian distribution.
Wedge Block
This is a particular configuration of points from Computational Geometry in C that can cause the divide and conquer algorithm some problems. It has exactly 16 points - unlike the other choices you cannot set a different number of points.
For a 2D hull, you have the following choices for the distribution of the points:
In Circle
The points are chosen uniformly from inside a circle.
On Circle
The points are chosen uniformly from the boundary of a circle. Note that all the points will be vertices of the convex hull.
In Square
The points are chosen uniformly from inside a square.

Points field

This lets you select the number of points to hull.

More Controls button

This lets you display more controls. The first time you click on the button the Animation control menu is displayed, the second time you click on the button the Show menu is displayed, and the third time you click on the button the View menu is displayed.

Animation control menu

To display this menu you must click on the More Controls button.
Start
Start the animation of the currently selected convex hull algorithm.
Stop
Stop the animation of the currently selected convex hull algorithm.
+1
Display the next frame of the animation.
-1
Display the previous frame of the animation.
<<
Display the first frame of the animation.
>>
Display the last frame of the animation
Frame field
You can enter the number of the frame that you want to see here.
Speed control
This lets you control the speed of the animation. Two clicks on the right arrow doubles the speed; two clicks on the left arrow halves it.
Less Controls Button
Lets you hide the extra controls revealed by the More Controls button.

Show menu

The checkboxes lets you control the visibility of objects. If the check box is checked you can see the specified objects. To display this menu you must click twice on the More Controls button.
Normal
Triangles that do not belong to any other category.
Added
Triangles that have been added in the currect frame.
Deleted
Triangles that will be deleted in the next frame.
Axes
The X,Y and Z axes
Points
The points that we are hulling. These are displayed in a layer in front of the hull so that you can see the points inside the hull. If you select 3D algorithms this box is unchecked so that points are invisible. If you select 2D algorithms this box is checked so that points are visible.
Left Hull
Triangles that are part of the left sub-hull in the divide and conquer algorithm.
Right Hull
Triangles that are part of the right sub-hull in the divide and conquer algorithm.
Selected
The triangle selected in the QuickHull algorithm.

View Menu

These buttons let you control the viewing direction for 3D hulls. To display this menu you must click three times on the More Controls button.
Projection
This lets you choose between a perspective projection (objects that are further away are drawn smaller) and an orthographic projection (objects are drawn the same size, no matter how far away they are).
Up z
The view direction is looking up the z axis. With this view direction and points chosen "On Paraboloid", you are looking at an animation of a Delaunay triangulation algorithm.
Down Z
The view direction is looking down the z axis. This view is chosen automatically when you select a "2D" from the dimension choice.
Up Y
The view direction is looking up the y axis.
Down Y
The view direction is looking up the y axis.
Up X
The view direction is looking up the x axis.
Down X
The view direction is looking down the x axis.
Home
Go to the home view. This is the starting view, or the view direction set by the "Set Home" button.
Set Home
Set the home view to be the current view. You can return to this view by pressing the "Home" button.

lambert@cse.unsw.edu.au
Last modified: Fri Sep 25 14:37:59 AET 1998