# Jarvis March

The first two-dimensional convex hull algorithm was originally developed by R. A. Jarvis in 1973 . Though other convex hull algorithms exist, this algorithm is often called the gift-wrapping algorithm.

The idea behind this algorithm is simple. If we start with a random distribution of points, we can find the convex hull by first starting with the left-most point and using the origin to calculate an angle between every other point in the simulation. As a note, the "angle" can be roughly approximated with a cross-product or a dot product, which is common for some implementations here. Whichever point has the largest interior angle is chosen as the next point in the convex hull and we draw a line between the two points. From there, we use the two known points to again calculate the angle between all other points in the simulation. We then choose the point with the largest interior angle and move the simulation forward. We keep repeating this process until we have returned to our original point. The set of points chosen in this simulation will be the convex hull.

As we might expect, this algorithm is not incredibly efficient and has a runtime of , where is the number of points and is the size of the hull. As a note, the Jarvis March can be generalized to higher dimensions. Since this algorithm, there have been many other algorithms that have advanced the field of two-dimensional gift-wrapping forward, including the Graham Scan and Chan's Algorithm, which will be discussed in due time.

### Bibliography

1.
Jarvis, Ray A, On the identification of the convex hull of a finite set of points in the plane, Elsevier, 1973.

## Example Code

##### JarvisMarch.cs
// submitted by Julian Schacher (jspp) with great help by gustorn
using System;
using System.Collections.Generic;
using System.Linq;

namespace JarvisMarch
{
public struct Vector
{

public Vector(int xValue, int yValue)
{
this.x = xValue;
this.y = yValue;
}

public override bool Equals(object obj) => obj is Vector v && this.x == v.x && this.y == v.y;
public override int GetHashCode() => (17 * 23 + this.x) * 23 + this.y;

public static bool operator==(Vector a, Vector b) => a.Equals(b);
public static bool operator!=(Vector a, Vector b) => !(a == b);
}

public class JarvisMarch
{
public List<Vector> Run(List<Vector> points)
{
var convexHull = new List<Vector>();

// Set the intial pointOnHull to the point of the list, where the x-position is the lowest.
var pointOnHull = points.Aggregate((leftmost, current) => leftmost.x < current.x ? leftmost : current);

// Continue searching for the next pointOnHull until the next pointOnHull is equal to the first point of the convex hull.
do
{

// Search for the next pointOnHull by looking which of the points is the next most outer point.
pointOnHull = points.Aggregate((potentialNextPointOnHull, current) =>
{
// Returns true, if potentialNextPointOnHull is equal to the current pointOnHull or if the current point is left of the line defined by pointOnHull and potentialNextPointOnHull.
if (potentialNextPointOnHull == pointOnHull || IsLeftOf(pointOnHull, potentialNextPointOnHull, current))
return current;
return potentialNextPointOnHull;
});

// Check if the gift wrap is completed.
} while (pointOnHull != convexHull);

return convexHull;
}

// Returns true, if p is left of the line defined by a and b.
private bool IsLeftOf(Vector a, Vector b, Vector p) => (b.x - a.x) * (p.y - a.y) > (p.x - a.x) * (b.y - a.y);
}
}

##### Program.cs
// submitted by Julian Schacher (jspp) with great help by gustorn
using System;
using System.Collections.Generic;

