# 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:

• 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.
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:
• <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