# GrahamScanNondegenerate.java

Below is the syntax highlighted version of GrahamScanNondegenerate.java from §9.9 Convex Hull.

```/******************************************************************************
*  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.
*
******************************************************************************/

import java.util.Arrays;

public class GrahamScanNondegenerate {
private Stack<Point2D> hull = new Stack<Point2D>();

public GrahamScanNondegenerate(Point2D[] points) {
// defensive copy
int n = points.length;
if (n <= 2) throw new RuntimeException("Requires at least 3 points");
Point2D[] a = new Point2D[n];
for (int i = 0; i < n; i++)
a[i] = points[i];

// preprocess so that a has lowest y-coordinate; break ties by x-coordinate
// a is an extreme point of the convex hull
// (could do easily in linear time)
Arrays.sort(a, Point2D.Y_ORDER);

// sort by polar angle with respect to base point a.
// (no ties because of general position assumption)
Arrays.sort(a, 1, n, a.polarOrder());

// a and a are extreme points (a because of general position)
hull.push(a);
hull.push(a);

// 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, a[i]) <= 0) {
top = hull.pop();
}
hull.push(top);
hull.push(a[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<Point2D> hull() {
Stack<Point2D> s = new Stack<Point2D>();
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 k = 0;
for (Point2D p : hull()) {
points[k++] = p;
}

// needs to check i = 1 and i = 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) {
Point2D[] points = new Point2D[n];
for (int i = 0; i < n; i++) {