Construct an applet which implements an algorithm to find the convex hull of a set of points. The convex hull of a set Q of points is the smallest convex polygon P for which each point in Q is either on the boundary of P or in its interior. The user can select either 50, 100 and 200 points. The algorithm to be used is Graham’s Scan.

1. Construct a simple closed polygon from a set of points.
2. Sort the points, based on the angle from the horizontal made from the line connecting each point with an anchor point, p(1).
3. Computation of the hull is finished by trying to place each point on the hull and removing those that can not be on the hull. We decide which points belong on the hull by the following procedure:

• After each point has been added to the ‘possible hull’, we go back and trace through the points added so far. At each point, we want to make a left turn. If we make a right turn, the point is removed.

Back to Main Page