Java Applets Centre

Graham's Scan Algorithm

Description
The Graham's Scan algorithm is used to compute the convex hull of a set of points. The point with minimum y-coordinate is identified first, and the remaining points sorted by the angle made with the x-axis by vectors from the minimum point to those points. The pseudo-code of the algorithm is given below.

Click the mouse anywhere on the applet to input a point at that location. Define a set of points in this manner.

Compute Hull: After specifying a set of points, click this button to start the algorithm.

Clear: Clears the screen. Click this button to start the input of a new set of points.

Pseudo-Code

P0 = Rightmost lowest point
Label points in the sorted set as P1, P2, … Pn-1.
Stack S ;
S.Push(Pn-1); S.Push(P0); i = 1;
while i < n do
{
   B = S.Pop(); A = S.Peek();
   if Pi is strictly left of AB
   {
      S.Push(B ); S.Push(Pi );
      i = i + 1;
   }
}

Computational Geometry
Java Applets Centre

R. Mukundan
Department of Computer Science
University of Canterbury
Private Bag 4800, Christchurch
New Zealand.