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