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])
        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;
    }
}
;;;; 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)))))

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

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

(defun jarvis-march (gift)
  "finds the convex hull of any distribution of points"
  ;deals with the edge cases
  (if (< (length gift) 3)
    gift
    (loop
      with start = (leftmost-point gift)
      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))))))

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

(print (jarvis-march gift))
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;
            }
        }
        hull.add(pointOnHull);

        //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 {
                hull.add(pointOnHull);
            }
        }
        return hull;
    }

    public static void main(String[] args) {

        //test array setup
        ArrayList<Point> gift = new ArrayList<Point>();
        gift.add(new Point(-5, 2));
        gift.add(new Point(5, 7));
        gift.add(new Point(-6, -12));
        gift.add(new Point(-14, -14));
        gift.add(new Point(9, 9));
        gift.add(new Point(-1, -1));
        gift.add(new Point(-10, 11));
        gift.add(new Point(-6, 15));
        gift.add(new Point(-6, -8));
        gift.add(new Point(15, -9));
        gift.add(new Point(7, -7));
        gift.add(new Point(-2, -9));
        gift.add(new Point(6, -5));
        gift.add(new Point(0, 14));
        gift.add(new Point(2, 8));

        //print initial array of points
        System.out.println("Gift:");
        for (Point p: gift) {
            System.out.println("[" + p.getX() + ", " + p.getY() + "]");
        }

        //find and print the array of points in the hull
        ArrayList<Point> hull = jarvisMarch(gift);
        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[0]

    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.x
}

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

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

        hullPoint = endPoint

        if endPoint.equal(hullPoints[0]) {
            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)
    }
}

results matching ""

    No results matching ""