Graphics Reference
In-Depth Information
C
D
A
G
E
F
B
Figure 3.22
Andrew's algorithm. Top left: the point set. Top right: the points sorted (lexi-
cographically) from left to right. Middle left: during construction of the upper chain. Middle
right: the completed upper chain. Lower left: the lower chain. Lower right: the two chains
together forming the convex hull.
Two of them are briefly described in the next two sections: Andrew's algorithm and
the Quickhull algorithm.
3.9.1
Andrew's Algorithm
One of the most robust and easy to implement 2D convex hull algorithms is
Andrew's
algorithm
[Andrew79]. In its first pass, it starts by sorting all points in the given point
set from left to right. In subsequent second and third passes, chains of edges from
the leftmost to the rightmost point are formed, corresponding to the upper and lower
half of the convex hull, respectively. With the chains created, the hull is obtained by
simply connecting the two chains end to end. The process is illustrated in Figure 3.22.
The main step lies in the creation of the chains of hull edges. To see how one of the
chains is formed, consider the partially constructed upper chain of points, as shown
in the middle left-hand illustration. To simplify the presentation, it is assumed there
are not multiple points of the same
x
coordinate (this assumption is lifted further on).
Initially, the two leftmost points,
A
and
B
, are taken to form the first edge of the
chain. The remaining points are now processed in order, considered one by one for
addition to the hull chain. If the next point for consideration lies to the right of the
