jules0707

FastCollinearPoints.java

Nov 24th, 2020 (edited)
580
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. /*
  2. Correctness:  41/41 tests passed
  3. Memory:       1/1 tests passed
  4. Timing:       41/41 tests passed
  5. Aggregate score: 100.00%*/
  6.  
  7. import edu.princeton.cs.algs4.In;
  8. import edu.princeton.cs.algs4.StdDraw;
  9. import edu.princeton.cs.algs4.StdOut;
  10.  
  11. import java.util.ArrayList;
  12. import java.util.Arrays;
  13. import java.util.Comparator;
  14.  
  15.  
  16. public class FastCollinearPoints {
  17.  
  18.     // since HashSets are not permitted as per assignments
  19.     private ArrayList<LineSegment> lineSegments;
  20.  
  21.     // finds all line segments containing 4 points
  22.     public FastCollinearPoints(Point[] points) {
  23.  
  24.         checkNull(points);
  25.         checkDuplicates(points);
  26.         lineSegments = new ArrayList<>();
  27.         int n = points.length;
  28.         Point[] copyPoints = points.clone(); // TO AVOID MUTATING THE ARRAY
  29.  
  30.         for (int i = 0; i < n - 3; i++) {
  31.             Arrays.sort(copyPoints); // resort as order has been modified by subsequent BY_SLOPE_ORDER call
  32.             // for each point we sort the points array by slope order
  33.             Comparator<Point> BY_SLOPE_ORDER = copyPoints[i].slopeOrder();
  34.             Arrays.sort(copyPoints, BY_SLOPE_ORDER);
  35.  
  36.             // we check if the next 2 points in the slope sorted array have equal slopes with respect to this point
  37. // this double cursor allows to find segments greater than 4 in length without the costly operation of merging and recomputing some slopes for aligned segments which will end up being too slow
  38.             for (int origine = 0, first = 1, last = 2; last < n; last++) { // thanks  AlexJoz
  39.  
  40.                 while (last < n && copyPoints[origine].slopeTo(copyPoints[first]) == copyPoints[origine].slopeTo(copyPoints[last])) {
  41.                     last++;
  42.                 }
  43.  
  44.                 if (last - first >= 3 && copyPoints[origine].compareTo(copyPoints[first]) < 0) { // to avoid writing duplicates segments
  45.                     lineSegments.add(new LineSegment(copyPoints[origine], copyPoints[last - 1]));
  46.                 }
  47.                 first = last; // search for the next aligned points
  48.             }
  49.         }
  50.     }
  51.  
  52.     private void checkDuplicates(Point[] points) {
  53.         int n = points.length;
  54.         if (n > 0) {
  55.             Point[] pointsCopy = new Point[n];
  56.             System.arraycopy(points, 0, pointsCopy, 0, n);
  57.             Arrays.sort(pointsCopy);
  58.             // only one pass in this search since array is already sorted
  59.             for (int i = 0; i < n - 1; i++)
  60.                 if (pointsCopy[i].compareTo(pointsCopy[i + 1]) == 0)
  61.                     throw new IllegalArgumentException(
  62.                             pointsCopy[i + 1] + "is a duplicate point !");
  63.         }
  64.     }
  65.  
  66.     private void checkNull(Point[] points) {
  67.         if (points == null) {
  68.             throw new IllegalArgumentException("in FastCollinear the Point array cannot be null.");
  69.         } else {
  70.             for (Point p : points) {
  71.                 if (p == null) {
  72.                     throw new IllegalArgumentException(
  73.                             "in FastCollinear one point in points is null.");
  74.                 }
  75.             }
  76.         }
  77.     }
  78.  
  79.      // the number of line segments
  80.     public int numberOfSegments() {
  81.         return lineSegments.size();
  82.     }
  83.  
  84.     // the line segments
  85.     public LineSegment[] segments() {
  86.         LineSegment[] lineSegmentsRes = new LineSegment[numberOfSegments()];
  87.         for (int i = 0; i < numberOfSegments(); i++) {
  88.             lineSegmentsRes[i] = lineSegments.get(i);
  89.         }
  90.         return lineSegmentsRes;
  91.     }
  92.  
  93.     // FastCollinearPoints sample client - to delete when submitting
  94.     public static void main(String[] args) {
  95.         // read the n points from a file
  96.         In in = new In(args[0]);
  97.         int n = in.readInt();
  98.         Point[] points = new Point[n];
  99.         for (int i = 0; i < n; i++) {
  100.             int x = in.readInt();
  101.             int y = in.readInt();
  102.             points[i] = new Point(x, y);
  103.         }
  104.         // draw the points
  105.         StdDraw.enableDoubleBuffering();
  106.         StdDraw.setXscale(0, 32768);
  107.         StdDraw.setYscale(0, 32768);
  108.         StdDraw.setPenColor();
  109.         StdDraw.setPenRadius(0.01);
  110.         for (Point p : points) {
  111.             p.draw();
  112.         }
  113.         StdDraw.show();
  114.         // print and draw the line segments
  115.         FastCollinearPoints collinear = new FastCollinearPoints(points);
  116.         LineSegment[] lineSegments = collinear.segments();
  117.  
  118.         for (LineSegment segment : lineSegments) {
  119.             if (null != segment) {
  120.                 StdOut.println(segment);
  121.                 segment.draw();
  122.             }
  123.         }
  124.         StdDraw.show();
  125.     }
  126. }
RAW Paste Data