Computing in Geographic Information Systems

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