Nearest pair of points

Question

Given a set of 2 dimensional points, it returns the two nearest points. If more pairs have the same min-distance between them, then an arbitrary choice is made. This program expects the points to be sorted on the x-axis. If not, input is unpredictable.

I'm looking for code review, optimizations and best practices.

final class PointPair  {
    private final Point point1;
    private final Point point2;
    private final double distance;

    PointPair (Point point1, Point point2, double distance) {
        this.point1 = point1;
        this.point2 = point2;
        this.distance = distance;
    }

    public Point getPoint1() {
        return point1; 
    }

    public Point getPoint2() {
        return point2; 
    }

    public double getDistance() {
        return distance;
    }
}


final class Point {

    private final int x;
    private final int y;

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

    public int getX() {
        return x;
    }

    public int getY() {
        return y;
    }
}


public final class ClosestPair {

    private static final int BRUTEFORCE_INDEX = 3;

    private ClosestPair() {}

        /**
 * Given a set of 2 dimensional points it returns the the two nearest points.
 * If more pairs have the same min-distance between then then arbitrary choice is made.
 * This program expects the points to be sorted on x-axis. If not input is unpredictable.
 * 
 * 
 * @param points    the array of points sorted by x-axis
 * @return          the pair of points which are nearest to each other.
 */
    public static PointPair minPointPair (Point[] points) {
        return calcPointPair(points, 0, points.length);
    }

    private static PointPair calcPointPair(Point[] points, int low, int high) {
        assert points != null;

        if ((high - low) <= BRUTEFORCE_INDEX) {
            return bruteForce(points, low, high);
        }

        int mid = (low + high) / 2;

        final PointPair leftPair  = calcPointPair(points, low, mid);
        final PointPair rightPair  = calcPointPair(points, mid + 1, high);

        final PointPair minPair = getMin (leftPair, rightPair);
        final PointPair pointPair = zoneSearch(points, mid, minPair.getDistance());

        return getMin(minPair, pointPair);
    }

    private static PointPair getMin (PointPair pointPair1, PointPair pointPair2) {
        assert pointPair1 != null;
        assert pointPair2 != null;

        if (pointPair1.getDistance() < pointPair2.getDistance()) {
            return pointPair1;
        } else {
            return pointPair2;
        }
    }

    private static PointPair bruteForce(Point[] points, int low, int high) {

        double minDistance = Double.MAX_VALUE;

        Point firstPoint = null;
        Point secondPoint = null;
        for (int i = low; i < high - 1; i++) {
            for (int j = i + 1; j < high; j++) {
                double distance = calcDistance(points[i], points[j]);
                if (distance < minDistance) {
                    firstPoint = points[i];
                    secondPoint = points[j];
                    minDistance = distance;
                }
            }
        }

        return new PointPair(firstPoint, secondPoint, minDistance);
    }


    private static double calcDistance(Point point1, Point point2) {
        int diffX = point1.getX() - point2.getY();
        int diffY = point1.getY() - point2.getY();
        return Math.sqrt(Math.pow(diffX, 2) + Math.pow(diffY, 2));
    }


    private static PointPair zoneSearch(Point[] points, int mid, double distance) {
        // contains all the nodes which are in horizontal x axis proximity of mid.
        final List<Point> pointList = new ArrayList<Point>(); 

        for (int i = 0; i < points.length; i++) {
            if (i != mid) {
                if (Math.abs(points[i].getX() - points[mid].getX()) <= distance) {
                    pointList.add(points[i]);
                }
            }
        }

        // sorted by y axis
        Collections.sort(pointList, new Comparator<Point>() {
            @Override
            public int compare(Point point1, Point point2) {
                return point2.getY() - point1.getY(); // sorting from top down
            }
        });

        double minDistance = Double.MAX_VALUE;

        Point firstPoint = null;
        Point secondPoint = null;

        // for each point, starting from the point on the top.
        for (int i = 0; i < pointList.size() - 1; i++) {
           for (int j = i + 1; j < pointList.size(); j++) {

               double yDistance = pointList.get(i).getY() - pointList.get(j).getY();

               if (yDistance > minDistance) { break; }

               double candidateDistance = calcDistance(pointList.get(i), pointList.get(j));
               if (calcDistance(pointList.get(i), pointList.get(j)) < minDistance) {
                   minDistance = candidateDistance;
                   firstPoint = pointList.get(i);
                   secondPoint =  pointList.get(j);
               }
           }
        }

        return new PointPair(firstPoint, secondPoint, minDistance);
    }



    public static void main(String[] args) {

        Point p1 = new Point(1, 1);
        Point p2 = new Point(2, 2);
        Point p3 = new Point(4, 4);
        Point p4 = new Point(7, 7);

        Point[] point1 = new Point[4];
        point1[0] = p1;
        point1[1] = p2;
        point1[2] = p3;
        point1[3] = p4;

        System.out.print("Expected 1,1 : 2, 2 Actual: ");
        PointPair pp = ClosestPair.minPointPair(point1);
        System.out.print(pp.getPoint1().getX() + "," + pp.getPoint1().getY() + " : ");
        System.out.println(pp.getPoint2().getX() + "," + pp.getPoint2().getY());


        Point p5 = new Point(1, 1);
        Point p6 = new Point(20, 20);
        Point p7 = new Point(40, 40);
        Point p8 = new Point(70, 70);
        Point p9 = new Point(100, 100);
        Point p10 = new Point(150, 150);
        Point p11 = new Point(400, 400);
        Point p12 = new Point(7, 7);

        Point[] point2 = new Point[8];
        point2[0] = p5;
        point2[1] = p6;
        point2[2] = p7;
        point2[3] = p8;
        point2[4] = p9;
        point2[5] = p10;
        point2[6] = p11;
        point2[7] = p12;

        System.out.print("Expected 1,1 : 7,7 Actual: ");
        pp = ClosestPair.minPointPair(point2);
        System.out.print(pp.getPoint1().getX() + "," + pp.getPoint1().getY() + " : ");
        System.out.println(pp.getPoint2().getX() + "," + pp.getPoint2().getY());

        Point p13 = new Point(1, 1);
        Point p14 = new Point(20, 20);
        Point p15 = new Point(40, 40);
        Point p16 = new Point(70, 70);
        Point p17 = new Point(100, 100);
        Point p18 = new Point(150, 150);
        Point p19 = new Point(5, 5);
        Point p20 = new Point(7, 7);

        Point[] point3 = new Point[8];
        point3[0] = p13;
        point3[1] = p14;
        point3[2] = p15;
        point3[3] = p16;
        point3[4] = p17;
        point3[5] = p18;
        point3[6] = p19;
        point3[7] = p20;

        System.out.print("Expected 5,5 : 7,7, Actual: ");
        pp = ClosestPair.minPointPair(point3);
        System.out.print(pp.getPoint1().getX() + "," + pp.getPoint1().getY() + " : ");
        System.out.println(pp.getPoint2().getX() + "," + pp.getPoint2().getY());
    }
}

Answer 1

The main() method could be replaced with automatized JUnit tests to avoid manual result verification. You could also have more test methods which help defect localization.