001package algs91; // section 9.8 002import stdlib.*; 003import java.util.Arrays; 004import algs12.Point2D; 005import algs13.Stack; 006/* *********************************************************************** 007 * Compilation: javac GrahamScan.java 008 * Execution: java GrahamScan < input.txt 009 * Dependencies: Point2D.java 010 * 011 * Create points from standard input and compute the convex hull using 012 * Graham scan algorithm. 013 * 014 * May be floating-point issues if x- and y-coordinates are not integers. 015 * 016 * % java GrahamScan < rs1423.txt 017 * (24690.0, 216.0) 018 * (32420.0, 756.0) 019 * (32706.0, 20013.0) 020 * (32373.0, 20274.0) 021 * (31776.0, 20523.0) 022 * (13443.0, 28086.0) 023 * (9252.0, 27747.0) 024 * (8286.0, 27555.0) 025 * (798.0, 22215.0) 026 * (954.0, 11163.0) 027 * (1833.0, 6300.0) 028 * (3804.0, 1017.0) 029 * (11196.0, 504.0) 030 * 031 *************************************************************************/ 032 033public class GrahamScan { 034 private final Stack<Point2D> hull = new Stack<>(); 035 036 public GrahamScan(Point2D[] pts) { 037 038 // defensive copy 039 int N = pts.length; 040 Point2D[] points = new Point2D[N]; 041 for (int i = 0; i < N; i++) 042 points[i] = pts[i]; 043 044 // preprocess so that points[0] has lowest y-coordinate; break ties by x-coordinate 045 // points[0] is an extreme point of the convex hull 046 // (alternatively, could do easily in linear time) 047 Arrays.sort(points); 048 049 // sort by polar angle with respect to base point points[0], 050 // breaking ties by distance to points[0] 051 Arrays.sort(points, 1, N, points[0].POLAR_ORDER); 052 053 hull.push(points[0]); // p[0] is first extreme point 054 055 // find index k1 of first point not equal to points[0] 056 int k1; 057 for (k1 = 1; k1 < N; k1++) 058 if (!points[0].equals(points[k1])) break; 059 if (k1 == N) return; // all points equal 060 061 // find index k2 of first point not collinear with points[0] and points[k1] 062 int k2; 063 for (k2 = k1 + 1; k2 < N; k2++) 064 if (Point2D.ccw(points[0], points[k1], points[k2]) != 0) break; 065 hull.push(points[k2-1]); // points[k2-1] is second extreme point 066 067 // Graham scan; note that points[N-1] is extreme point different from points[0] 068 for (int i = k2; i < N; i++) { 069 Point2D top = hull.pop(); 070 while (Point2D.ccw(hull.peek(), top, points[i]) <= 0) { 071 top = hull.pop(); 072 } 073 hull.push(top); 074 hull.push(points[i]); 075 } 076 077 assert isConvex(); 078 } 079 080 // return extreme points on convex hull in counterclockwise order as an Iterable 081 public Iterable<Point2D> hull() { 082 Stack<Point2D> s = new Stack<>(); 083 for (Point2D p : hull) s.push(p); 084 return s; 085 } 086 087 // check that boundary of hull is strictly convex 088 private boolean isConvex() { 089 int N = hull.size(); 090 if (N <= 2) return true; 091 092 Point2D[] points = new Point2D[N]; 093 int n = 0; 094 for (Point2D p : hull()) { 095 points[n++] = p; 096 } 097 098 for (int i = 0; i < N; i++) { 099 if (Point2D.ccw(points[i], points[(i+1) % N], points[(i+2) % N]) <= 0) { 100 return false; 101 } 102 } 103 return true; 104 } 105 106 // test client 107 public static void main(String[] args) { 108 StdIn.fromFile ("data/rs1423.txt"); 109 110 int N = StdIn.readInt(); 111 Point2D[] points = new Point2D[N]; 112 for (int i = 0; i < N; i++) { 113 int x = StdIn.readInt(); 114 int y = StdIn.readInt(); 115 points[i] = new Point2D(x, y); 116 } 117 GrahamScan graham = new GrahamScan(points); 118 for (Point2D p : graham.hull()) 119 StdOut.println(p); 120 } 121 122}