4
\$\begingroup\$

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());
    }
}
\$\endgroup\$
6
  • 3
    \$\begingroup\$ Quick tip: You don't need the actual distances A-B and A-C to determine whether B or C is closer to A--just the relative distances. Drop the call to sqrt to shave off a few CPU cycles. \$\endgroup\$ Feb 9, 2014 at 0:32
  • 1
    \$\begingroup\$ You could explicitly save off the Comparator<Point> you're using for sorting on y-location, although the JITter may be doing that for you anyways. You said that your method required data to be sorted on the x-axis, but the examples you give aren't, what's up with that? You should probably add .equals(), .hashcode(), and .toString() methods for your value types. Some methods should probably be broken up further. \$\endgroup\$ Feb 9, 2014 at 1:58
  • 1
    \$\begingroup\$ in zoneSearch you go over the whole array every time, instead of only from low to high, which means you make too many calculations, and you may return a result which is not in the range expected... \$\endgroup\$
    – Uri Agassi
    Feb 11, 2014 at 18:19
  • \$\begingroup\$ @Clockwork-Muse good point, i realized this does not need a sorted array as input \$\endgroup\$ Feb 12, 2014 at 23:28
  • 1
    \$\begingroup\$ Um, if you're trying for the planar case optimization (which it looks like), you do need them sorted on the x-axis. I have a feeling you're currently getting correct results only because of a small data-set, and/or the use of bruteForce(...). What happens if you pump the number of points up to 100 or further? Also, your current code has a weakness to integer overflow... why aren't the x/y coordinates doubles to begin with? \$\endgroup\$ Feb 13, 2014 at 10:02

1 Answer 1

2
\$\begingroup\$

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.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.