static int distL;
static int distR;
static int distLR;
/** Find the square distance of the closest pairs in the point set. This static function is the preparation step for the recursive part of the algorithm defined in the method closestPairAux. */
public static int closestPair(PointSet P)
throws TrivialClosestPairException, UnknownSortOptionException
{
Point[] X = P.sort('x');
Point[] Y = P.sort('y');
int sqrDist = 0;
if (P.size() <= 3) {
// Brute force
sqrDist = PointSet.naiveClosestPair(P);
return sqrDist;
} else {
sqrDist = closestPairAux(X, Y);
}
return sqrDist;
}
/** The recursive part of Shamos's Algorithm. The parameter X is an array of points sorted by the X axis and the parameter Y is the same array of points sorted by the Y axis. */
public static int closestPairAux(Point[] X, Point[] Y)
throws TrivialClosestPairException, UnknownSortOptionException
{
Point midPoint = X[(X.length / 2)- 1];
PointSet yStrip = null;
int minDist;
Point[] PL = (Arrays.copyOfRange(X, 0, (int) Math.ceil(X.length/2)));
Point[] PR = Arrays.copyOfRange(X, (int) Math.ceil(X.length/2), (int) X.length);
Point[] YL = Arrays.copyOfRange(Y, 0, (int) Math.ceil(X.length/2));
Point[] YR = Arrays.copyOfRange(Y, (int) Math.ceil(X.length/2), (int) X.length);
if (X.length > 2) {
distL = closestPairAux(PL,YL);
distR = closestPairAux(PR,YR);
}
// Find the minimum distance between left set and right set
if (distL < distR) {
distLR = distL;
} else {
distLR = distR;
}
for (int i = 0; i < Y.length -1; i++) {
if ( Y[i].getX() - midPoint.getX() < distLR) {
yStrip.addPoint(Y[i]);
}
}
Point[] yStripsort = yStrip.sort('x');
minDist = distLR;
for ( int j = 0; j <= yStripsort.length - 2; j++) {
int k = j + 1;
while (k <= yStripsort.length - 1 && yStripsort[k].getY() - yStripsort[j].getY() < distLR) {
int d = yStripsort[j].sqrDist(yStripsort[k]);
if (d < minDist) {
minDist = d;
}
k++;
}
}
return minDist;
}