Skip to content

Instantly share code, notes, and snippets.

@figraham figraham/JarvisMarch.pde
Last active Jun 28, 2019

Embed
What would you like to do?
Jarvis March Algorithm, also known as gift wrapping. Coding in Processing / Java and inspired by thecodingtrain.com computational geomentry.
import java.util.*;
ArrayList<PVector> jarvisMarch(ArrayList<PVector> _input) throws InvalidJarvisInputException {
if (_input.size() < 3) throw new InvalidJarvisInputException("Input must have at least 3 PVectors in the list.");
ArrayList<PVector> output = new ArrayList<PVector>();
ArrayList<PVector> input = deepCopyArrayListPVector(_input);
Collections.sort(input, new leftSorter());
output.add(input.get(0));
int current = 0; // index into output
int next = 1; // index into input
while (true) {
for (int i = 1; i < input.size(); i++) {
PVector a = input.get(next).copy().sub(output.get(current));
PVector b = input.get(i).copy().sub(output.get(current));
PVector cross = a.cross(b);
if ( cross.z < 0 || (cross.z == 0 && b.mag() > a.mag()) ) {
next = i;
}
}
if (next == 0) break;
output.add(input.get(next));
current++;
input.remove(output.get(current));
next = 0;
}
return output;
}
class InvalidJarvisInputException extends Exception {
InvalidJarvisInputException(String message) {
super("ERROR: Invalid Arguments for jarvisMarch(). " + message);
}
}
class leftSorter implements Comparator<PVector> {
int compare(PVector a, PVector b) {
return round(a.x - b.x);
}
}
ArrayList<PVector> deepCopyArrayListPVector(ArrayList<PVector> ls) {
ArrayList<PVector> cp = new ArrayList<PVector>(ls.size());
for (PVector v : ls) {
cp.add(v.copy());
}
return cp;
}
int WIDTH = 600;
int HEIGHT = 600;
ArrayList<PVector> points = new ArrayList<PVector>();
ArrayList<PVector> hull;
void settings() {
size(WIDTH, HEIGHT);
}
void setup() {
int padding = width / 8;
for (int i = 0; i < 25; i++) {
points.add(new PVector(random(padding, width - padding), random(padding, height - padding)));
}
try {
hull = jarvisMarch(points);
} catch (Exception e) {
e.printStackTrace();
exit();
}
}
void draw() {
beginShape();
for (int i = 0; i < hull.size(); i++) {
vertex(hull.get(i).x, hull.get(i).y);
}
endShape(CLOSE);
for (int i = 0; i < points.size(); i++) {
circle(points.get(i).x, points.get(i).y, 3);
}
noLoop();
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
You can’t perform that action at this time.