@Test public void basicTest() { List<Point2D> expectInput = new ArrayList<>(); expectInput.add(new Point2D(1, 1)); expectInput.add(new Point2D(0, 0)); expectInput.add(new Point2D(2, 2)); List<Point2D> testInput = new ArrayList<>(expectInput); GrahamScan expect = new GrahamScan(expectInput.toArray(new Point2D[0])); List<Point2D> test = ConvexHull.solve(testInput); int i = 0; for (Point2D p : expect.hull()) { assertTrue(test.get(i).equals(p)); i++; } }
public static List<Point2D> solve(List<Point2D> input) { List<Point2D> points = new ArrayList<>(new HashSet<>(input)); int upmost = 0; for (int i = 1; i < points.size(); i++) { int compare = Double.compare(points.get(i).y(), points.get(upmost).y()); if (compare < 0) { upmost = i; } else if (compare == 0 && points.get(i).x() < points.get(upmost).x()) { upmost = i; } } List<Point2D> preResult = new ArrayList<>(); preResult.add(points.get(upmost)); int p = upmost; while (true) { int q = (p + 1) % points.size(); for (int i = 0; i < points.size(); i++) { int ccw = ccw(points.get(p), points.get(i), points.get(q)); if (ccw > 0) { q = i; } } if (q == upmost) break; preResult.add(points.get(q)); p = q; } return preResult; }
ConvexHull { public static List<Point2D> solve(List<Point2D> input) { List<Point2D> points = new ArrayList<>(new HashSet<>(input)); int upmost = 0; for (int i = 1; i < points.size(); i++) { int compare = Double.compare(points.get(i).y(), points.get(upmost).y()); if (compare < 0) { upmost = i; } else if (compare == 0 && points.get(i).x() < points.get(upmost).x()) { upmost = i; } } List<Point2D> preResult = new ArrayList<>(); preResult.add(points.get(upmost)); int p = upmost; while (true) { int q = (p + 1) % points.size(); for (int i = 0; i < points.size(); i++) { int ccw = ccw(points.get(p), points.get(i), points.get(q)); if (ccw > 0) { q = i; } } if (q == upmost) break; preResult.add(points.get(q)); p = q; } return preResult; } }
ConvexHull { public static List<Point2D> solve(List<Point2D> input) { List<Point2D> points = new ArrayList<>(new HashSet<>(input)); int upmost = 0; for (int i = 1; i < points.size(); i++) { int compare = Double.compare(points.get(i).y(), points.get(upmost).y()); if (compare < 0) { upmost = i; } else if (compare == 0 && points.get(i).x() < points.get(upmost).x()) { upmost = i; } } List<Point2D> preResult = new ArrayList<>(); preResult.add(points.get(upmost)); int p = upmost; while (true) { int q = (p + 1) % points.size(); for (int i = 0; i < points.size(); i++) { int ccw = ccw(points.get(p), points.get(i), points.get(q)); if (ccw > 0) { q = i; } } if (q == upmost) break; preResult.add(points.get(q)); p = q; } return preResult; }  }
ConvexHull { public static List<Point2D> solve(List<Point2D> input) { List<Point2D> points = new ArrayList<>(new HashSet<>(input)); int upmost = 0; for (int i = 1; i < points.size(); i++) { int compare = Double.compare(points.get(i).y(), points.get(upmost).y()); if (compare < 0) { upmost = i; } else if (compare == 0 && points.get(i).x() < points.get(upmost).x()) { upmost = i; } } List<Point2D> preResult = new ArrayList<>(); preResult.add(points.get(upmost)); int p = upmost; while (true) { int q = (p + 1) % points.size(); for (int i = 0; i < points.size(); i++) { int ccw = ccw(points.get(p), points.get(i), points.get(q)); if (ccw > 0) { q = i; } } if (q == upmost) break; preResult.add(points.get(q)); p = q; } return preResult; }  static List<Point2D> solve(List<Point2D> input); static int ccw(Point2D a, Point2D b, Point2D c); }
ConvexHull { public static List<Point2D> solve(List<Point2D> input) { List<Point2D> points = new ArrayList<>(new HashSet<>(input)); int upmost = 0; for (int i = 1; i < points.size(); i++) { int compare = Double.compare(points.get(i).y(), points.get(upmost).y()); if (compare < 0) { upmost = i; } else if (compare == 0 && points.get(i).x() < points.get(upmost).x()) { upmost = i; } } List<Point2D> preResult = new ArrayList<>(); preResult.add(points.get(upmost)); int p = upmost; while (true) { int q = (p + 1) % points.size(); for (int i = 0; i < points.size(); i++) { int ccw = ccw(points.get(p), points.get(i), points.get(q)); if (ccw > 0) { q = i; } } if (q == upmost) break; preResult.add(points.get(q)); p = q; } return preResult; }  static List<Point2D> solve(List<Point2D> input); static int ccw(Point2D a, Point2D b, Point2D c);  }