jules0707

BruteCollinearPoints.java

Nov 24th, 2020
882
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. import edu.princeton.cs.algs4.In;
  2. import edu.princeton.cs.algs4.MergeX;
  3. import edu.princeton.cs.algs4.StdDraw;
  4. import edu.princeton.cs.algs4.StdOut;
  5.  
  6. import java.util.ArrayList;
  7. import java.util.Arrays;
  8. import java.util.Collections;
  9. import java.util.Vector;
  10.  
  11.  
  12. public class BruteCollinearPoints {
  13.  
  14.     /**
  15.      * ArrayList are best to manipulate and store the line segments. HashSets (for uniqueness) are not permitted as per assignments
  16.      * Vectors will enable us to augment the presegment every time we can merge two presegments and they are generics.
  17.      */
  18.     private ArrayList<LineSegment> lineSegments;
  19.     private ArrayList<ArrayList<Point>> segments;
  20.  
  21.     // CONSTRUCTOR finds all line segments containing 4 points
  22.     public BruteCollinearPoints(Point[] points) {
  23.  
  24.         // get those out of the way
  25.         checkNull(points);
  26.         checkDuplicates(points);
  27.  
  28.         lineSegments = new ArrayList<>();
  29.         segments = new ArrayList<>();
  30.         ArrayList<ArrayList<Point>> segmentsCopy;
  31.  
  32.         int n = points.length;
  33.  
  34.         Point[] copySortedPoints = copySort(points); // TO AVOID MUTATING THE ARRAY
  35.  
  36.         /* We compare 4 adjacent points at a time in the array, by comparing their slopes to point[i]
  37.          * a quadruple nested for loop will find all the combinations of N choose 4 in a quadratic (N^4)
  38.          * amortized constant time for adds  which is acceptable as per requirement */
  39.         for (int i = 0; i < n; i++) {
  40.             //we maintain a min and max index to avoid writing duplicate segments
  41.             int min = n - 1;
  42.             int max = 0;
  43.             int mid1 = 0;
  44.             int mid2 = 0;
  45.             double slope1;
  46.             double slope2;
  47.             double slope3;
  48.  
  49.             // we iterate over N choose 4 possible combinations
  50.             for (int j = i + 1; j < n; j++) {
  51.                 slope1 = copySortedPoints[i].slopeTo(copySortedPoints[j]);
  52.                 for (int k = j + 1; k < n; k++) {
  53.                     slope2 = copySortedPoints[i].slopeTo(copySortedPoints[k]);
  54.                     /** If the first 2 slopes are not equals then the 4 points cannot be collinear
  55.                      * and its not worth computing a third slope */
  56.                     if (slope1 == slope2) {
  57.                         // we calculate a third slope
  58.                         for (int p = k + 1; p < n; p++) {
  59.                             slope3 = copySortedPoints[i].slopeTo(copySortedPoints[p]);
  60.                             // we test for collinear points
  61.                             if (slope3 == slope1) {
  62.                                 // we update our min and max indices for this points[i]
  63.                                 min = Math.min(i, min);
  64.                                 max = Math.max(p, max);
  65.                                 mid1 = j;
  66.                                 mid2 = k;
  67.                             }
  68.                         }
  69.                     }
  70.                 }
  71.  
  72.                 /** If all three slopes are equal we have 4 collinear points. We add a new segment.
  73.                  * An intermediary structure useful to filter duplicate points */
  74.                 if (min < max) {
  75.                     Point p1 = copySortedPoints[min];
  76.                     Point p2 = copySortedPoints[mid1];
  77.                     Point p3 = copySortedPoints[mid2];
  78.                     Point p4 = copySortedPoints[max];
  79.  
  80.                     ArrayList<Point> collinearPoints = new ArrayList<>();
  81.                     collinearPoints.add(p1);
  82.                     collinearPoints.add(p2);
  83.                     collinearPoints.add(p3);
  84.                     collinearPoints.add(p4);
  85.  
  86.                     // we make a copy of preSegments to avoid concurrent Modification Exception
  87.                     segmentsCopy = copySortSegments(segments);
  88.  
  89.                     if (!segments.isEmpty()) {
  90.                         /* We traverse preSegments and compare the slopes and merge with the first vector
  91.                          * that has similar slope and at least one point in common */
  92.                         int sum = 0;
  93.                         for (ArrayList<Point> segment : segmentsCopy) {
  94.                             // we check wether exists a presegment that we can merge the newly found collinearPoints with
  95.                             sum += merge(collinearPoints, segment);
  96.                         }
  97.                         // if none is found we write a new presegment
  98.                         if (sum < 1) segments.add(collinearPoints);
  99.                     } else {
  100.                         segments.add(collinearPoints);
  101.                     }
  102.                 }
  103.             }
  104.         }
  105.         createSegments();
  106.     }
  107.  
  108.     private void createSegments() {
  109.         // for each preSegment we extract the min and max
  110.         for (ArrayList<Point> segment : segments) {
  111.             Point[] p = new Point[segment.size()]; // to avoid casting and mutating the array
  112.             MergeX.sort(segment.toArray(p));
  113.             Point minPoint = p[0];
  114.             Point maxPoint = p[segment.size() - 1];
  115.             LineSegment s = new LineSegment(minPoint, maxPoint);
  116.             lineSegments.add(s);
  117.         }
  118.     }
  119.  
  120.  
  121.     private int merge(ArrayList<Point> src, ArrayList<Point> dest) {
  122.         int found = 0;
  123.         // precondition preSeq size and null test
  124.         assert src.size() == 4;
  125.         assert dest.size() >= 4;
  126.  
  127.         double srcSlope = src.get(0).slopeTo(src.get(src.size() - 1));
  128.         double destSlope = dest.get(0).slopeTo(dest.get(dest.size() - 1));
  129.  
  130.         // a copy to avoid mutating the array
  131.         ArrayList<Point> destCopy = copySort(dest);
  132.  
  133.         if (srcSlope == destSlope) {
  134.             for (Point srcPoint : src) {
  135.                 if (found == 0) {
  136.                     for (Point desPoint : destCopy) {
  137.                         // we check if they have one point in common
  138.                         if (srcPoint.compareTo(desPoint) == 0) {
  139.                             // we add all the points to dest in place mutation
  140.                             dest.addAll(src);
  141.                             Collections.sort(dest);
  142.                             // we exit as soon as we find an adequat segment to add it to
  143.                             found = 1;
  144.                             break;
  145.                         }
  146.                     }
  147.                 }
  148.             }
  149.         }
  150.         return found;
  151.     }
  152.  
  153.  
  154.     // Brute sample client - to delete when submitting
  155.     public static void main(String[] args) {
  156.         // read the n points from a file
  157.         In in = new In(args[0]);
  158.         int n = in.readInt();
  159.         Point[] points = new Point[n];
  160.         for (int i = 0; i < n; i++) {
  161.             int x = in.readInt();
  162.             int y = in.readInt();
  163.             points[i] = new Point(x, y);
  164.         }
  165.  
  166.         // draw the points
  167.         StdDraw.enableDoubleBuffering();
  168.         StdDraw.setXscale(0, 32768);
  169.         StdDraw.setYscale(0, 32768);
  170.  
  171.         StdDraw.setPenRadius(0.01);
  172.         StdDraw.setPenColor();
  173.         for (Point p : points) {
  174.             p.draw();
  175.         }
  176.  
  177.         StdDraw.show();
  178.  
  179.         // print and draw the line segments
  180.         BruteCollinearPoints collinear = new BruteCollinearPoints(points);
  181.         LineSegment[] lineSegments = collinear.segments();
  182.  
  183.         for (LineSegment segment : lineSegments) {
  184.             if (null != segment) {
  185.                 StdOut.println(segment);
  186.                 segment.draw();
  187.             }
  188.         }
  189.         StdDraw.show();
  190.     }
  191.  
  192.     private ArrayList<Point> copySort(ArrayList<Point> segment) {
  193.         ArrayList<Point> copy = new ArrayList<>();
  194.         copy.addAll(segment);
  195.         Collections.sort(copy);
  196.         return copy;
  197.     }
  198.  
  199.  
  200.     private ArrayList<ArrayList<Point>> copySortSegments(ArrayList<ArrayList<Point>> segments) {
  201.         ArrayList<ArrayList<Point>> copySortedPreSegments = new ArrayList<>();
  202.  
  203.         for (ArrayList<Point> segment : segments) {
  204.             Collections.sort(segment);
  205.             copySortedPreSegments.add(segment);
  206.         }
  207.         return copySortedPreSegments;
  208.     }
  209.  
  210.     // natural order sort of points
  211.     private Point[] copySort(Point[] points) {
  212.         int n = points.length;
  213.         Point[] copySortedPoints = new Point[n];
  214.         System.arraycopy(points, 0, copySortedPoints, 0, n);
  215.         Arrays.sort(copySortedPoints);
  216.         return copySortedPoints;
  217.     }
  218.  
  219.     // the number of line segments
  220.     public int numberOfSegments() {
  221.         return lineSegments.size();
  222.     }
  223.  
  224.     // the line segments
  225.     public LineSegment[] segments() {
  226.         int l = numberOfSegments();
  227.         LineSegment[] lineSegmentsRes = new LineSegment[l];
  228.         for (int i = 0; i < l; i++) {
  229.             lineSegmentsRes[i] = lineSegments.get(i);
  230.         }
  231.         return lineSegmentsRes;
  232.     }
  233.  
  234.  
  235.     // thanks susutou
  236.     private void checkNull(Point[] points) {
  237.         if (null == points) throw new IllegalArgumentException(
  238.                 "in BruteForceCollinear the Point array cannot be null.");
  239.         else {
  240.             for (Point p : points) {
  241.                 if (null == p) {
  242.                     throw new IllegalArgumentException(
  243.                             "in BruteCollinearPoints.points one of the points is null.");
  244.                 }
  245.             }
  246.         }
  247.     }
  248.  
  249.     // thanks susutou
  250.     private void checkDuplicates(Point[] points) {
  251.         int n = points.length;
  252.         if (n > 0) {
  253.             Point[] pointsCopy = new Point[n];
  254.             System.arraycopy(points, 0, pointsCopy, 0, n);
  255.             Arrays.sort(pointsCopy);
  256.             // only one pass in this combinatorial search since array is already sorted
  257.             for (int i = 0; i < n - 1; i++)
  258.                 //if (pointsCopy[i].compareTo(pointsCopy[i + 1]) == 0)
  259.                 if (pointsCopy[i].compareTo(pointsCopy[i + 1]) == 0)
  260.                     throw new IllegalArgumentException(
  261.                             pointsCopy[i + 1] + "is a duplicate point !");
  262.         }
  263.     }
  264. }
RAW Paste Data