001// Exercise 2.5.25 (Solution published at http://algs4.cs.princeton.edu/)
002package algs12;
003import stdlib.*;
004//import java.util.Arrays;
005import java.util.Comparator;
006/* ***********************************************************************
007 *  Compilation:  javac Point2D.java
008 *
009 *  Immutable point data type for points in the plane.
010 *
011 *************************************************************************/
012
013public class Point2D implements Comparable<Point2D> {
014        public static final Comparator<Point2D> X_ORDER = new XOrder();
015        public static final Comparator<Point2D> Y_ORDER = new YOrder();
016        public static final Comparator<Point2D> R_ORDER = new ROrder();
017
018        public final Comparator<Point2D> POLAR_ORDER = new PolarOrder();
019        public final Comparator<Point2D> ATAN2_ORDER = new Atan2Order();
020        public final Comparator<Point2D> DISTANCE_TO_ORDER = new DistanceToOrder();
021
022        private final double x;    // x coordinate
023        private final double y;    // y coordinate
024
025        // create a new point (x, y)
026        public Point2D(double x, double y) {
027                this.x = x;
028                this.y = y;
029        }
030
031        // return the x-coorindate of this point
032        public double x() { return x; }
033
034        // return the y-coorindate of this point
035        public double y() { return y; }
036
037        // return the radius of this point in polar coordinates
038        public double r() { return Math.sqrt(x*x + y*y); }
039
040        // return the angle of this point in polar coordinates
041        // (between -pi/2 and pi/2)
042        public double theta() { return Math.atan2(y, x); }
043
044        // return the polar angle between this point and that point (between -pi and pi);
045        // (0 if two points are equal)
046        private double angleTo(Point2D that) {
047                double dx = that.x - this.x;
048                double dy = that.y - this.y;
049                return Math.atan2(dy, dx);
050        }
051
052        // is a->b->c a counter-clockwise turn?
053        // -1 if clockwise, +1 if counter-clockwise, 0 if collinear
054        public static int ccw(Point2D a, Point2D b, Point2D c) {
055                double area2 = (b.x-a.x)*(c.y-a.y) - (b.y-a.y)*(c.x-a.x);
056                if      (area2 < 0) return -1;
057                else if (area2 > 0) return +1;
058                else                return  0;
059        }
060
061        // twice signed area of a-b-c
062        public static double area2(Point2D a, Point2D b, Point2D c) {
063                return (b.x-a.x)*(c.y-a.y) - (b.y-a.y)*(c.x-a.x);
064        }
065
066        // return Euclidean distance between this point and that point
067        public double distanceTo(Point2D that) {
068                double dx = this.x - that.x;
069                double dy = this.y - that.y;
070                return Math.sqrt(dx*dx + dy*dy);
071        }
072
073        // return square of Euclidean distance between this point and that point
074        public double distanceSquaredTo(Point2D that) {
075                double dx = this.x - that.x;
076                double dy = this.y - that.y;
077                return dx*dx + dy*dy;
078        }
079
080        // compare by y-coordinate, breaking ties by x-coordinate
081        public int compareTo(Point2D that) {
082                if (this.y < that.y) return -1;
083                if (this.y > that.y) return +1;
084                if (this.x < that.x) return -1;
085                if (this.x > that.x) return +1;
086                return 0;
087        }
088
089        // compare points according to their x-coordinate
090        private static class XOrder implements Comparator<Point2D> {
091                public int compare(Point2D p, Point2D q) {
092                        if (p.x < q.x) return -1;
093                        if (p.x > q.x) return +1;
094                        return 0;
095                }
096        }
097
098        // compare points according to their y-coordinate
099        private static class YOrder implements Comparator<Point2D> {
100                public int compare(Point2D p, Point2D q) {
101                        if (p.y < q.y) return -1;
102                        if (p.y > q.y) return +1;
103                        return 0;
104                }
105        }
106
107        // compare points according to their polar radius
108        private static class ROrder implements Comparator<Point2D> {
109                public int compare(Point2D p, Point2D q) {
110                        double delta = (p.x*p.x + p.y*p.y) - (q.x*q.x + q.y*q.y);
111                        if (delta < 0) return -1;
112                        if (delta > 0) return +1;
113                        return 0;
114                }
115        }
116
117        // compare other points relative to atan2 angle (bewteen -pi/2 and pi/2) they make with this Point
118        private class Atan2Order implements Comparator<Point2D> {
119                public int compare(Point2D q1, Point2D q2) {
120                        double angle1 = angleTo(q1);
121                        double angle2 = angleTo(q2);
122                        if      (angle1 < angle2) return -1;
123                        else if (angle1 > angle2) return +1;
124                        else                      return  0;
125                }
126        }
127
128        // compare other points relative to polar angle (between 0 and 2pi) they make with this Point
129        private class PolarOrder implements Comparator<Point2D> {
130                public int compare(Point2D q1, Point2D q2) {
131                        Trace.draw ();
132                        double dx1 = q1.x - x;
133                        double dy1 = q1.y - y;
134                        double dx2 = q2.x - x;
135                        double dy2 = q2.y - y;
136
137                        if      (dy1 >= 0 && dy2 < 0) return -1;    // q1 above; q2 below
138                        else if (dy2 >= 0 && dy1 < 0) return +1;    // q1 below; q2 above
139                        else if (dy1 == 0 && dy2 == 0) {            // 3-collinear and horizontal
140                                if      (dx1 >= 0 && dx2 < 0) return -1;
141                                else if (dx2 >= 0 && dx1 < 0) return +1;
142                                else                          return  0;
143                        }
144                        else return -ccw(Point2D.this, q1, q2);     // both above or below
145
146                        // Note: ccw() recomputes dx1, dy1, dx2, and dy2
147                }
148        }
149
150        // compare points according to their distance to this point
151        private class DistanceToOrder implements Comparator<Point2D> {
152                public int compare(Point2D p, Point2D q) {
153                        double dist1 = distanceSquaredTo(p);
154                        double dist2 = distanceSquaredTo(q);
155                        if      (dist1 < dist2) return -1;
156                        else if (dist1 > dist2) return +1;
157                        else                    return  0;
158                }
159        }
160
161
162        // does this point equal y?
163        public boolean equals(Object other) {
164                if (other == this) return true;
165                if (other == null) return false;
166                if (other.getClass() != this.getClass()) return false;
167                Point2D that = (Point2D) other;
168                // Don't use == here if x or y could be NaN or -0
169                if (Double.compare(this.x,that.x) != 0) return false;
170                if (Double.compare(this.y,that.y) != 0) return false;
171                return true;
172        }
173
174        // must override hashcode if you override equals
175        // See Item 9 of Effective Java (2e) by Joshua Block
176        private volatile int hashCode;
177        public int hashCode() {
178                int result = hashCode;
179                if (result == 0) {
180                        result = 17;
181                        result = 31*result + Double.hashCode(x);
182                        result = 31*result + Double.hashCode(y);
183                        hashCode = result;
184                }
185                return result;
186        }
187
188        // convert to string
189        public String toString() {
190                return "(" + x + "," + y + ")";
191        }
192
193        // plot using StdDraw
194        public void draw() {
195                StdDraw.point(x, y);
196        }
197
198        // draw line from this point p to q using StdDraw
199        public void drawTo(Point2D that) {
200                StdDraw.line(this.x, this.y, that.x, that.y);
201        }
202
203
204        public static void main(String[] args) {
205                Trace.run ();
206                Point2D origin = new Point2D (0, 0);
207                Point2D a = new Point2D (1, -1);
208                Point2D b = new Point2D (-1, 1);
209                
210                StdOut.println (origin.POLAR_ORDER.compare (a, b));
211                
212                
213//              args = new String[] { "20", "20", "100" };
214//              
215//              int x0 = Integer.parseInt(args[0]);
216//              int y0 = Integer.parseInt(args[1]);
217//              int N = Integer.parseInt(args[2]);
218//
219//              StdDraw.setCanvasSize(800, 800);
220//              StdDraw.setXscale(0, 100);
221//              StdDraw.setYscale(0, 100);
222//              StdDraw.setPenRadius(.005);
223//              Point2D[] points = new Point2D[N];
224//              for (int i = 0; i < N; i++) {
225//                      int x = StdRandom.uniform(100);
226//                      int y = StdRandom.uniform(100);
227//                      points[i] = new Point2D(x, y);
228//                      points[i].draw();
229//              }
230//
231//              // draw p = (x0, x1) in red
232//              Point2D p = new Point2D(x0, y0);
233//              StdDraw.setPenColor(StdDraw.RED);
234//              StdDraw.setPenRadius(.02);
235//              p.draw();
236//
237//
238//              // draw line segments from p to each point, one at a time, in polar order
239//              StdDraw.setPenRadius();
240//              StdDraw.setPenColor(StdDraw.BLUE);
241//              Arrays.sort(points, p.POLAR_ORDER);
242//              for (int i = 0; i < N; i++) {
243//                      p.drawTo(points[i]);
244//                      StdDraw.show(100);
245//              }
246        }
247}