@Test public void test2() { Point[] points = { new Point(0, 3), new Point(4, 2), new Point(3, 5), new Point(5, 3), new Point(3, 0), new Point(1, 1), new Point(1, 2), new Point(2, 2) }; List<Point> result = Jarvis.convexHull(Arrays.asList(points)); Assert.assertEquals(5, result.size()); Assert.assertEquals(new Point(0, 3), result.get(0)); Assert.assertEquals(new Point(3, 5), result.get(1)); Assert.assertEquals(new Point(5, 3), result.get(2)); Assert.assertEquals(new Point(3, 0), result.get(3)); Assert.assertEquals(new Point(1, 1), result.get(4)); }
public static List<Point> convexHull(List<Point> points) { if (points.size() < 3) { return null; } List<Point> ch = new ArrayList<>(); Point left = findLeftMost(points); Point current = left; do { ch.add(current); Point next = null; for (Point p : points) { if (next == null) { next = p; continue; } int cp = crossProduct(current, p, next); if (cp > 0 || (cp == 0 && current.distanceTo(p) > current.distanceTo(next))) { next = p; } } if (next == null) { return null; } assert ch.size() <= points.size() : "hull has more points than graph"; current = next; } while (current != left); return ch; }
Jarvis { public static List<Point> convexHull(List<Point> points) { if (points.size() < 3) { return null; } List<Point> ch = new ArrayList<>(); Point left = findLeftMost(points); Point current = left; do { ch.add(current); Point next = null; for (Point p : points) { if (next == null) { next = p; continue; } int cp = crossProduct(current, p, next); if (cp > 0 || (cp == 0 && current.distanceTo(p) > current.distanceTo(next))) { next = p; } } if (next == null) { return null; } assert ch.size() <= points.size() : "hull has more points than graph"; current = next; } while (current != left); return ch; } }
Jarvis { public static List<Point> convexHull(List<Point> points) { if (points.size() < 3) { return null; } List<Point> ch = new ArrayList<>(); Point left = findLeftMost(points); Point current = left; do { ch.add(current); Point next = null; for (Point p : points) { if (next == null) { next = p; continue; } int cp = crossProduct(current, p, next); if (cp > 0 || (cp == 0 && current.distanceTo(p) > current.distanceTo(next))) { next = p; } } if (next == null) { return null; } assert ch.size() <= points.size() : "hull has more points than graph"; current = next; } while (current != left); return ch; }  }
Jarvis { public static List<Point> convexHull(List<Point> points) { if (points.size() < 3) { return null; } List<Point> ch = new ArrayList<>(); Point left = findLeftMost(points); Point current = left; do { ch.add(current); Point next = null; for (Point p : points) { if (next == null) { next = p; continue; } int cp = crossProduct(current, p, next); if (cp > 0 || (cp == 0 && current.distanceTo(p) > current.distanceTo(next))) { next = p; } } if (next == null) { return null; } assert ch.size() <= points.size() : "hull has more points than graph"; current = next; } while (current != left); return ch; }  static List<Point> convexHull(List<Point> points); }
Jarvis { public static List<Point> convexHull(List<Point> points) { if (points.size() < 3) { return null; } List<Point> ch = new ArrayList<>(); Point left = findLeftMost(points); Point current = left; do { ch.add(current); Point next = null; for (Point p : points) { if (next == null) { next = p; continue; } int cp = crossProduct(current, p, next); if (cp > 0 || (cp == 0 && current.distanceTo(p) > current.distanceTo(next))) { next = p; } } if (next == null) { return null; } assert ch.size() <= points.size() : "hull has more points than graph"; current = next; } while (current != left); return ch; }  static List<Point> convexHull(List<Point> points);  }