Jarvis March

The first two-dimensional convex hull algorithm was originally developed by R. A. Jarvis in 1973 [1]. 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

1Jarvis, 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 readonly int x;
        public readonly int y;

        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
            {
                convexHull.Add(pointOnHull);

                // 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[0]);

            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(1, 3),
                new Vector(2, 4),
                new Vector(4, 0),
                new Vector(1, 0),
                new Vector(0, 2),
                new Vector(2, 2),
                new Vector(3, 4),
                new Vector(3, 1),
            };
            var jarvisMarch = new JarvisMarch();
            var giftWrap = jarvisMarch.Run(points);

            // Print the points of the gift wrap.
            foreach (var point in giftWrap)
                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[1])

    i = 1
    curr_point = points[2]

    # Find cross product between points
    curr_product = jarvis_cross(Pos(0,0), hull[1], curr_point)
    #while (curr_point != hull[1])
    while (length(hull) < 4)
        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 [email protected](xa, ya) [email protected](xb, yb) [email protected](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 [email protected](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[0];

    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[0];

        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[0]));

    return i;
}

int main() {
    struct point points[] = {{0.0, 0.0}, {-1.0, -1.0}, {1.0, 1.0}, {0.0, 1.0},
                                {0.0, -1.0}, {2.0, 2.0}};
    struct point hull_points[6];

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

    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[0]);

  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: 1, y: 3 },
  { x: 2, y: 4 },
  { x: 4, y: 0 },
  { x: 1, y: 0 },
  { x: 0, y: 2 },
  { x: 2, y: 2 },
  { x: 3, y: 4 },
  { x: 3, y: 1 },
];

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[1]-p1[1])*(p2[0]-p1[0]) >= (p2[1]-p1[1])*(p3[0]-p1[0])


def jarvisMarch(gift):
    n = len(gift)  #Number of points in list
    pointOnHull = min(gift) #leftmost point in gift
    hull = [pointOnHull] #leftmost point guaranteed to be in hull

    while True:
        endpoint = gift[0]  #Candidate for next point in hull
        for j in range(1,n):
            if endpoint==pointOnHull or not CCW(gift[j],hull[-1],endpoint):
                endpoint = gift[j]

        pointOnHull = endpoint        

        #Check if we have completely wrapped gift
        if hull[0]==endpoint:
            break
        else:
            hull.append(pointOnHull)

    return hull


def main():
    testGift = [(-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)]
    hull = jarvisMarch(testGift)

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

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 = {
        { 1.0, 3.0 },
        { 1.0, 3.0 },
        { 2.0, 4.0 },
        { 4.0, 0.0 },
        { 1.0, 0.0 },
        { 0.0, 2.0 },
        { 2.0, 2.0 },
        { 3.0, 4.0 },
        { 3.0, 1.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;
    }
}

results matching ""

    No results matching ""