``` 001 002 003 004 005 006 007 008 009 010 011 012 013 014 015 016 017 018 019 020 021 022 023 024 025 026 027 028 029 030 031 032 033 034 035 036 037 038 039 040 041 042 043 044 045 046 047 048 049 050 051 052 053 054 055 056 057 058 059 060 061 062 063 064 065 066 067 068 069 070 071 072 073 074 075 076 077 078 079 080 081 082 083 084 085 086 087 088 089 090 091 092 093 094 095 096 097 098 099 100 101 102 103 104 105 106 107 108 ``` ```package algs9; // section 9.8 import stdlib.*; import java.util.Arrays; import algs12.Point2D; import algs13.Stack; /* *********************************************************************** * Compilation: javac GrahamaScanNondegenerate.java * Execution: java GrahamNondegenerate < input.txt * Dependencies: Point2D.java Stack.java * * Read points from standard input and compute their convex hull * using Graham's algorithm. * * Returns the extreme points of the convex hull in counterclockwise * order (starting with the point with smallest y-coordinate). * * Non-degeneracy assumption * ------------------------- * - at least 3 points * - no coincident points * - no 3 collinear points * * GrahamScan.java removes these degeneracy assumptions. * *************************************************************************/ public class XGrahamScanNondegenerate { private final Stack hull = new Stack<>(); public XGrahamScanNondegenerate(Point2D[] points) { // defensive copy int N = points.length; if (N <= 2) throw new Error("Requires at least 3 points"); Point2D[] p = new Point2D[N]; for (int i = 0; i < N; i++) p[i] = points[i]; // preprocess so that p has lowest y-coordinate; break ties by x-coordinate // p is an extreme point of the convex hull // (could do easily in linear time) Arrays.sort(p, Point2D.Y_ORDER); // sort by polar angle with respect to base point p. // (no ties because of general position assumption) Arrays.sort(p, 1, N, p.POLAR_ORDER); // p and p are extreme points (p because of general position) hull.push(p); hull.push(p); // Graham scan for (int i = 2; i < N; i++) { Point2D top = hull.pop(); // could replace >= with > since no three collinear // could replace unnecessary popping/pushing with peekpeek() while (Point2D.ccw(hull.peek(), top, p[i]) <= 0) { top = hull.pop(); } hull.push(top); hull.push(p[i]); } assert isConvex(); } // return extreme points on convex hull in counterclockwise order as an Iterable // (no need to reverse if we want to return in clockwise order) public Iterable hull() { Stack s = new Stack<>(); for (Point2D p : hull) s.push(p); return s; } // check that boundary of hull is strictly convex private boolean isConvex() { int N = hull.size(); Point2D[] points = new Point2D[N]; int n = 0; for (Point2D p : hull()) { points[n++] = p; } // needs to check N = 1 and N = 2 cases if not in general position for (int i = 0; i < N; i++) { if (Point2D.ccw(points[i], points[(i+1) % N], points[(i+2) % N]) <= 0) { return false; } } return true; } // test client public static void main(String[] args) { int N = StdIn.readInt(); Point2D[] points = new Point2D[N]; for (int i = 0; i < N; i++) { int x = StdIn.readInt(); int y = StdIn.readInt(); points[i] = new Point2D(x, y); } XGrahamScanNondegenerate graham = new XGrahamScanNondegenerate(points); for (Point2D p : graham.hull()) StdOut.println(p); } } ```