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());
}
}
sqrt
to shave off a few CPU cycles. \$\endgroup\$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\$zoneSearch
you go over the whole array every time, instead of only fromlow
tohigh
, which means you make too many calculations, and you may return a result which is not in the range expected... \$\endgroup\$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 coordinatesdouble
s to begin with? \$\endgroup\$