Convex Hull Honors Project

By Walton Dell for CSE310 Spring Semester 99
Uploaded: April 19, 1999
Last Updated: June 25, 2006

In computer graphics, it is often useful to find the minimum convex shape that will enclose a set of points.  This is called a convex hull.  A convex shape is one in which all internal angles are less than 180 degrees.  Below, I demonstrate two algorithms that find the convex hull of a set of points.

Click within each box to add points, click the title bar to clear all the points:

Sorry, your web browser does not support running Java programs.

The first number displayed is the number of points (shown in yellow).  The second number (in green) is a very approximate number of operations. If you always multiply ops by some constant, it will represent the maximum operations performed.  The best constant to use is difficult to calculate.  Note: For Graham's Scan, ops is dependant on the type of sort used to sort the points.  In this case, I used the heapsort algorithm.
Graham's Scan

This algorithm starts by finding the lowest point.  If there are two points at the lowest position, the leftmost point of these two is used.  The lowest point is colored red in my program.  Next, all the remaining points are sorted by their polar angle with respect to the low point and the x-axis.   The algorithm then goes counter-clockwise connecting points "around the circle", but if it has to make a right turn, then it backs up and skips that point.

The result (in white) is a convex hull.  The blue lines in this program connect the points in their (polar angle) sorted order (displayed for learning purposes).

Jarvis's March

This algorithm builds the convex hull in two parts.  As with Graham's Scan, this algorithm starts by finding the lowest point (shown in red), and it builds the convex hull counter-clockwise.  This algorithm, though, also finds the highest point (shown in pink).  It starts at the bottom.  To build the right chain, the algorithm searches for the unused point with the minimum polar angle relative to the current position (and that becomes the current position).  It continues like this until it reaches the highest point.  Then the strategy is only slightly modified to build the left chain.  From then on, it will search for the unused point with the minimum polar angle from the negative x-axis.

The result (in white) is the same as with Graham's Scan.  The blue lines in this program simply connect the set of unused points (displayed for learning purposes).

Tricky Angles

One thing you have to keep in mind when calculating the polar angles needed by both algorithms is that the coordinate system on a computer screen is upside-down.  The y-axis starts at 0 at the top of the screen, and increases as you go down the screen.  This can be fixed by consistently using (Y_MAX - y) in place of y.  I have also discovered that Java has a feature that will do this for you.

Another thing to take note of is that the Java atan2 function (arctanget) is not the same as the arctan button on your calculator.  On the calculator, if you calculate arctan(-.25), the calculator has no way of knowing if this is (-1 / 4) or (1 / -4), and therefore it will not know if the resulting angle is in the bottom-right quadrant or the top-left quadrant, respectively.  (It will assume a positive x quadrant.)  The Java atan2 function, however, takes individual parameters for the opposite (y) and adjacent (x) sides of the triangle.  Thus, the atan2 function can return a full 360 degree (2 PI) range of angles.


Let n = the number of points  and   h = the number of vertices of the convex hull

The running time of Jarvis's March is O(nh)
The running time of Graham's Scan is O(n lg n)

Thus, if there are a sufficiently great number of points relative to the number of vertices, then Jarvis's March will have greater performance than Graham's Scan (imagine a triangle filled with hundreds of points).  The running time of Graham's Scan will vary depending on how easy it is to sort the points (some sets of points may be very scrambled).

Additional Thoughts -- Finding the 3D Convex Hull of a Set of 3D Points

Here is my attempt at solving this problem (at this point I have done no 3D programming, although I'd like to in the future):

  1. Find the lowest three points.
  2. Consider the plane that intersects these points.  Assume, for now, that it is not a perfectly vertical plane.
  3. Search through all remaining points to find any points that are below this plane.
  4. If a point is found, try swapping it with each of our three points until a plane is formed that is below the swapped point. Now repeat step 3.  This is like hinging the plane on two points and swinging it toward the lower point.  As the plane "rotates", the low side may pass through some point, which will then be lower than the plane, but I believe by repeating step 3, the "lowest" plane will eventually be found.
    Once no point is found that is below our plane, we know our three points are part of the convex hull, because the rest of the object is above (and perhaps to the side of) the plane formed by our three points.
  5. Now take two of the three points (dropping one), and "hinge" a plane on these two points.  Search for an unused point that (with the "hinge") creates a plane for which all points are on one side of the plane (including the dropped point).
  6. Repeat step five until all hull points are found (how to do this is yet to be determined).

I'm sure some trig would be necessary to efficiently do the steps above, but I'm not even sure if the steps are correct.

I have another totally different strategy, but I don't think it works:

  1. Pick any three points for the starting plane.
  2. Pick another point.  You now have your hypothetical convex hull.
  3. Search for a point that is not "inside" the hypothetical hull.  I don't know how to calculate "inside".  I think that calculating "inside" means determining a convex hull, in which case this method would not work.
  4. If a point is not found, then we're done!
  5. If a point is found, "balloon" (expand) the convex hull to include this point, and check to see if any of the current hull points were "eaten" and are no longer hull points.
  6. Repeat step 3.


Copyright 1999 by Walton Dell Home Page Walton Dell's Software School Projects by Walton Dell Computer Support (Tutorials and more!) Glossary of computer terminology Music Video Games Fun Stuff Humor Links to other web sites Search or the entire web! Contact Walton Dell
Web Site: