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:
|
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. |
Performance 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):
- Find the lowest three points.
- Consider the plane that intersects these points. Assume, for now, that it is not a
perfectly vertical plane.
- Search through all remaining points to find any points that are below this plane.
- 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.
- 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).
- 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:
- Pick any three points for the starting plane.
- Pick another point. You now have your hypothetical convex hull.
- 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.
- If a point is not found, then we're done!
- 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.
- Repeat step 3.
|
|