Gift wrapping algorithm

The gift wrapping algorithm is an algorithm for computing the convex hull of a set of points in two or more dimensions.

Two dimensions

expand Sorry, but you need Java to see the animation. Find least point A (with minimum y coordinate) as a starting point.
expand Sorry, but you need Java to see the animation. We can find B where all points lie to the left of AB by scanning through all the points.
expand Sorry, but you need Java to see the animation. Similarly, we can find C where all points lie to the left of BC. We can repeat this to find the next point and so on.

If the number of sides of the hull is h then the complexity is nh.

Three dimensions

You can use the left mouse button to look at any of the images below from a different direction.
expand Sorry, but you need Java to see the animation. Find a starting edge AB by using the 2D algorithm on the projection of the points on the XY plane.
expand Sorry, but you need Java to see the animation. We can find C where all points lie to the left of triangle ABC by scanning through all the points. The view to the left is looking along AB so that the triangle appears as a line.
expand Sorry, but you need Java to see the animation. Similarly, we can find D where all points lie to the left of ACD. The view to the left is looking along AC so that the triangle appears as a line. We also need to find the other triangle adjacent to BA and CB, So we need a stack or a queue to organise the search. Can repeat this to find the next point and so on.

More dimensions

We can generalise this to any number of dimensions.
lambert@cse.unsw.edu.au
Last modified: Fri Sep 18 17:42:22 AET 1998