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:

Red: A triangle that has just been created.
Yellow: A triangle that is about to be deleted.
Blue: The back of any triangle.
Cyan and Magenta: Triangles that belong to the left and right sub-hulls in the Divide and Conquer algorithm.
Cyan: Triangle selected in Quickhull algorithm.
Green: Any other triangle.

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=x²+y². 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 the animation of the currently selected convex hull algorithm.
: Stop the animation of the currently selected convex hull algorithm.
: Display the next frame of the animation.
: Display the previous frame of the animation.
: Display the first frame of the animation.
: Display the last frame of the animation
: You can enter the number of the frame that you want to see here.
: 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.
: 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.

: Triangles that do not belong to any other category.
: Triangles that have been added in the currect frame.
: Triangles that will be deleted in the next frame.
: The X,Y and Z axes
: 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.
: Triangles that are part of the left sub-hull in the divide and conquer algorithm.
: Triangles that are part of the right sub-hull in the divide and conquer algorithm.
: 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.

: 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).
: 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.
: The view direction is looking down the z axis. This view is chosen automatically when you select a "2D" from the dimension choice.
: The view direction is looking up the y axis.
: The view direction is looking up the y axis.
: The view direction is looking up the x axis.
: The view direction is looking down the x axis.
: Go to the home view. This is the starting view, or the view direction set by the "Set Home" button.
: 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