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.
Remarks: By default, we show e-Lecture Mode for first time (or non logged-in) visitor.
If you are an NUS student and a repeat visitor, please login.
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.
Pro-tip 1: Since you are not logged-in, you may be a first time visitor (or not an NUS student) who are not aware of the following keyboard shortcuts to navigate this e-Lecture mode: [PageDown]/[PageUp] to go to the next/previous slide, respectively, (and if the drop-down box is highlighted, you can also use [→ or ↓/← or ↑] to do the same),and [Esc] to toggle between this e-Lecture mode and exploration mode.
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.
Pro-tip 2: We designed this visualization and this e-Lecture mode to look good on 1366x768 resolution or larger (typical modern laptop resolution in 2021). We recommend using Google Chrome to access VisuAlgo. Go to full screen mode (F11) to enjoy this setup. However, you can use zoom-in (Ctrl +) or zoom-out (Ctrl -) to calibrate this.
Pro-tip 3: Other than using the typical media UI at the bottom of the page, you can also control the animation playback using keyboard shortcuts (in Exploration Mode): Spacebar to play/pause/replay the animation, ←/→ to step the animation backwards/forwards, respectively, and -/+ to decrease/increase the animation speed, respectively.
Buat
Example Points
Edit Points
Andrew_Chain(Pts)
CH_Graham(pts)
Shamos(Pts)