Main Page

Applet

Instructions

This applet implements the simple shape from probing algorithm described previously. This algorithm requires at most 3n+1 probes to discover the shape of a convex n-gon. The applet is simple to use:

Click on the plane to extend the shape. The shape is the convex hull of all the points entered by the user. Clicks are ignored if too close to existing vertices.
Alternatively click on the "select an example..." drop-down list to select a predefined shape.
Click on the "Probe" button to show the next probe of the algorithm. The shape can no longer be extended after probing has started. The "Probe" button is disabled when the shape has been found.
Click on the "Clear" button at any time to reset the applet.

The information can be interpreted as follows:

Blue lines:	Probes.
Green polygon:	Current hull H.
Gray polygon:	Shape S.
Red, hollow dots:	Contact points.
Red, filled dots:	Verified vertices.
Red lines:	Fully-verified edges.
Black lines:	Semi-verified edges.
Yellow wedge:	Wedge of the next probe. The internal gray line indicates the orientation of the next probe. (This wedge usually hides the gray shape under it.)

This notation is very similar to the one shown here. For an applet respecting more closely those conventions, take a look at the Java 2 version of this applet (Java 2 plug-in required).

The applet seems to be stable but it occasionally behaves incorrectly. The main difficulty in the implementation of this algorithm is the limited precision of all numerical computations. The contact point, for example, is never computed exactly at the apex of the wedge even though it should be.

Acknowledgements

The implementation of the convex hull algorithm was taken from Jason C. Yang's applet. Another applet (available here) was used as a template after being stripped down to its essential components. Many thanks also to Matt Holly for taking the time to hunt down the source code for his applet.

Lower Bound of 3n-1

Conclusion