Question

Given a two dimensional graph with points on it, find a line which passes the most number of points.

Solution

For this question, we used to use HashMap(Double, Integer) to do. However, the answer suggested in the book define its own Line Class, and uses HashMap(Line, Intger).

This is a much better solution, however, I failed to write it, don’t know why.

The key is to override the 2 methods:

@override
public int hashCode() {}

@override
public boolean equals(Object o) {}

Code

not written by me

Line.java

public class Line {

    private static double epsilon = .0001;

    public double slope;
    public double intercept;
    private boolean infinite_slope = false;

    public Line(GraphPoint p, GraphPoint q) {
        if (Math.abs(p.x - q.x) > epsilon) { // if x痴 are different
            slope = (p.y - q.y) / (p.x - q.x); // compute slope
            intercept = p.y - slope * p.x; // y intercept from y=mx+b
        } else {
            infinite_slope = true;
            intercept = p.x; // x-intercept, since slope is infinite
        }
    }

    public boolean isEqual(double a, double b) {
        return (Math.abs(a - b) < epsilon);
    }

    public void Print() {
        System.out.println("slope = " + slope + "\nintercept = " + intercept);
    }

    @Override
    public int hashCode() {
        int sl = (int) (slope * 1000);
        int in = (int) (intercept * 1000);
        return sl | in;
    }

    @Override
    public boolean equals(Object o) {
        Line l = (Line) o;
        if (isEqual(l.slope, slope) && isEqual(l.intercept, intercept)
                && (infinite_slope == l.infinite_slope)) {
            return true;
        }
        return false;
    }
}

Main method:

public static Line findBestLine(GraphPoint[] points) {

    Line bestLine = null;
    HashMap<Line, Integer> line_count = new HashMap<Line, Integer>();

    for (int i = 0; i < points.length; i++) {
        for (int j = i + 1; j < points.length; j++) {
            Line line = new Line(points[i], points[j]);
            if (!line_count.containsKey(line)) {
                line_count.put(line, 0);
            }
            line_count.put(line, line_count.get(line) + 1);
            if (bestLine == null
                    || line_count.get(line) > line_count.get(bestLine)) {
                bestLine = line;
                System.out.println("bestLine upodated! count = "
                        + line_count.get(line));
            }
        }
    }
    return bestLine;
}