namespace JarvisMarch
{
class Program
{
static void Main(string[] args)
{
System.Console.WriteLine("JarvisMarch");
// Example list of points.
// The points are represented by vectors here, but that doesn't really matter.
var points = new List<Vector>()
{
new Vector(-5, 2),
new Vector(5, 7),
new Vector(-6, -12),
new Vector(-14, -14),
new Vector(9, 9),
new Vector(-1, -1),
new Vector(-10, 11),
new Vector(-6, 15),
new Vector(-6, -8),
new Vector(15, -9),
new Vector(7, -7),
new Vector(-2, -9),
new Vector(6, -5),
new Vector(0, 14),
new Vector(2, 8),
};
var jarvisMarch = new JarvisMarch();

// Print the points of the gift wrap.
System.Console.WriteLine($"{point.x}, {point.y}"); } } }  struct Pos x::Float64 y::Float64 end function jarvis_cross(point1::Pos, point2::Pos, point3::Pos) vec1 = Pos(point2.x - point1.x, point2.y - point1.y) vec2 = Pos(point3.x - point2.x, point3.y - point2.y) ret_cross = vec1.x*vec2.y - vec1.y*vec2.x return ret_cross*ret_cross end function jarvis_march(points::Vector{Pos}) hull = Vector{Pos}() # sorting array based on leftmost point sort!(points, by = item -> item.x) push!(hull, points) i = 1 curr_point = points # Find cross product between points curr_product = jarvis_cross(Pos(0,0), hull, curr_point) while (curr_point != hull) for point in points product = 0.0 if (i == 1) if (hull[i] != point) product = jarvis_cross(Pos(0,0), hull[i], point) end else if (hull[i] != point && hull[i-1] != point) product = jarvis_cross(hull[i-1], hull[i], point) end end if (product > curr_product) curr_point = point curr_product = product end end push!(hull, curr_point) curr_product = 0 i += 1 end return hull end function main() points = [Pos(2,1.5), Pos(1, 1), Pos(2, 4), Pos(3, 1)] hull = jarvis_march(points) println(hull) end main()  import Data.List (sort, maximumBy) import Data.Function (on) type Point = (Double, Double) angle :: Point -> Point -> Point -> Double angle a@(xa, ya) b@(xb, yb) c@(xc, yc) | a==b || c==b = 0 | theta<0 = theta+2*pi | otherwise = theta where thetaA = atan2 (ya-yb) (xa-xb) thetaC = atan2 (yc-yb) (xc-xb) theta = thetaC - thetaA jarvisMarch :: [Point] -> [Point] jarvisMarch [] = [] jarvisMarch pts = p0 : wrap (x, y-1) p0 where p0@(x, y)= minimum pts wrap p1 p2 | pm == p0 = [] | otherwise = pm : wrap p2 pm where pm = maximumBy (compare on angle p1 p2) pts main = do let pts = filter (\(x,y) -> x^2+y^2<=5^2) [(x,y)|x<-[-5..5], y<-[-5..5]] print$ jarvisMarch pts

#include <stdio.h>
#include <stddef.h>
#include <stdbool.h>

struct point {
double x,y;
};

struct point left_most_point(struct point *points, size_t num_points) {
struct point ret = points;

for (size_t i = 0; i < num_points; ++i) {
if (points[i].x < ret.x) {
ret = points[i];
} else if(points[i].x == ret.x) {
if (points[i].y < ret.y) {
ret = points[i];
}
}
}

return ret;
}

bool equal(struct point a, struct point b) {
return a.x == b.x && a.y == b.y;
}

double winding(struct point p, struct point q, struct point r) {
return (q.x - p.x)*(r.y - p.y) - (q.y - p.y)*(r.x - p.x);
}

size_t jarvis_march(struct point *points, struct point *hull_points,
size_t num_points) {
struct point hull_point = left_most_point(points, num_points);
struct point end_point;

size_t i = 0;
do {
hull_points[i] = hull_point;
end_point = points;

for (size_t j = 1; j < num_points; ++j) {
if (equal(end_point, hull_point) ||
winding(hull_points[i], end_point, points[j]) > 0.0) {
end_point = points[j];
}
}

i++;
hull_point = end_point;
} while (!equal(end_point, hull_points));

return i;
}

int main() {
struct point points[] = {
{ -5.0, 2.0 },
{ 5.0, 7.0 },
{ -6.0, -12.0 },
{ -14.0, -14.0 },
{ 9.0, 9.0 },
{ -1.0, -1.0 },
{ -10.0, 11.0 },
{ -6.0, 15.0 },
{ -6.0, -8.0 },
{ 15.0, -9.0 },
{ 7.0, -7.0 },
{ -2.0, -9.0 },
{ 6.0, -5.0 },
{ 0.0, 14.0 },
{ 2.0, 8.0 }
};
struct point hull_points;

size_t num_hull_points = jarvis_march(points, hull_points, 15);

printf("The Hull points are:\n");
for (size_t i = 0; i < num_hull_points; ++i) {
printf("x=%f y=%f\n", hull_points[i].x, hull_points[i].y);
}

return 0;
}

function jarvisMarch(points) {
const hull = [];

let pointOnHull = points.reduce((leftmost, current) => leftmost.x < current.x ? leftmost : current);
do {
hull.push(pointOnHull);
pointOnHull = points.reduce(chooseNextPointOnHull(pointOnHull));
} while (pointOnHull !== hull);

return hull;
}

