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