Question

How to get the number of points that lie on the same straight line on x y graph with Java

Answer 1

//    y
//    
//    |
// 5 -|
//    |
// 4 -|    .
//    |
// 3 -|         .              .
//    |
// 2 -|              .
//    |
// 1 -|    .              .
//    |
//    ---------------------------- x
//    0    1    2    3    4    5    
   
// points = {{1, 1}, {3, 2}, {5, 3}, {4, 1}, {2, 3}, {1, 4}};

import java.util.HashMap;

public class MaxPointsOnALine {
    public static int getMaxPointsOnALine(int[][] points) {
        int size = points.length;
        if (size == 1) {
            return 0;
        }
        int result = 0;

        for (int i = 0; i < size; i++) {
            HashMap<Double, Integer> hmp = new HashMap<>();
            int duplicate = 1;

            for (int j = i + 1; j < size; j++) {
                if (points[i][0] == points[j][0] && points[i][1] == points[j][1]) {
                    duplicate++;
                    continue;
                }

                int x = points[j][0] - points[i][0];
                int y = points[j][1] - points[i][1];

                // vertical lines (x = 0) 
                // horizontal lines (y = 0) 
                double line = x == 0 ? Double.POSITIVE_INFINITY : y == 0 ? 0 : y / (double) x;

                hmp.put(line, hmp.getOrDefault(line, 0) + 1);
            }

            result = Math.max(result, duplicate);

            for (int count : hmp.values()) {
                result = Math.max(result, count + duplicate);
            }
        }

        return result;
    }
    public static void main(String args[]) {
        int[][] points = {{1, 1}, {3, 2}, {5, 3}, {4, 1}, {2, 3}, {1, 4}};
         
        System.out.println(getMaxPointsOnALine(points)); 
    }
}
    
   
   
    
/*
run:
   
4
   
*/

 

Learn SQL from A to Z at LearnSQL.com