← Back to index

Convex hull (gift wrap)

The smallest convex polygon containing every input point. The gift-wrap algorithm (also called Jarvis march) starts at an extreme point and repeatedly picks the next hull vertex as the one that keeps every other point on the same side of the new edge. Move the mouse to add an extra live point.

Pseudocode

start = leftmost point in S
hull = []
current = start
loop:
    hull.push(current)
    next = any other point in S
    for each candidate in S:
        // turn from current->next towards candidate
        cross = (next - current) × (candidate - current)
        if next == current or cross is "more right-handed":
            next = candidate
    current = next
    if current == start: break

Source

function giftWrap(points) {
    if (points.length < 3) return points.slice()
    let start = 0
    for (let i = 1; i < points.length; i++) {
        if (points[i].x < points[start].x) start = i
    }
    const hull = []
    let current = start
    do {
        hull.push(points[current])
        let next = (current + 1) % points.length
        for (let i = 0; i < points.length; i++) {
            if (i === current) continue
            const cx = points[current].x, cy = points[current].y
            const nx = points[next].x,    ny = points[next].y
            const px = points[i].x,       py = points[i].y
            const cross = (nx - cx) * (py - cy) - (ny - cy) * (px - cx)
            if (cross < 0) next = i      // candidate is more counter-clockwise (screen coords)
        }
        current = next
    } while (current !== start)
    return hull
}