How to find the maximum number of points lying on the same straight line

Question

Suppose you have an array of Points on a 2D plane. Point being defined as such:

class Point {
    public int x; 
    public int y;

    Point(int _x, int _y) { x = _x; y = _y; }
}

How could I find the maximum number of points lying on the same straight line in java?

Answer 1

Here is a solution in Java using precise arithmetic:

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

public class Solver {
    public int maxPointsOnLine(List<Point> points) {
        int ans = 0;
        Map<Line, Integer> lines = new HashMap<Line, Integer>();
        for (Point a : points) {
            int max = 0;
            int same = 0;
            lines.clear();

            for (Point b : points) {
                if (a.x == b.x && a.y == b.y) {
                    ++same;
                } else {
                    Line line = new Line(b.x - a.x, b.y - a.y);
                    Integer count = lines.get(line);
                    if (count == null) {
                        count = 0;
                    }
                    ++count;
                    lines.put(line, count);
                    max = Math.max(max, count);
                }
            }
            ans = Math.max(ans, same + max);
        }
        return ans;
    }

    static class Line {
        final int dx;
        final int dy;

        Line(int dx, int dy) {
            if (dy == 0) {
                dx = Math.abs(dx);
            }
            else if (dy < 0) {
                dx = -dx;
                dy = -dy;
            }
            int gcd = gcd(Math.abs(dx), dy);
            dx /= gcd;
            dy /= gcd;
            this.dx = dx;
            this.dy = dy;
        }

        @Override
        public boolean equals(Object other) {
            if (!(other instanceof Line)) {
                return false;
            }
            Line another = (Line)other;
            return dx == another.dy && dy == another.dy;
        }

        @Override
        public int hashCode() {
            return 31 * dx + dy;
        }
    }

    static int gcd(int a, int b) {
        return b == 0 ? a : gcd(b, a % b);
    }
}

Answer 2

For each point in the array, calculate the angle between this point and other points. Counting the number of those with the same angle using a hashMap. Expected time O(n^2)

Pseudo code

int result = 0;
for(int i = 0; i < data.length; i++){
    HashMap<Double, Integer> map = new HashMap();
    for(int j = 0; j < data.length; j++){
        if(i == j)
            continue;
        double angle = calculateAngle(data[i], data[j]);
        if(map.containsKey(slope)){
            map.put(angle, map.get(slope) + 1);
        }else{
            map.put(angle, 1);
        }
        result = max(result, map.get(slope));
    }
}

Note: As mention in NiklasB 's comment, using double will cause some problems with precision, especially when we need to compare those floating values. We can avoid that by using the Rational class suggested by NiklasB. (Or less precise, using this)

Answer 3

/**
 * Definition for a point.
 * struct Point {
 *     int x;
 *     int y;
 *     Point() : x(0), y(0) {}
 *     Point(int a, int b) : x(a), y(b) {}
 * };
 */
class Solution {
public:
    int maxPoints(vector<Point> &points) {
        int n = points.size(); //number of the points
        if (n<=2){return n;}   
        vector<double> k; //vector to store the slops for one point with all the other points
        int res = 0;

        for (int i=0;i<n;i++){ // for each point in the 2d plane
            k.clear();
            int dup = 1; // number of the duplicates with currrent point
            for (int j=0;j<n;j++){ 
                if (i!=j){ // for every other point
                    if (points[i].x-points[j].x==0){ // if the slope is a vertical line
                        if (points[i].y-points[j].y==0){ // if the point j is the same as point i
                            dup++;  
                        }else{
                            k.push_back(99999); //store the vertical line to a specific slope
                        }
                    }else{ // if it is the regular slop between point i and j
                        k.push_back(10000*(points[i].y-points[j].y)/(points[i].x-points[j].x)); // store the slope
                    }
                }
            }

            sort(k.begin(),k.end()); //sort the slopes for counting

            int pp = 1; //number of points in the same line of the point i
            if (k.size()==0){pp=0;} 

            for (int jj=1;jj<k.size();jj++){ //count pp
                if (k[jj]==k[jj-1]){
                    pp++;
                }else{
                    if (pp+dup>res){res=pp+dup;} // res = pp + the number of duplicates
                    pp = 1;
                }
            }
            if (pp+dup>res){res = pp+dup;}
        }

        return res;
    }
};