Java Code

FastCollinearPoints.java

import java.util.Arrays;
import java.util.ArrayList;
import edu.princeton.cs.algs4.StdDraw;
import edu.princeton.cs.algs4.StdOut;
import edu.princeton.cs.algs4.StdIn;
import edu.princeton.cs.algs4.In;

public class FastCollinearPoints {
    private int N=0;
    private ArrayList<LineSegment> segments = new ArrayList<LineSegment>();
    private Point[] orderedCopy;
    private ArrayList<Point> tempArray = new ArrayList<Point>();

    public FastCollinearPoints(Point[] points) {
        // Constructor for fast collinear class. First sort the array of
        // Point objects by natural order. Then iterate through that array.
        // We first create a copy of the array and then we sort that array
        // using the Comparator method SLOPE_ORDER. Then we scan through the
        // array to look for groups of points with the same slope. If that
        // group reaches greater than 3 points we then check to see if the
        // smallest point in that array is bigger than our pivot Point. If it
        // is then it is a valid segment.
        if (points == null) {
            throw new java.lang.NullPointerException();
        }

        orderedCopy = points.clone(); 
        // Sort by natural order
        Arrays.sort(points);
         
        for(int i=0; i<points.length; i++) {
            tempArray.clear();
            // Make copy of natural ordered copy
            orderedCopy = points.clone(); //working copy
            Point base = orderedCopy[i];
            Arrays.sort(orderedCopy,base.SLOPE_ORDER);
            
            //double currentSlope = base.slopeTo(orderedCopy[1]); 

            for(int p=1; p<points.length-1;p++) {
                double currentSlope = base.slopeTo(orderedCopy[p]);
                double nextSlope = base.slopeTo(orderedCopy[p+1]);

                //TODO: Something is wrong here.
                if (nextSlope == currentSlope) {
                    tempArray.add(orderedCopy[p]);
                    tempArray.add(orderedCopy[p+1]);
                }
                //else {
                //    currentSlope = nextSlope;
                //}
            }
            //TODO: Fix this so it doesn't give index out of range
            if (tempArray.size() > 2) {
                int comparison = base.compareTo(tempArray.get(0)); 
                if(comparison < 0) {
                    segments.add(new LineSegment(base,
                                tempArray.get(tempArray.size()-1)));
                }
            }
        }
    }
       
    public int numberOfSegments() {
        // the number of line segment
        return N;
    }

    public LineSegment[] segments() {
        return segments.toArray(new LineSegment[segments.size()]);// the line segments
    }

    public static void main(String[] args) {
        In in = new In(args[0]);
        int N = in.readInt();
        Point[] points = new Point[N];

        for(int i = 0; i<N; i++) {
            int x = in.readInt();
            int y = in.readInt();

            points[i] = new Point(x, y);
        }
        Point[] copyArray;
        Point[] slopeArray;
        copyArray = points.clone();
        slopeArray = points.clone();
        
        Arrays.sort(copyArray);
        
        StdDraw.show(0);
        StdDraw.setXscale(0, 32768);
        StdDraw.setYscale(0,32768);
        for( Point p : points) {
            p.draw();
        }
        StdDraw.show();
        //for(int i=0;i<N;i++) {
        //    StdOut.print(copyArray[i]);
        //    StdOut.print(" ");
        //}
        //StdOut.println();
        //Arrays.sort(copyArray, copyArray[1].SLOPE_ORDER); 

        //for(int i=0;i<N;i++) {
        //    StdOut.print(copyArray[i]);
        //    StdOut.print(" ");
        //}
        //StdOut.println();
            
        FastCollinearPoints fast = new FastCollinearPoints(points);
         
        for( LineSegment segment : fast.segments() )
        {
            StdOut.println(segment);
            segment.draw();
        }

    }
}