Source code online books for professionals by professionals

Figure 6-8.  A set of points and their convex hull
Figure 6-9.  Combining two smaller convex hull by finding upper and lower common tangents (dashed)
By now, I’m sure you’re suspecting how we’ll be solving this: Divide the point set into two equal halves along 
the x-axis and solve them recursively. The only part remaining is the linear-time combination of the two solutions. 
Figure 
6-9
 hints at what we need: We must find the upper and lower common tangents. (That they’re tangents basically 
means that the angles they form with the preceding and following line segments should curve inward.)
14
A region is convex if you can draw a line between any two points inside it, and the line stays inside the region.

---

Chapter 6 
■
 DiviDe, Combine, anD Conquer
130
Without going into implementation details, assume that you can check whether a line is an upper tangent for 
either half. (The lower part works in a similar manner.) You can then start with the rightmost point of the left half and 
the leftmost point of the right half. As long as the line between your points is not an upper tangent for the left part, you 
move to the next point along the subhull, counterclockwise. Then you do the same for the right half. You may have to 
do this more than once. Once the top is fixed, you repeat the procedure for the lower tangent. Finally, you remove the 
line segments that now fall between the tangents, and you’re done.