Convex Hull Honors Project

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

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).

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).

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).

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.