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}