function chooseNextPointOnHull(currentPoint) {
return function (nextPoint, candidate) {
if (nextPoint === currentPoint || isLeftOf({ a: currentPoint, b: nextPoint }, candidate)) {
return candidate;
}
return nextPoint;
}
}

function isLeftOf({ a, b }, p) {
return (b.x - a.x) * (p.y - a.y) > (p.x - a.x) * (b.y - a.y);
}

const points = [
{ x: -5, y: 2 },
{ x: 5, y: 7 },
{ x: -6, y: -12 },
{ x: -14, y: -14 },
{ x: 9, y: 9 },
{ x: -1, y: -1 },
{ x: -10, y: 11 },
{ x: -6, y: 15 },
{ x: -6, y: -8 },
{ x: 15, y: -9 },
{ x: 7, y: -7 },
{ x: -2, y: -9 },
{ x: 6, y: -5 },
{ x: 0, y: 14 },
{ x: 2, y: 8 }
];

const convexHull = jarvisMarch(points);
convexHull.forEach(p => console.log((${p.x},${p.y})));

# Is the turn counter clockwise?
def ccw(p1, p2, p3):
return (p3 - p1) * (p2 - p1) \
>= (p2 - p1) * (p3 - p1)

n = len(gift)  # Number of points in list
hull = [point_on_hull]  # leftmost point guaranteed to be in hull

while True:
# Candidate for next point in hull
for j in range(1, n):
if endpoint == point_on_hull \

point_on_hull = endpoint

# Check if we have completely wrapped gift
if hull == endpoint:
break
else:
hull.append(point_on_hull)

return hull

def main():
(-5, 2), (5, 7), (-6, -12), (-14, -14), (9, 9),
(-1, -1), (-10, 11), (-6, 15), (-6, -8), (15, -9),
(7, -7), (-2, -9), (6, -5), (0, 14), (2, 8)
]

print("The points in the hull are:")
for point in hull:
print(point)

if __name__ == "__main__":
main()

#include <vector>
#include <iostream>
#include <algorithm>

struct Point
{
double x, y;

bool operator==(const Point& b) const
{
return x == b.x && y == b.y;
}

bool operator!=(const Point& b) const
{
return !(*this == b);
}
};

std::vector<Point> jarvis_march(const std::vector<Point>& points)
{
std::vector<Point> hull_points;

if(points.empty())
return hull_points;

// Left most point
auto first_point_it = std::min_element(points.begin(), points.end(), [](const Point& a, const Point& b){ return a.x < b.x; });

auto next_point_it = first_point_it;
do
{
hull_points.push_back(*next_point_it);

const Point& p1 = hull_points.back();

// Largest internal angle
next_point_it = std::max_element(
points.begin(),
points.end(),
[p1](const Point& p2, const Point& p3){
return (p1 == p2) || (p2.x - p1.x) * (p3.y - p1.y) > (p3.x - p1.x) * (p2.y - p1.y);
}
);
}
while(*next_point_it != *first_point_it);

return hull_points;
}

int main() {
std::vector<Point> points = {
{ -5.0, 2.0 },
{ 5.0, 7.0 },
{ -6.0, -12.0 },
{ -14.0, -14.0 },
{ 9.0, 9.0 },
{ -1.0, -1.0 },
{ -10.0, 11.0 },
{ -6.0, 15.0 },
{ -6.0, -8.0 },
{ 15.0, -9.0 },
{ 7.0, -7.0 },
{ -2.0, -9.0 },
{ 6.0, -5.0 },
{ 0.0, 14.0 },
{ 2.0, 8.0 }
};

auto hull_points = jarvis_march(points);

std::cout << "Hull points are:" << std::endl;

for(const Point& point : hull_points) {
std::cout << '(' << point.x << ", " << point.y << ')' << std::endl;
}
}

;;;; Jarvis March implementation

(defstruct (point (:constructor make-point (x y))) x y)

(defun is-left-p (p1 p2 p3)
"Checks if the point p3 is to the left of the line p1 -> p2"
(>
(*
(- (point-y p3) (point-y p1))
(- (point-x p2) (point-x p1)))
(*
(- (point-y p2) (point-y p1))
(- (point-x p3) (point-x p1)))))

