CPSC 653 project page


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:

Note: The code can be also run as an application which can optionally read data from an input file. This input file can be specified on the command line. The format of the input file is:


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