Hull Cembung

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.


In this visualization, we show Andrew's monotone chain and Graham's Scan algorithm.

2. Andrew's Monotone Chain

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.

3. Graham's Scan

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.

4. Pekerjaan Untuk Kedepannya

Visualisasi ini saat ini hanya digunakan sekali setahun di NUS (sekitar awal April tiap tahun untuk CS3233),, sehingga hanya diperbarui secara singkat sekali setahun.