The simplest solution here is as follows: you can consider each pair of points. For each pair, one calculates the distance of each other point to the line connecting the two points. If this distance is almost zero, then the point lies on a straight line.
When this is done for all pairs, you can select the pair for which the largest number of points lies on the connecting line.
Of course, this is not very elegant, since it is in O (n ^ 3) and performs some calculations twice. But it is very simple and reliable enough. I just implemented this as MCVE here:
You can set points by left-clicking. Right clicks clear the screen. The maximum number of points in one line is displayed, and the corresponding points are highlighted.
(UPDATE: updated to handle points that have a distance of 0, based on a 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, px, py); 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(px-2, py-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(px-3, py-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) { } }