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.

• Enter P/Q toggles whether points are added to (and deleted from) the polygon P or from the set of red points Q.
• Animate toggles some animation of partial computation
• Update is the button you push when the input is ready
• Clear All and Delete Last give minimalist editing.

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.