THE CONVEX HULL — a dart

THE CONVEX HULL the rubber band around the points — keep the extremes, drop the inside

The convex hull of a point set is the smallest convex shape containing them all — the rubber band snapped around the outermost points. Gift wrapping (Jarvis march) builds it by orientation alone: start at the leftmost point and repeatedly pick the next point that is most clockwise, so every other point lies to one side. Interior points are simply dropped — they belong to no hull edge. For the square’s four corners plus an interior point, the hull is the four corners; the inside point (2,2), being within a triangle of the others, is excluded.

THE TECHNIQUE gift wrapping: pick the most-clockwise point each step (orientation)

The demo shows the hull excludes an interior point — (2,2) is inside triangle (0,0),(4,0),(0,4), while corner (4,4) is not: live demo

HISTORY & CREDIT Jarvis march 1973 · Graham 1972

“You must consider every point for the outline.” — only the extremes; interior points belong to no hull edge and are dropped. cited

the wrap · from the leftmost point, pick the most-clockwise next point — orientation only.
the drop · interior points lie inside some triangle of others — excluded from the hull.
1972-73 · Graham scan; Jarvis march (gift wrapping).

A band around the outermost points, the inside let go — the shape read off by orientation. resource

RECOMMEND FOR I-13 interior excluded, on the compiler

On the canonical compiler, (2,2) is inside triangle (0,0),(4,0),(0,4) so it is not a hull vertex; corner (4,4) is not inside, so it is kept:

$ i13 run cg_convexhull.i13 # gift-wrapping keeps extremes RUN OK · 283 step(s) · peak stack 9 · call depth 2 interior_excluded = 1 -- (2,2) inside the triangle: dropped corner_kept = 1 -- (4,4) not inside: a hull vertex hull_ok = 1

Recommend as a NULL — a computed set, via orientation. The convex hull is a construction built from the orientation predicate (dart 487); it computes a subset of points (the extremes), which is a resource/algorithmic result (B40) whose answer is forall-pinned by the input (B39). No new invariant. NULL — the rubber band, read off by the cross product’s sign.