"Finds the next point on the convex hull of a gift"
p2
(if (is-left-p p1 p2 (first gift))

"Returns the lefmost point of a gift"
(reduce
(lambda (p1 p2)
(if (< (point-x p1) (point-x p2)) p1 p2))

"finds the convex hull of any distribution of points"
;deals with the edge cases
(loop
with hull = (list start (make-point (point-x start) (- (point-y start) 1)))
do
(setq hull
(cons
(next-point-on-hull (first hull) (second hull) gift)
hull))
until (equalp (first hull) start)
;deletes extra points
finally (return (rest (butlast hull))))))

(map
'list
(lambda (e) (apply #'make-point e))
'((2 1.5) (1 1) (2 4) (3 1))))


import java.util.*;

public class JarvisMarch {

static class Point {
private double x;
private double y;

public Point(double a, double b) {
x = a;
y = b;
}

public double getX() {
return x;
}
public double getY() {
return y;
}

public boolean equals(Point p) {
if (p.getX() == x && p.getY() == y) {
return true;
} else {
return false;
}
}
public double magnitude() {
return Math.sqrt(Math.pow(x, 2) + Math.pow(y, 2));
}
}

//find the angle by creating two vectors and then using a property of dot products
private static double angle(Point a, Point b, Point c) {
Point ab = new Point(b.getX() - a.getX(), b.getY() - a.getY());
Point bc = new Point(c.getX() - b.getX(), c.getY() - b.getY());
return Math.acos(-1 * ((ab.getX() * bc.getX()) + (ab.getY() * bc.getY())) /
(ab.magnitude() * bc.magnitude()));
}

public static ArrayList<Point> jarvisMarch(ArrayList<Point> arr) {
ArrayList<Point> hull = new ArrayList<Point>();
Point pointOnHull = new Point(Double.MAX_VALUE, 0);

//find leftmost point
for (Point p: arr) {
if (p.getX() < pointOnHull.getX()) {
pointOnHull = p;
}
}

//look for the rest of the points on the hull
Point ref;
while (true) {
if (hull.size() == 1) {
ref = new Point(pointOnHull.getX(), pointOnHull.getY() + 1); //finds a third point to use in calculating the angle
} else {
ref = hull.get(hull.size() - 2);
}
Point endpoint = arr.get(0); //initial canidate for next point in hull
for (Point p: arr) {
if (angle(p, pointOnHull, ref) > angle(endpoint, pointOnHull, ref)) { //found a point that makes a greater angle
endpoint = p;
}
}
pointOnHull = endpoint;
if (pointOnHull.equals(hull.get(0))) { //add next point to hull if not equal to the leftmost point
break;
} else {
}
}
return hull;
}

public static void main(String[] args) {

//test array setup

//print initial array of points
System.out.println("[" + p.getX() + ", " + p.getY() + "]");
}

//find and print the array of points in the hull
System.out.println("Wrapping:");
for (Point p: hull) {
System.out.println("[" + p.getX() + ", " + p.getY() + "]");
}
}

}

package main

import (
"fmt"
)

type point struct {
x, y float64
}

func leftMostPoint(points []point) point {
ret := points

for _, p := range points {
if (p.x < ret.x) || (p.x == ret.x && p.y < ret.y) {
ret = p
}
}

return ret
}

func (p point) equal(o point) bool {
return p.x == o.x && p.y == o.y
}

func counterClockWise(p1, p2, p3 point) bool {
return (p3.y-p1.y)*(p2.x-p1.x) >= (p2.y-p1.y)*(p3.x-p1.x)
}

func jarvisMarch(points []point) []point {
hullPoints := make([]point, 0)
hullPoint := leftMostPoint(points)
hullPoints = append(hullPoints, hullPoint)

for {
endPoint := points

for _, p := range points[1:] {
if endPoint.equal(hullPoint) || !counterClockWise(p, hullPoints[len(hullPoints)-1], endPoint) {
endPoint = p
}
}

hullPoint = endPoint

if endPoint.equal(hullPoints) {
break
}

hullPoints = append(hullPoints, hullPoint)
}
return hullPoints
}

func main() {
points := []point{{-5, 2}, {5, 7}, {-6, -12}, {-14, -14}, {9, 9},
{-1, -1}, {-10, 11}, {-6, 15}, {-6, -8}, {15, -9},
{7, -7}, {-2, -9}, {6, -5}, {0, 14}, {2, 8},
}

hullPoints := jarvisMarch(points)
fmt.Println("The hull points are:")

for _, p := range hullPoints {
fmt.Printf("x=%f y=%f\n", p.x, p.y)
}
}

struct Point {
x int
y int
}

fn left_most_point(points []Point) Point {
mut ret := points

for p in points {
if (p.x < ret.x) || (p.x == ret.x && p.y < ret.y) {
ret = p
}
}

return ret
}

fn (p Point) equal(o Point) bool {
return p.x == o.x && p.y == o.x
}

fn counter_clock_wise(p1, p2, p3 Point) bool {
return (p3.y-p1.y) * (p2.x-p1.x) >= (p2.y-p1.y) * (p3.x-p1.x)
}

fn jarvis_march(points []Point) []Point {
mut hull_point := left_most_point(points)
mut hull_points := [hull_point]

for {
mut end_point := points

for i := 1; i < points.len; i++ {
if end_point.equal(points[i]) || !counter_clock_wise(points[i], hull_points[hull_points.len-1], end_point) {
end_point = points[i]
}
}

hull_point = end_point
if end_point.equal(hull_points) {
break
}

hull_points << hull_point
}
return hull_points
}

fn main() {
points := [
Point{-5, 2}, Point{5, 7}, Point{-6, -12}, Point{-14, -14}, Point{9, 9},
Point{-1, -1}, Point{-10, 11}, Point{-6, 15}, Point{-6, -8}, Point{15, -9},
Point{7, -7}, Point{-2, -9}, Point{6, -5}, Point{0, 14}, Point{2, 8}
]

hull_points := jarvis_march(points)

println('The hull points are:')
for p in hull_points {
println('x=$p.x y=$p.y')
}
}


type Point = (i64, i64);

// Is the turn counter clockwise?
fn turn_counter_clockwise(p1: Point, p2: Point, p3: Point) -> bool {
(p3.1 - p1.1) * (p2.0 - p1.0) >= (p2.1 - p1.1) * (p3.0 - p1.0)
}

fn jarvis_march(gift: &[Point]) -> Option<Vec<Point>> {
// There can only be a convex hull if there are more than 2 points
return None;
}

// Iterate over all points
.iter()
// Find the point with minimum x
.min_by_key(|i| i.0)
// If there are no points in the gift, there might
// not be a minimum. Unwrap fails (panics) the program
// if there wasn't a minimum, but we know there always
// is because we checked the size of the gift.
.unwrap()
.clone();

let mut hull = vec![leftmost_point];

let mut point_on_hull = leftmost_point;
loop {
// Search for the next point on the hull
if endpoint == point_on_hull || !turn_counter_clockwise(gift[i], hull[hull.len() - 1], endpoint) {
}
}

point_on_hull = endpoint;

// Stop whenever we got back to the same point
// as we started with, and we wrapped the gift
// completely.
if hull == endpoint {
break;
} else {
hull.push(point_on_hull);
}
}

Some(hull)
}

