The applet presented
on this page is an implementation of an algorithm described by H. Ratschek
and J. Rokne in a paper
*Exact and Optimal Convex
Hulls in 2D*. This
algorithm computes the convex hull of a finite set of points. It is based
on a version of Graham Scan where all computations are rounding-error free
and therefore the computed convex hull is exact. Here is the applet:

Help:
Click the mouse in the window to add new points. The Clear points button will erase all existing points. The Show stairs toggle toggles viewing of stairs. Show hull toggles viewing of the convex hull. |

I have introduced
two modifications in my implementation to deal with *pathological*
cases:

- When computing points in a given rectangle, only points to the right of the diagonal defining the rectangle are considered. This guarantees that the contents of the rectangles do not overlap. The test is performed using a LEFT-TURN test. If the contents of the 4 rectangles are allowed to overlap, in some cases it could result in decomposing the convex hull right after it is built in step #3 of Graham Scan. E.g. consider the following example:

- The third step is modified slightly: since we don't know for sure which two points will be on the convex hull after the stairs are constructed, only one point is put on the stack. Then the rule for the while loop is modiffied as folows: if there is only one point on the stack, always add the new point onto the stack. If there are more than one point on the stack the while loop remains unmodified.

- <n = number of points>
- <x1> <y1>
- <x2> <y2>
- ...
- <xn> <yn>

The sources can
be downloaded here: convexHull.jar
or viewed here: list
of sources

The documentation
can be found here in html format (created using javadoc): documentation