@Test public void testCollinear() { Point[] points = new Point[] { new Point(604, 76), new Point(609, 81), new Point(606, 78), new Point(602, 74), new Point(610, 74), new Point(609, 77), new Point(602, 72), new Point(606, 77), new Point(611, 77), new Point(607, 72), new Point(616, 74), new Point(611, 70), new Point(611, 71), new Point(610, 73), new Point(614, 82), new Point(615, 79), new Point(615, 77), new Point(615, 76), new Point(634, 71), new Point(604, 76) }; Jarvis.convexHull(Arrays.asList(points)); }
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);  }