
134 Computing in Geographic Information Systems
(O’Rourke suggests using a linked list to represent this stack.) The essential
issue at each step is how to process the next point, p
i
. Let p
t
and p
t−1
denote
the vertices that currently at the top and next to top positions on the stack.
If p
i
lies strictly to the left of the directed segment ¯p
t−1
p
t
(which we can
determine by an orientation test) then we add p
i
to the stack. Otherwise, we
know that p
t
cannot be on the convex hull. Why not? (Because the point p
t
lies within the triangle p
o
p
t−1
p
i
, and hence cannot be on the hull.) We pop
p
t
off the stack. We repeat the popping until p
i
is strictly to the left