# Gift Wrapping

Jump to navigation
Jump to search

**Gift Wrapping** is perhaps the simplest of the Convex Hull algorithms. Starting from the lowest, left-most point (this point has to be on the hull), "gift wrap" by choosing the next point such no points lie on the left of the line created by the current point and the next point. Repeat this until it wraps around back to the original point. The algorithm runs in time, or worst-case.

## Pseudo-code[edit]

*p*,*current*is a 2D point.*point*is an array containing the points.

p = left-most, bottom point current = p do { // Sentinel leftmost = 1 for i from 2 to N // If line current->leftmost is to the left of current->point[i] if ( left( current, point[i], leftmost ) ) leftmost = i // Output and move on. current = point[leftmost] } while ( current != p )