# Convex Hull Scan

To develop an efficient algorithm for computing the convex hull (whose fact sheet appears in Figure 9-7) for a set of points P, we could choose an iterative approach, as shown in Figure 9-8. To determine the next point in the hull, compute the smallest angular difference formed by all non-hull points with an infinite ray determined by the last two discovered hull points. When the partial convex hull contains h points, the angles must be computed for n-h points to determine the next point; this approach is unable to prune away wasted computations that will clearly not be needed.

Andrew's Convex Hull Scan divides the problem into two parts—constructing the partial upper hull and the partial lower hull. First, all points are sorted by their x coordinate (breaking ties by considering the y). Note that the points in Figure 9-8 are already numbered from left to right along the x axis. The partial upper hull starts with the leftmost twopoints in P. Convex Hull Scan extends the partial upper hull by finding the point p in P whose x coordinate comes next in sorted order after the partial upper hull's last point Li.

If the three points Li−1, Li and the candidate point p form a right turn, ...

Get Algorithms in a Nutshell now with O’Reilly online learning.

O’Reilly members experience live online training, plus books, videos, and digital content from 200+ publishers.