Convex Hull Using Jarvis March | Gift Wrapping Tutorial with Python

The animation starts from the leftmost point and repeatedly selects the most counterclockwise next point. By joining these boundary points one by one, Jarvis March wraps around the set and forms the convex hull.

Jarvis March, also called the Gift Wrapping algorithm, is a simple way to find the convex hull of a set of points. In this tutorial, we explain the idea in layman terms, show how the orientation test works, provide pseudocode, and build a small animation and Python implementation.

1. Main idea in simple words

Imagine some points placed on paper.

Now think of wrapping a thread around the outermost points.

The thread touches only the boundary points.
That boundary is the convex hull.

The Jarvis March / Gift Wrapping method finds hull points one by one:

start from the leftmost point
then find the next outer point
then the next
keep going until you come back to the starting point

It is like walking around the outside fence of the points.

2. Why it is better than brute force

The brute force method checks many point pairs and is slow: (O(n^3)).

Jarvis March is smarter:

for each hull point, it scans all points once
if there are (h) hull points, time is:
[O(nh)]
In the worst case, (h = n), so:
[O(n^2)]

3. Intuition

Suppose you are standing at one hull point.

Now you want the next hull point.

So you look at all other points and choose the one such that all points lie to one side of the line.

That chosen point becomes the next point on the hull.

Then repeat.

4. Orientation test

For three points A, B, C, compute:

[(B_x-A_x)(C_y-A_y) – (B_y-A_y)(C_x-A_x)]

This tells the turn direction:

positive → left turn
negative → right turn
zero → collinear

Jarvis March uses this to decide which candidate point is the “most outside.”

5. Algorithm steps

Find the leftmost point
Put it in the hull
Choose a candidate for the next point
Scan all points:
Move to that candidate
Stop when you return to the starting point

6. Pseudocode

			
JARVIS_MARCH(points):
    hull = empty list
    leftmost = point with smallest x
    current = leftmost
    repeat:
        add current to hull
        next_point = any other point
        for each point p in points:
            if p is more counterclockwise than next_point
               with respect to current:
                next_point = p
        current = next_point
    until current == leftmost
    return hull

		

7. Python implementation

import math
import matplotlib.pyplot as plt
from matplotlib.animation import FuncAnimation

def orientation(a, b, c):
    return (b[0] - a[0]) * (c[1] - a[1]) - (b[1] - a[1]) * (c[0] - a[0])

def distance_sq(a, b):
    return (a[0] - b[0])**2 + (a[1] - b[1])**2

def jarvis_march(points):
    n = len(points)
    if n < 3:
        return points[:]

    # leftmost point
    leftmost = min(points, key=lambda p: (p[0], p[1]))
    hull = []
    current = leftmost

    while True:
        hull.append(current)
        next_point = points[0] if points[0] != current else points[1]

        for p in points:
            if p == current:
                continue

            val = orientation(current, next_point, p)

            # If p is more counterclockwise, update next_point
            if val > 0:
                next_point = p
            elif val == 0:
                # keep the farthest collinear point
                if distance_sq(current, p) > distance_sq(current, next_point):
                    next_point = p

        current = next_point

        if current == leftmost:
            break

    return hull


# Example points
points = [(1, 1), (2, 4), (4, 5), (6, 3), (5, 1), (3, 2), (4, 3), (2.5, 2.5)]

hull = jarvis_march(points)
print("Hull points in order:")
for p in hull:
    print(p)

# Static plot
plt.figure(figsize=(6, 6))
x = [p[0] for p in points]
y = [p[1] for p in points]
plt.scatter(x, y)

hx = [p[0] for p in hull] + [hull[0][0]]
hy = [p[1] for p in hull] + [hull[0][1]]
plt.plot(hx, hy)

for i, p in enumerate(points):
    plt.text(p[0] + 0.05, p[1] + 0.05, f"P{i}")

plt.title("Convex Hull using Jarvis March")
plt.xlabel("X")
plt.ylabel("Y")
plt.grid(True)
plt.axis("equal")
plt.show()

import math

import matplotlib.pyplot as plt

from matplotlib.animation import FuncAnimation

def orientation(a, b, c):

return (b[0] - a[0]) * (c[1] - a[1]) - (b[1] - a[1]) * (c[0] - a[0])

def distance_sq(a, b):

return (a[0] - b[0])**2 + (a[1] - b[1])**2

def jarvis_march(points):

n = len(points)

if n < 3:

return points[:]

# leftmost point

leftmost = min(points, key=lambda p: (p[0], p[1]))

hull = []

current = leftmost

while True:

hull.append(current)

next_point = points[0] if points[0] != current else points[1]

for p in points:

if p == current:

continue

val = orientation(current, next_point, p)

# If p is more counterclockwise, update next_point

if val > 0:

next_point = p

elif val == 0:

# keep the farthest collinear point

if distance_sq(current, p) > distance_sq(current, next_point):

next_point = p

current = next_point

if current == leftmost:

break

return hull

# Example points

points = [(1, 1), (2, 4), (4, 5), (6, 3), (5, 1), (3, 2), (4, 3), (2.5, 2.5)]

hull = jarvis_march(points)

print("Hull points in order:")

for p in hull:

print(p)

# Static plot

plt.figure(figsize=(6, 6))

x = [p[0] for p in points]

y = [p[1] for p in points]

plt.scatter(x, y)

hx = [p[0] for p in hull] + [hull[0][0]]

hy = [p[1] for p in hull] + [hull[0][1]]

plt.plot(hx, hy)

for i, p in enumerate(points):

plt.text(p[0] + 0.05, p[1] + 0.05, f"P{i}")

plt.title("Convex Hull using Jarvis March")

plt.xlabel("X")

plt.ylabel("Y")

plt.grid(True)

plt.axis("equal")

plt.show()

8. Very short explanation for narration

“Jarvis March, also called Gift Wrapping, finds the convex hull by starting from the leftmost point and repeatedly selecting the next outermost point. At each step, it scans all points to find the most counterclockwise one. This continues until the algorithm returns to the starting point. Its worst-case time complexity is (O(n^2)).”

9. One-line summary

Jarvis March builds the convex hull by walking from one boundary point to the next, always choosing the most outside turn.

I hope this tutorial will create a good foundation for you. If you want tutorials on another topic or you have any queries, please send an mail at contact@spatial-dev.guru.