Max Points on a Line

Given n distinct points on a plane, return the maximum number of points that lie on the same straight line.

Example

Text

Input:  [(1, 1), (2, 2), (1, 2), (3, 3), (2, 3)]
Output: 3   ((1, 1), (2, 2), (3, 3))

Brute force: every pair defines a line

Any two points define a line. For each pair, count how many points lie on it. Point r is on the line through p and q when the cross product is zero:

Text

(q.x - p.x) · (r.y - p.y) == (q.y - p.y) · (r.x - p.x)

This compares slopes without dividing, so it's exact. Each point is a long[] of length 2 ({x, y}), and the products use long so coordinates up to about 2 billion cannot overflow.

Java

public class Main {
    static int maxPoints(long[][] points) {
        int n = points.length;
        if (n <= 2) return n;
        int best = 0;
        for (int i = 0; i < n; i++) {
            long[] p = points[i];
            for (int j = i + 1; j < n; j++) {
                long[] q = points[j];
                int onLine = 0;
                for (long[] r : points) {
                    if ((q[0] - p[0]) * (r[1] - p[1]) == (q[1] - p[1]) * (r[0] - p[0])) onLine++;
                }
                best = Math.max(best, onLine);
            }
        }
        return best;
    }

    public static void main(String[] args) {
        System.out.println(maxPoints(new long[][]{{1, 1}, {2, 2}, {1, 2}, {3, 3}, {2, 3}}));
        System.out.println(maxPoints(new long[][]{{1, 1}, {3, 2}, {5, 3}, {4, 1}, {2, 3}, {1, 4}}));
    }
}

Output

3
4

Time: O(n³). Space: O(1).

Optimal: group by slope from each anchor

Fix an anchor point p. Every other point q lies on exactly one line through p, determined by the slope from p to q. Count the points per slope in a HashMap; the largest group plus p itself is the best line through p. The best over all anchors is the answer.

Floating-point slopes can make two equal slopes differ in the last bit. Instead, store the slope as the fraction (dy, dx) reduced by their GCD, with a normalized sign:

divide dx and dy by gcd(|dx|, |dy|),
make dx positive, or, for vertical lines (dx == 0), make dy positive.

Then (2, 4), (1, 2), and (-1, -2) all become (1, 2).

A Java array has no value-based equals, so it cannot be a HashMap key. The slope is stored as a String such as "1/2" instead, which has value-based equals and hashCode.

Java

import java.util.HashMap;
import java.util.Map;

public class Main {
    static long gcd(long a, long b) {
        while (b != 0) {
            long t = a % b;
            a = b;
            b = t;
        }
        return a;
    }

    static String slope(long[] p, long[] q) {
        long dx = q[0] - p[0];
        long dy = q[1] - p[1];
        long g = gcd(Math.abs(dx), Math.abs(dy)); // never 0: the points are distinct
        dx /= g;
        dy /= g;
        if (dx < 0 || (dx == 0 && dy < 0)) {
            dx = -dx;
            dy = -dy;
        }
        return dy + "/" + dx;
    }

    static int maxPoints(long[][] points) {
        int best = Math.min(points.length, 1);
        for (int i = 0; i < points.length; i++) {
            Map<String, Integer> counts = new HashMap<>();
            for (int j = i + 1; j < points.length; j++) {
                int count = counts.merge(slope(points[i], points[j]), 1, Integer::sum);
                best = Math.max(best, count + 1); // + 1 for p itself
            }
        }
        return best;
    }

    public static void main(String[] args) {
        System.out.println(maxPoints(new long[][]{{1, 1}, {2, 2}, {1, 2}, {3, 3}, {2, 3}}));
        System.out.println(maxPoints(new long[][]{{1, 1}, {3, 2}, {5, 3}, {4, 1}, {2, 3}, {1, 4}}));
        System.out.println(maxPoints(new long[][]{{0, 0}, {0, 5}, {0, -3}}) + " " + maxPoints(new long[][]{{7, 7}}));
    }
}

Output

3
4
3 1

Time: O(n²) on average. Space: O(n) for one anchor's map.

Only points after p are compared with it. A line's points are all counted from its first point in the array, so nothing is missed.

Edge cases

One or two points: always on one line.
Vertical and horizontal lines: become (1, 0) and (0, 1) after normalization.
Duplicate points: this problem rules them out. If they're allowed, count copies of p separately and add them to every line through p.