the gift-wrapping algorithm

Gift wrapping builds the convex hull exactly the way you would wrap a gift by hand: pin the paper at one definite outer point, then pull it taut to the next point that wraps everyone else, pin again, and keep going around until you return to where you started. Each step finds one new hull vertex, so the algorithm literally produces the hull boundary one edge at a time, in order. It is the most intuitive hull method and a good mental model even if it is not always the fastest.

Mechanically, start from a point guaranteed to be on the hull — say the leftmost point. To find the next hull vertex, scan all remaining points and pick the one C that is the most clockwise (equivalently, such that every other point lies to the left of the directed edge from the current vertex to C). You decide this with the orientation test: candidate C beats the current best B if the triple current, B, C turns clockwise, meaning C wraps tighter. Set C as the next vertex and repeat from there. You stop when you wrap back to the starting point. Each new vertex costs one full O(n) scan of the points, and you do this once per hull vertex, so the total time is O(n*h) where h is the number of vertices on the hull.

That O(n*h) cost is the whole story of when to use it. If the hull has only a few vertices — say points scattered so that just h = 5 are on the boundary — gift wrapping is wonderfully cheap, effectively linear, and it never needs a sort. But if nearly all n points sit on the hull (think points on a circle), then h is about n and the cost balloons to O(n^2), worse than the O(n log n) of Graham scan or monotone chain. So gift wrapping is output-sensitive: fast when the output is small, slow when the output is large. Use it when you expect a small hull; otherwise prefer a sorting-based method.