fn main() {
(-5, 2), (5, 7), (-6, -12), (-14, -14), (9, 9),
(-1, -1), (-10, 11), (-6, 15), (-6, -8), (15, -9),
(7, -7), (-2, -9), (6, -5), (0, 14), (2, 8)
];

println!("The points in the hull are: {:?}", hull);
}

data point(x=0, y=0):
def __str__(self):
return f'({self.x}, {self.y})'

# Is the turn counter-clockwise?
def counter_clockwise(p1 is point, p2 is point, p3 is point) =
(p3.y - p1.y) * (p2.x - p1.x) >= (p2.y - p1.y) * (p3.x - p1.x)

hull = [point_on_hull] # It is guaranteed it will be on the hull.

while True:
# Candidate for the next point in the hull
if (endpoint == point_on_hull
or not counter_clockwise(p, hull[-1], endpoint)):
endpoint = p

point_on_hull = endpoint

# Check if the gift is completely covered.
if hull == endpoint:
return hull
hull.append(point_on_hull)

if __name__ == '__main__':
(-5, 2), (5, 7), (-6, -12), (-14, -14), (9, 9),
(-1, -1), (-10, 11), (-6, 15), (-6, -8), (15, -9),
(7, -7), (-2, -9), (6, -5), (0, 14), (2, 8)
] |> map\$(t -> point(*t)) |> list

print("[#] The points in the hull are:")
for point in hull:
print(point)


##### Text 