CoreSource checked

Jarvis March

Finds a convex hull by wrapping around the outside point by point.

Explore relationships Open constellationBrowse atlas

Quick Facts

Compact metadata for implementation and discovery.

Category: Geometry
Difficulty: Beginner
Family: Convex Hull
Tier: Core
Status: Verified
Review: Source Checked
Sources: 1
Formulas: 1
Relationships: 4
Code example: Not ready
Visualization: Ready
Aliases: Gift Wrapping

Overview

Jarvis March starts from an extreme point and repeatedly chooses the next point that keeps all others on one side.

Core Concepts

geometric calculationgeometric predicatepolygon boundaryconvex hullspatial relationshipcoordinate calculation

Quick facts

Complexity

Runtime and memory behavior at a glance.

Best

O(n)

Average

O(nh)

Worst

O(n^2)

Space

O(1)

When to Use

Use Jarvis March when you need to choose the next outermost point.
Use it for convex hulls with few boundary points with inputs like set of points.
Use it when the problem depends on spatial relationships between points, lines, or shapes.
Use it when the Convex Hull tradeoff is acceptable for the problem size.

When Not to Use

Avoid it when floating-point precision or degenerate cases are not handled.
Avoid it when O(n^2) worst-case behavior is too costly for the expected input size.
Avoid it when the required output is not convex hull vertices.

What It Does

Chooses the next outermost point
Walks around the hull boundary

Use Cases

Convex hulls with few boundary points
Geometry teaching
Small point sets

Inputs

Set of points

Outputs

Convex hull vertices

Key Formulas (1)

Next hull point

choose q such that orientation(current, q, r) is counterclockwise for all r

choose q such that orientation(current, q, r) is counterclockwise for all r

Selects the next outer boundary point by wrapping around the set.

Pseudocode

1.Find the leftmost point
2.Select a candidate next point
3.Check every point to find the most counterclockwise choice
4.Append that point to the hull
5.Repeat until back at the start

Canonical Example

Input: points = [(0,0), (2,0), (1,1), (1,0)]
Output: spatial result such as a boundary, intersection, or containment answer
Explanation: Jarvis March: The algorithm uses geometric tests to reason about the input shapes.

Implementation Notes

Keep the input contract explicit: Set of points.
Use this step as the implementation spine: Find the leftmost point.
Then preserve the next state change: Select a candidate next point.
Write tests for points on boundaries, equal coordinates, and very small distances.

Common Pitfalls

Jarvis March is output-sensitive because it depends on the number of hull points.
Forgetting collinear, duplicate, overlapping, or boundary cases.
Returning convex hull vertices without handling empty, invalid, or boundary inputs.

Interactive Mechanism Walkthrough

Spatial Primitive & Sweep-Line Canvas

Show a line wrapping around the outside of a point set.

Step 1 of 5: Find the leftmost point

gift-wrap-hull

Notes

Jarvis March operates in O(nh) time and O(1) space within the Convex Hull family. Key governing relation: choose q such that orientation(current, q, r) is counterclockwise for all r. Often compared with Convex Hull and Graham Scan.