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:
The information can be interpreted as follows:
|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.
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