Find Maximum points that lie on a Straigt line

Given n points on a 2D plane with (x, y) co-ordinates.

Find the maximum number of points that lie on the same straight line.

For Example, If given points are: { (1, 1), (2, 2), (2, 1), (4, 3), (3, 3), (1, 4) }
Then the output should be 3 because there are 3 points on the same line:

Solution:

We can draw a line between each pair of points.

The brute force way of solving this problem is to check how many points fall on every such line. If you know two points falling on the line, then you can find the equation of the line, which is in the following form:

In this equation, m is the slope.

If you are given two points (x1, y1) and (x2, y2), then the slope is: m = (y2-y1)/(x2-x1) 

The slope remains the same for a line. Follow the following algorithm:

• For each given point, find the slope of that point with all other points.
• If the slope of this point with two other points is same, then these three points (the 2 points and the point of origin) are considered to be in the same line. Do it for all the points, and keep a track of the maximum points on one line seen till now.
• Maintain a HashMap for each point.
• The slope between two points becomes the key and value is the frequency (number of points) with that slope.

The problem here is that slope is a double value, and we may run into precision errors. So to avoid this, store the slope as a rational number instead of double. To get the same number for 5/10 and 7/14, store the GCD (i.e 1/2).

class Point {
   int i;
   int j;
   Point() { i = 0; j = 0; }
   Point(int a, int b) { i = a; j = b; }
}

public class Test 
{
   public static int maxPointsOnALine(Point[] points) 
   {
      int result = 0;
      HashMap<Integer, hashmap<Integer, Integer>> map = new HashMap<>();
        
      for (int i = 0; i < points.length; i++) 
      {
         map.clear(); // USING FRESH MAP FOR EACH POINT
            
         int overlap = 0;
         int max = 0;
            
         for (int j = i+1; j < points.length; j++) 
         {
            int x = points[j].i - points[i].i;
            int y = points[j].j - points[i].j;
            
            // IF TWO POINTS ARE SAME
            if (x == 0 && y == 0) {
               overlap++;
               continue;
            }
                
            int gcd = generateGCD(x, y); // FIND GCD
                
            if (gcd != 0) // BRING x AND y TO SIMPLEST FORM 
            {
               x /= gcd;
               y /= gcd;
            }
                
            if(map.containsKey(x)) 
            {
               if(map.get(x).containsKey(y)) // OLD POINT 
                  map.get(x).put(y, map.get(x).get(y) + 1);
               else // NEW POINT
                  map.get(x).put(y, 1);
            } 
            else 
            {
               HashMap<Integer, Integer> m = new HashMap<>();
               m.put(y, 1);
               map.put(x, m);
            }
            max = Math.max(max, map.get(x).get(y));  
         }
         result = Math.max(result, max + overlap + 1);
      }
      return result;  
    }
    
    private static int generateGCD(int a, int b) 
    {
        if (b == 0) return a;
        return generateGCD(b, a % b);
    }
    public static void main(String[] args)
    {
    	Point[] points = new Point[]{
    		new Point(1, 1),
    		new Point(2, 2),
    		new Point(2, 1),
    		new Point(4, 3),
    		new Point(3, 3),
    		new Point(1, 4)
    	};
    	System.out.println(maxPointsOnALine(points));
    }
}