Convex Hull

1. Introduction

The Convex Hull of a set of points P is the smallest convex polygon CH(P) for which each point in P is either on the boundary of CH(P) or in its interior. Imagine that the points are nails on a flat 2D plane and we have a long enough rubber band that can enclose all the nails. If this rubber band is released, it will try to enclose as small an area as possible. That area is the area of the convex hull of these set of points/nails. Finding convex hull of a set of points has natural applications in packing problems.

2. Graham's Scan

In this visualization, we currently only support Graham's Scan algorithm.

We first pick a pivot point (bottom-most, left-most point) and then sort the other N-1 points in counter-clockwise order w.r.t. this pivot point.

3. Future Works

This visualization is currently only used once a year in NUS (around early April each year, for CS3233), hence it only gets updated briefly once a year.