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.
In this visualization, we show Andrew's monotone chain and Graham's Scan algorithm.
We first sort all N points by their x-coordinates (left to right), and if tie, by their y-coordinates (bottom to top). Then this algorithm finds the lower hull by going left to right, strictly maintaining only left (CCW) turns, and then finds the upper hull by going right to left, also by maintaining only left (CCW) turns.
We first pick a pivot point (bottom-most, left-most point for this visualization) that is guaranteed to be part of the convex hull, and then sort the other N-1 points in counter-clockwise order w.r.t. this pivot point.
PS: Picking bottom-most, right-most point as the pivot point is also possible, as this point will also guaranteed to be part of the convex hull.
这个可视化目前每年只在新加坡国立大学 (NUS) 使用一次（每年四月初，为了CS3233），因此它每年只更新一次。