FastCollinearPoints.java

import edu.princeton.cs.algs4.In;
import edu.princeton.cs.algs4.StdDraw;
import edu.princeton.cs.algs4.StdOut;

import java.util.ArrayList;
import java.util.Arrays;

/**
 * Created by hepeng on 11/14/16.
 */
public class FastCollinearPoints {

    private ArrayList<LineSegment> lineSegments;

    public FastCollinearPoints(Point[] points) {

        if (points == null) {
            throw new java.lang.NullPointerException();
        }

        lineSegments = new ArrayList<>();

        Point[] copyP = Arrays.copyOf(points, points.length);
        Arrays.sort(copyP);
        checkDuplicatePoints(copyP);

        ArrayList<Point> slopePoint = new ArrayList<>();
        for(Point startPoint : points) {
             Arrays.sort(copyP, startPoint.slopeOrder());
             for(int i = 1; i < copyP.length; i++)
             {
                if (startPoint.slopeTo(copyP[i]) == startPoint.slopeTo(copyP[i - 1])) {
                    slopePoint.add(copyP[i]);
                }
                else {
                    addSegment(slopePoint);
                    slopePoint.clear();
                    slopePoint.add(startPoint);
                    slopePoint.add(copyP[i]);
                }
             }
        }
    }

    private void addSegment(ArrayList<Point> slopePoint) {

        if (slopePoint.size() < 4) {
            return;
        }

        Point[] points = slopePoint.toArray(new Point[slopePoint.size()]);
        Arrays.sort(points);
        LineSegment l = new LineSegment(points[0], points[points.length - 1]);

        for (LineSegment line : lineSegments) {
            if (line.toString().equals(l.toString())) return;
        }

        lineSegments.add(l);
    }

    public           int numberOfSegments() {
        return lineSegments.size();

    }
    public LineSegment[] segments() {
        return lineSegments.toArray(new LineSegment[lineSegments.size()]);
    }

    private void checkDuplicatePoints(Point[] points) {

        for (int i = 1; i < points.length; i++) {
            if (points[i].compareTo(points[i - 1]) == 0) {
                throw new java.lang.IllegalArgumentException();
            }
        }
    }
}