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}