Find a line which passes the most number of points | Runhe Tian Coding Practice

Find a line which passes the most number of points | Runhe Tian Coding Practice
Given a two dimensional graph with points on it, find a line which passes the most number of points.

We have a bunch of line segments, represented as a slope and y-intercept, and we want to find the most common slope and y-intercept. How can we find the most common one? This is really no different than the old "find the most common number in a list of numbers" problem. We just iterate through the lines segments and use a hash table to count the number of times we've seen each line.

Find the line through the most points

Line_most_points.cpp LineMostPoints.java
class Line {
private Pair<Integer, Integer> slope;
private Pair<Integer, Integer> intercept;

Line(Point a, Point b) {
if (a.x != b.x) {
slope = getCanonicalFractional(b.y - a.y, b.x - a.x);
} else {
slope = new Pair<Integer, Integer>(1, 0);
}
if (a.x != b.x) {
intercept = getCanonicalFractional(b.x * a.y - a.x * b.y, b.x - a.x);
} else {
intercept = new Pair<Integer, Integer>(a.x, 1);
}
}

public static Pair<Integer, Integer> getCanonicalFractional(int a, int b) {
int gcd = BigInteger.valueOf(a).gcd(BigInteger.valueOf(b)).intValue();
a /= gcd;
b /= gcd;
return b < 0 ? new Pair<Integer, Integer>(-a, -b)
: new Pair<Integer, Integer>(a, b);
}

public Pair<Integer, Integer> getSlope() {
return slope;
}

public Pair<Integer, Integer> getIntercept() {
return intercept;
}
public boolean equals(Object o) {
if (o instanceof Line) {
Line l = (Line) o;
return nullEqual(slope, l.getSlope())
&& nullEqual(intercept, l.getIntercept());
}

return false;
}
public int hashCode() {
return slope.getFirst() ^ slope.getSecond() ^ intercept.getFirst()
^ intercept.getSecond();
}
}

public class LineMostPoints {

private static int check(ArrayList<Point> P) {
int maxCount = 0;
for (int i = 0; i < P.size(); ++i) {
for (int j = i + 1; j < P.size(); ++j) {
int count = 2;
Line temp = new Line(P.get(i), P.get(j));
for (int k = j + 1; k < P.size(); ++k) {
if (new Line(P.get(i), P.get(k)).equals(temp)) {
++count;
}
}
maxCount = Math.max(maxCount, count);
}
}

return maxCount;
}
private static Line findLineWithMostPoints(ArrayList<Point> P) {
// Add all possible lines into hash table.
HashMap<Line, HashSet<Point>> table = new HashMap<Line, HashSet<Point>>();
for (int i = 0; i < P.size(); ++i) {
for (int j = i + 1; j < P.size(); ++j) {
Line l = new Line(P.get(i), P.get(j));

HashSet<Point> s1 = table.get(l);
if (s1 == null) {
s1 = new HashSet<Point>();
table.put(l, s1);
}
s1.add(P.get(i));

HashSet<Point> s2 = table.get(l);
if (s2 == null) {
s2 = new HashSet<Point>();
table.put(l, s2);
}
s2.add(P.get(j));
}
}
return Collections.max(table.entrySet(),
new Comparator<Map.Entry<Line, HashSet<Point>>>() {
@Override
public int compare(Map.Entry<Line, HashSet<Point>> e1,
Map.Entry<Line, HashSet<Point>> e2) {
if (e1 != null && e2 != null) {
return new Integer(e1.getValue().size())
.compareTo(e2.getValue().size());
} else if (e1 != null) {
return 1;
} else {
return -1;
}
}
}).getKey();
}
 }
Read full article from Find a line which passes the most number of points | Runhe Tian Coding Practice