A recursive algorithm for calculating the relative convex hull
Gisela Klette · 2010
The calculation of relative convex hulls is a special subject in computational geometry (shortest paths), in image analysis (calculation of features), in robotics (shortest path of a robot in a constrained environment), and so forth. The relative convex hull of a simple polygon A, that is contained in a second simple polygon B, is also the minimum perimeter polygon (MPP) [or the minimum length polygon (MLP) in the particular case of regions in digital images] that circumscribes A and is contained in B. The MPP (or the relative convex hull) is uniquely defined. The paper recalls properties and algorithms related to the relative convex hull, and proposes a new (recursive) algorithm for calculating the relative convex hull. The input may be simple polygons A and B in general, or more specific “inner and outer” polygonal shapes such as in 2D digital imaging.