Find a line which passes the most number of points

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

My initial thoughts:
A pair of points forms a line. We can iterate through all pairs and count for how many points are on each line. That is in total a O(n^{3}) algorithm. Naive algorithm.

My initial codes:

	public class Line {
		private double slope;
		private double intercept;

		private final double THRESHOLD = Math.pow(10, -8);

		public Line(double slope, double intercept) {
			super();
			this.slope = slope;
			this.intercept = intercept;
		}

		public Line(Pair<Double> p1, Pair<Double> p2) {
			this.slope = (p2.getY() - p1.getY()) / (p2.getX() - p1.getX());
			this.intercept = (p2.getX() * p1.getY() - p1.getX() * p2.getY())
					/ (p2.getX() - p1.getX());
		}

		public boolean contains(Pair<Double> p) {
			double x = p.getX();
			double y = p.getY();
			return Math.abs(y - (slope * x + intercept)) < THRESHOLD;
		}
	}

	public static Line findLine(Set<Pair<Double>> points) {
		int maxNumber = -Integer.MAX_VALUE;
		int number = 0;
		Line result = null;
		for (Pair<Double> p1 : points) {
			for (Pair<Double> p2 : points) {
				if (!p1.equals(p2)) {
					number = 0;
					Line line = new Line(p1, p2);
					for (Pair<Double> p : points) {
						if (line.contains(p))
							number++;
					}
					if (number > maxNumber) {
						maxNumber = number;
						result = line;
					}

				}
			}
		}
		return result;
	}

Solution:
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.

	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;
				}
			}
		}
		return bestLine;
	}

	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’s 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);
		}

		@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;
		}
	}
  1. Be careful about the calculation of the slope of a line. The line might be completely vertical. We can keep track of this in a separate flag (infinite_slope). We need to check this condition in the equals method.
  2. Remember that when we perform division to calculate the slope, division is not exact. Therefore, rather than checking to see if two slopes are exactly equal, we need to check if they’re different by greater than epsilon.
Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: