finding the maximum number of points that lie on the same straight line in a 2D plane

Question

This "Given n points on a 2D plane, find the maximum number of points that lie on the same straight line." question from leetcode.com I am trying to solve it but I am not able to pass all test cases.

What I am trying to do is:- I am using a hashmap whose key is the angle b/w the points which I am getting through tan inverse of the slope and I am storing the values for each slope initially the value of the no of occurrance of that point and then incrementing it.

I am using another hashmap for counting the occurance of points.

I am not getting the correct answer for points like (0,0),(1,0) which should return 2 but it's returning 1.

What am I missing?

My code is:

public class MaxPointsINLine {
    int max = 0;
    int same;

    public int maxPoints(Point[] points) {
        int max = 0;
        Map<Double, Integer> map = new HashMap<Double, Integer>();
        Map<Point, Integer> pointmap = new HashMap<Point, Integer>();
        for(Point point: points)
        {
            if(!pointmap.containsKey(point))
            {
                pointmap.put(point, 1);
            }
            else
            {
                pointmap.put(point, pointmap.get(point)+1);
            }
        }
        if (points.length >= 2) {
            for (int i = 0; i < points.length; i++) {
                for (int j = i ; j < points.length; j++) {
                    double dx = points[j].x - points[i].x;
                    double dy = points[j].y - points[i].y;
                    double slope = Math.atan(dy / dx);
                    if (!map.containsKey(slope)) {
                        map.put(slope, pointmap.get(points[j]));
                    } else
                        map.put(slope, map.get(slope) + 1);
                }
            }
            for (Double key : map.keySet()) {
                if (map.get(key) > max) {
                    max = map.get(key);
                }
            }
            return max;
        } else if (points.length != 0) {
            return 1;
        } else {
            return 0;
        }
    } 

    public static void main(String[] args) {
        Point point1 = new Point(0,0);
        Point point2 = new Point(0,0);
        //Point point3 = new Point(2,2);
        MaxPointsINLine maxpoint = new MaxPointsINLine();
        Point[] points = { point1, point2};
        System.out.println(maxpoint.maxPoints(points));

    }

}

class Point {
    int x;
    int y;

    Point() {
        x = 0;
        y = 0;
    }

    Point(int a, int b) {
        x = a;
        y = b;
    }

    @Override
    public boolean equals(Object obj) {
        Point that = (Point)obj;
        if (that.x == this.x && that.y == this.y)
            return true;
        else
            return false;
    }

    @Override
    public int hashCode() {
        // TODO Auto-generated method stub
        return 1;
    }
}

Answer 1

The most straightforward solution here seems to be the following: One can consider each pair of points. For each pair, one computes the distance of each other point to the line connecting the two points. If this distance is nearly zero, then the point lies on the line.

When this is done for all pairs, one can pick the pair for which the highest number of points lies on the connecting line.

Of course, this is not very elegant, as it is in O(n^3) and performs some computations twice. But it is very simple and rather reliable. I just implemented this as a MCVE here:

One can set points with left-clicking the mouse. Right-clicks clear the screen. The maximum number of points in one line is displayed, and the corresponding points are highlighted.

(EDIT: Updated to handle points that have a distance of 0, based on the comment)

import java.awt.BorderLayout;
import java.awt.Color;
import java.awt.Graphics;
import java.awt.Graphics2D;
import java.awt.Point;
import java.awt.event.MouseEvent;
import java.awt.event.MouseListener;
import java.awt.geom.Line2D;
import java.util.ArrayList;
import java.util.List;

import javax.swing.JFrame;
import javax.swing.JPanel;
import javax.swing.SwingUtilities;

public class PointsOnStraightLineTest
{
    public static void main(String[] args)
    {
        SwingUtilities.invokeLater(new Runnable()
        {
            @Override
            public void run()
            {
                createAndShowGUI();
            }
        });
    }

    private static void createAndShowGUI()
    {
        JFrame f = new JFrame();
        f.setDefaultCloseOperation(JFrame.EXIT_ON_CLOSE);
        f.getContentPane().setLayout(new BorderLayout());
        f.getContentPane().add(new PointsPanel());
        f.setSize(600, 600);
        f.setLocationRelativeTo(null);
        f.setVisible(true);
    }
}

class PointsOnStraightLine
{
    // Large epsilon to make it easier to place
    // some points on one line with the mouse...
    private static final double EPSILON = 5.0; 

    List<Point> maxPointsOnLine = new ArrayList<Point>();

    void compute(List<Point> points)
    {
        maxPointsOnLine = new ArrayList<Point>();

        for (int i=0; i<points.size(); i++)
        {
            for (int j=i+1; j<points.size(); j++)
            {
                Point p0 = points.get(i);
                Point p1 = points.get(j);
                List<Point> resultPoints = null;
                if (p0.distanceSq(p1) < EPSILON)
                {
                    resultPoints = computePointsNearby(p0, points);
                }
                else
                {
                    resultPoints = computePointsOnLine(p0, p1, points);
                }
                if (resultPoints.size() > maxPointsOnLine.size())
                {
                    maxPointsOnLine = resultPoints;
                }
            }
        }
    }

    private List<Point> computePointsOnLine(
        Point p0, Point p1, List<Point> points)
    {
        List<Point> result = new ArrayList<Point>();
        for (int k=0; k<points.size(); k++)
        {
            Point p = points.get(k);
            double d = Line2D.ptLineDistSq(p0.x, p0.y, p1.x, p1.y, p.x, p.y);
            if (d < EPSILON)
            {
                result.add(p);
            }
        }
        return result;
    }

    private List<Point> computePointsNearby(
        Point p0, List<Point> points)
    {
        List<Point> result = new ArrayList<Point>();
        for (int k=0; k<points.size(); k++)
        {
            Point p = points.get(k);
            double d = p.distanceSq(p0);
            if (d < EPSILON)
            {
                result.add(p);
            }
        }
        return result;
    }

}



class PointsPanel extends JPanel implements MouseListener
{
    private final List<Point> points;
    private final PointsOnStraightLine pointsOnStraightLine;

    PointsPanel()
    {
        addMouseListener(this);

        points = new ArrayList<Point>();
        pointsOnStraightLine = new PointsOnStraightLine();
    }

    @Override
    protected void paintComponent(Graphics gr)
    {
        super.paintComponent(gr);
        Graphics2D g = (Graphics2D)gr;

        g.setColor(Color.BLACK);
        for (Point p : points)
        {
            g.fillOval(p.x-2, p.y-2, 4, 4);
        }

        pointsOnStraightLine.compute(points);

        int n = pointsOnStraightLine.maxPointsOnLine.size();
        g.drawString("maxPoints: "+n, 10, 20);

        g.setColor(Color.RED);
        for (Point p : pointsOnStraightLine.maxPointsOnLine)
        {
            g.drawOval(p.x-3, p.y-3, 6, 6);
        }
    }

    @Override
    public void mouseClicked(MouseEvent e)
    {
        if (SwingUtilities.isRightMouseButton(e))
        {
            points.clear();
        }
        else
        {
            points.add(e.getPoint());
        }
        repaint();
    }

    @Override
    public void mousePressed(MouseEvent e)
    {
    }

    @Override
    public void mouseReleased(MouseEvent e)
    {
    }

    @Override
    public void mouseEntered(MouseEvent e)
    {
    }

    @Override
    public void mouseExited(MouseEvent e)
    {
    }
}

Answer 2

This one worked for me:

/**
 * Definition for a point.
 * class Point {
 *     int x;
 *     int y;
 *     Point() { x = 0; y = 0; }
 *     Point(int a, int b) { x = a; y = b; }
 * }
 */
public class Solution {
    public int maxPoints(Point[] points) {


        int result = 0;
        for(int i = 0; i<points.length; i++){
            Map<Double, Integer> line = new HashMap<Double, Integer>();
            Point a = points[i];
            int same = 1;    
            //System.out.println(a);
            for(int j = i+1; j<points.length; j++){
                Point b = points[j];
                //System.out.println(" point " + b.toString());
                if(a.x == b.x && a.y == b.y){
                    same++;
                } else {
                    double dy = b.y - a.y;
                    double dx = b.x - a.x;
                    Double slope;
                    if(dy == 0){ // horizontal
                        slope = 0.0;
                    } else if(dx == 0){//eartical
                        slope = Math.PI/2;
                    } else {
                        slope = Math.atan(dy/dx);
                    }
                    Integer slopeVal = line.get(slope);
                    //System.out.println(" slope " + slope + "  slope value " + slopeVal);
                    if(slopeVal == null){
                        slopeVal = 1;
                    } else {
                        slopeVal += 1;
                    }
                    line.put(slope, slopeVal);
                }
            }

            for (Double key : line.keySet()) {
                Integer val = line.get(key);
                result = Math.max(result, val + same);
            }
            // for all points are same
            result = Math.max(result, same);

        }
        return result;
    }



}

Answer 3

The general strategy doesn't seem like it can work. Let's suppose that we've successfully populated map with key-value pairs (a, N) where a is an angle and N is the number of pairs of points that are joined by the angle a. Consider the following arrangement of 6 points:

**
  **
**

Explicitly, there are points at (0,0), (1,0), (2,1), (3,1), (0,2), and (1,2). You can check that the maximum number of points that lie on any line is 2. However, there are 3 pairs of points that are joined by the same angle: ((0,0), (1,0)), ((2,1), (3,1)), and ((0,2), (1,2)). So map will contain a key-value pair with N = 3, but that isn't the answer to the original question.

Because of arrangements like the above, it's not enough to count slopes. A successful algorithm will have to represent lines in such a way that you can distinguish between parallel lines.