Giftwrapping a curve with the convex hull
John K. Johnstone · 2004
We develop an algorithm to compute the convex hull of a closed planar parametric curve. The algorithm sweeps a tangent around the curve, using bitangents to define events and effectively wrapping a tangent around the hull. First, a point on the hull is found using a walk out of a concavity and next, the entire hull is found using a walk punctuated by bitangents. The algorithm is a smooth analogue to two classical computational geometry algorithms: plane sweep and giftwrapping. It leverages our recent work on the computation of bitangents.