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}