patternjavaMinor

Line passing the most number of points

Submitted by: @import:stackexchange-codereview·Mar 10, 2026·

Viewed 0 times

thenumberlinepassingpointsmost

Problem

Given points on a two dimensional graph, find a line that passes the most number of points.

Any comments please?

```
import static org.junit.Assert.*;

import java.util.*;

import org.junit.*;

public class Solution {
public class Point {
double x_coord;

double y_coord;

public Point(double x, double y) {
x_coord = x;
y_coord = y;
}
}

public class Line {
// define line with two points
Point p1;

Point p2;

public Line(Point a, Point b) {
p1 = a;
p2 = b;
}
}

public Line maxLine(ArrayList points) {
int cnt = 0;
int maxL = 0;
Line bestL = null;
if (points.size() == 0) {
return new Line(new Point(0, 0), new Point(1, 1));
} else if (points.size() == 1) {
return new Line(new Point(0, 0), points.get(0));
} else if (points.size() == 2) {
return new Line(points.get(0), points.get(1));
} else {
for (Point p1 : points) {
for (Point p2 : points) {
if (p1.x_coord maxL) {
if (p1.x_coord == p2.x_coord && p1.y_coord bestL.p2.x_coord) {
bestL = new Line(bestL.p1, p2);
} else if (cnt == maxL && p1.x_coord bestL.p2.y_coord) {
bestL = new Line(bestL.p1, p2);
}
}
}
}
}
return bestL;
}

public int countPoints(Point p1, Point p2, ArrayList points) {
int cnt = 0;
if (p1.x_coord != p2.x_coord) {
double slope = (p2.y_coord - p1.y_coord) / (p2.x_coord - p1.x_coord);
for (Point p : points) {
if (p.y_coord - p1.y_coord == slope * (p.x_coord - p1.x_coord)) {
cnt++;
}
}
} else {
for (Point p : points) {
if (p.x_coord == p1.x_coord) {
cnt++;
}
}
}
return cnt;
}

@Test
public void test_1() {
ArrayList p = new ArrayList();
p.add(new Point(0, 0));
// System.out.println(maxLine(p).p1.x_coord + " " + maxLine(p).p1.y_coord + " "
// + ma

Solution

This part of code is not just hard to follow, it is incorrect:

else if (cnt == maxL && p2.x_coord > bestL.p2.x_coord) {
    bestL = new Line(bestL.p1, p2);
} else if (cnt == maxL && p1.x_coord  bestL.p2.y_coord) {
    bestL = new Line(bestL.p1, p2);
}

Here is a unit test it fails:

final double DELTA = 1e-12;

public void testMaxLineWithSixPoints() {
    Solution solution = new Solution();
    ArrayList p = new ArrayList<>(Arrays.asList(
            solution.new Point(0, 0),
            solution.new Point(1, 0),
            solution.new Point(2, 0),
            solution.new Point(1, 1),
            solution.new Point(2, 1),
            solution.new Point(3, 1)
    ));
    Solution.Line line = solution.maxLine(p);
    assertEquals(1, line.p1.x, DELTA);
    assertEquals(1, line.p1.y, DELTA);
    assertEquals(3, line.p2.x, DELTA);
    assertEquals(1, line.p2.y, DELTA);
}

Your code returns a Line with Point(0, 0) and Point(3, 1), which contains only two points(while the correct answer is a Line with Point(1, 1) and Point(3, 1), which contains three points(or (0, 0), (2, 0)). I would recommend refactoring this piece of code to make it readable and correct:

-
I will start with refactoring the Point class. I will override the equals method and the compareTo method from the Comparable interface(I will also rename x_coord and y_coord to x and y).

public class Point implements Comparable {

    double x;
    double y;

    public Point(double x, double y) {
        this.x = x;
        this.y = y;
    }

    @Override
    public boolean equals(Object o) {
        if (!(o instanceof Point))
            return false;
        Point p = (Point) o;
        return this.compareTo(p) == 0;
    }

    /**
     * Compares two Points first by their x coordinate and if they are
     * equal, by y coordinate.
     * @param p The other Point.
     * @return -1 if this is less than p, 0 if they are equal and 1 otherwise.
     */
    @Override
    public int compareTo(Point p) {
        int result = Double.compare(x, p.x);
        if (result != 0)
            return result;
        return Double.compare(y, p.y);
    }
}

-
Now I can rewrite the part of code mentioned above:

else if (cnt == maxL) {
    if (bestL.p1.compareTo(p1) > 0 || bestL.p2.compareTo(p2) < 0) {
        bestL = new Line(p1, p2);
    }
}

It looks much better now(and it passes the test)! The old version was incorrect because we can have several different lines with the same number of points on them and there is no guarantee that bestL.p1, bestL.p2, p1 and p2 lie on the same line(you can take look at the unit test I have shown above to understand it better).

The last thing: comparing doubles using == operator after performing arithmetic operations on them can be wrong due to the rounding errors(I refer to this part of code):

double slope = (p2.y_coord - p1.y_coord) / (p2.x_coord - p1.x_coord);
for (Point p : points) {
    if (p.y_coord - p1.y_coord == slope * (p.x_coord - p1.x_coord)) {
        cnt++;
    }
}

Code Snippets

else if (cnt == maxL && p2.x_coord > bestL.p2.x_coord) {
    bestL = new Line(bestL.p1, p2);
} else if (cnt == maxL && p1.x_coord < bestL.p1.x_coord) {
    bestL = new Line(p1, bestL.p2);
} else if (cnt == maxL && p1.x_coord == bestL.p1.x_coord
        && p1.y_coord < bestL.p1.y_coord) {
    bestL = new Line(p1, bestL.p2);
} else if (cnt == maxL && p2.x_coord == bestL.p2.x_coord
        && p2.y_coord > bestL.p2.y_coord) {
    bestL = new Line(bestL.p1, p2);
}

final double DELTA = 1e-12;

public void testMaxLineWithSixPoints() {
    Solution solution = new Solution();
    ArrayList<Solution.Point> p = new ArrayList<>(Arrays.asList(
            solution.new Point(0, 0),
            solution.new Point(1, 0),
            solution.new Point(2, 0),
            solution.new Point(1, 1),
            solution.new Point(2, 1),
            solution.new Point(3, 1)
    ));
    Solution.Line line = solution.maxLine(p);
    assertEquals(1, line.p1.x, DELTA);
    assertEquals(1, line.p1.y, DELTA);
    assertEquals(3, line.p2.x, DELTA);
    assertEquals(1, line.p2.y, DELTA);
}

public class Point implements Comparable<Point> {

    double x;
    double y;

    public Point(double x, double y) {
        this.x = x;
        this.y = y;
    }

    @Override
    public boolean equals(Object o) {
        if (!(o instanceof Point))
            return false;
        Point p = (Point) o;
        return this.compareTo(p) == 0;
    }

    /**
     * Compares two Points first by their x coordinate and if they are
     * equal, by y coordinate.
     * @param p The other Point.
     * @return -1 if this is less than p, 0 if they are equal and 1 otherwise.
     */
    @Override
    public int compareTo(Point p) {
        int result = Double.compare(x, p.x);
        if (result != 0)
            return result;
        return Double.compare(y, p.y);
    }
}

else if (cnt == maxL) {
    if (bestL.p1.compareTo(p1) > 0 || bestL.p2.compareTo(p2) < 0) {
        bestL = new Line(p1, p2);
    }
}

double slope = (p2.y_coord - p1.y_coord) / (p2.x_coord - p1.x_coord);
for (Point p : points) {
    if (p.y_coord - p1.y_coord == slope * (p.x_coord - p1.x_coord)) {
        cnt++;
    }
}

Context

StackExchange Code Review Q#82444, answer score: 4

Revisions (0)

No revisions yet.