Question
I need helpwriting this code in java. Please help!!
In this assignment, you will be required to write code to implement Graham's scan to solve the convex hull problem. You will be given a set of points that you would have to read from a text file. File should look like: 3, 4 1, 10 7, 9 ...
Where each line represents a point (first number is the x-coordinate and the second number is the y-coordinate)
Here's a rough outline of the steps that you will need to perform:
Read all the points and add them to an array of a user-defined Class 'Point'
Find the point with the least x value (left-most point)
Make the left-most point 0,0 and shift/transform all other points accordingly (for example, if the left-most point is (-5, -2), then a second point that has coordinate (1, 3) will have new coordinate (1-(-5), 3-(-2)) which would be (6, 5)
Now sort all the points according to their orientation (details on how to do that provided in the convex hull video)
To sort an array of Points according to their orientation, you will need to override the compareTo function in the Class Point to specify how two points will be compared (in this case they will be compared by their orientation to each other). Google how to override compareTo for more details in case you haven't done it before. You can also ask me or the TA if you're stuck or you could ask us questions in the coming Hangout
Next you create a stack (and any other needed data structure) and follow Graham's scan as explained in the video and in the notes.
The notes outline a stet-by-step of how Grahams' scan algorithm works.
Finally, print the output of Graham's scan, which is the list of points (in order) that surround all other points
Explanation / Answer
import java.util.Arrays; import java.util.Comparator; import java.util.Scanner; import java.util.Stack; class Point2D implements Comparable { public static final Comparator X_ORDER = new XOrder(); public static final Comparator Y_ORDER = new YOrder(); public static final Comparator R_ORDER = new ROrder(); public final Comparator POLAR_ORDER = new PolarOrder(); public final Comparator ATAN2_ORDER = new Atan2Order(); public final Comparator DISTANCE_TO_ORDER = new DistanceToOrder(); private final double x; // x coordinate private final double y; // y coordinate public Point2D(double x, double y) { if (Double.isInfinite(x) || Double.isInfinite(y)) throw new IllegalArgumentException("Coordinates must be finite"); if (Double.isNaN(x) || Double.isNaN(y)) throw new IllegalArgumentException("Coordinates cannot be NaN"); if (x == 0.0) x = 0.0; // convert -0.0 to +0.0 if (y == 0.0) y = 0.0; // convert -0.0 to +0.0 this.x = x; this.y = y; } public double x() { return x; } public double y() { return y; } public double r() { return Math.sqrt(x * x + y * y); } public double theta() { return Math.atan2(y, x); } private double angleTo(Point2D that) { double dx = that.x - this.x; double dy = that.y - this.y; return Math.atan2(dy, dx); } public static int ccw(Point2D a, Point2D b, Point2D c) { double area2 = (b.x - a.x) * (c.y - a.y) - (b.y - a.y) * (c.x - a.x); if (area2 < 0) return -1; else if (area2 > 0) return +1; else return 0; } public static double area2(Point2D a, Point2D b, Point2D c) { return (b.x - a.x) * (c.y - a.y) - (b.y - a.y) * (c.x - a.x); } public double distanceTo(Point2D that) { double dx = this.x - that.x; double dy = this.y - that.y; return Math.sqrt(dx * dx + dy * dy); } public double distanceSquaredTo(Point2D that) { double dx = this.x - that.x; double dy = this.y - that.y; return dx * dx + dy * dy; } public int compareTo(Point2D that) { if (this.y that.y) return +1; if (this.x that.x) return +1; return 0; } private static class XOrder implements Comparator { public int compare(Point2D p, Point2D q) { if (p.x q.x) return +1; return 0; } } private static class YOrder implements Comparator { public int compare(Point2D p, Point2D q) { if (p.y q.y) return +1; return 0; } } private static class ROrder implements Comparator { public int compare(Point2D p, Point2D q) { double delta = (p.x * p.x + p.y * p.y) - (q.x * q.x + q.y * q.y); if (delta < 0) return -1; if (delta > 0) return +1; return 0; } } private class Atan2Order implements Comparator { public int compare(Point2D q1, Point2D q2) { double angle1 = angleTo(q1); double angle2 = angleTo(q2); if (angle1 angle2) return +1; else return 0; } } private class PolarOrder implements Comparator { public int compare(Point2D q1, Point2D q2) { double dx1 = q1.x - x; double dy1 = q1.y - y; double dx2 = q2.x - x; double dy2 = q2.y - y; if (dy1 >= 0 && dy2 < 0) return -1; // q1 above; q2 below else if (dy2 >= 0 && dy1 < 0) return +1; // q1 below; q2 above else if (dy1 == 0 && dy2 == 0) { // 3-collinear and horizontal if (dx1 >= 0 && dx2 < 0) return -1; else if (dx2 >= 0 && dx1 < 0) return +1; else return 0; } else return -ccw(Point2D.this, q1, q2); // both above or below } } private class DistanceToOrder implements Comparator { public int compare(Point2D p, Point2D q) { double dist1 = distanceSquaredTo(p); double dist2 = distanceSquaredTo(q); if (dist1 dist2) return +1; else return 0; } } public boolean equals(Object other) { if (other == this) return true; if (other == null) return false; if (other.getClass() != this.getClass()) return false; Point2D that = (Point2D) other; return this.x == that.x && this.y == that.y; } public String toString() { return "(" + x + ", " + y + ")"; } public int hashCode() { int hashX = ((Double) x).hashCode(); int hashY = ((Double) y).hashCode(); return 31 * hashX + hashY; } } public class GrahamScan { private Stack hull = new Stack(); public GrahamScan(Point2D[] pts) { // defensive copy int N = pts.length; Point2D[] points = new Point2D[N]; for (int i = 0; i