Relative Convex Hull

Computes the relative convex hull of a set of red points Q inside a blue simple polygon P (counter-clockwise oriented, as usual). The algorithm is a modification of Jarvis march, so is not optimal, but is comparatively easy. It actually starts at the first vertex of P, then wraps Q twice, and stops just before it reaches the first vertex of P again.

Known bugs: I really should trim the tails off the green relative convex hull.

Code by Jack Snoeyink, University of British Columbia Back to Jack's Computational Geometry Demo page.