package closestPair; import java.util.*; /** The implementation of Shamos's Algorithm. */ public class Code { /** 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 { int distance = 0;// Point[] X = P.sort('x'); Point[] Y = P.sort('y'); distance = closestPairAux(X, Y);[B]->here return distance; } /** 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. The burden of work is going on here. Good luck! */ public static int closestPairAux(Point[] X, Point[] Y) throws TrivialClosestPairException, UnknownSortOptionException {//trivial case if (X.length<4){ return PointSet.naiveClosestPair(new PointSet (X)); } //get the middle element of the array here int centerIndex = X.length/2; int W = X[centerIndex].getX(); //the two disjoint sets devided by the conceptual sweep line Point[] PL = Arrays.copyOfRange(X,(int) 0,(int) Math.ceil(centerIndex)); Point[] PR = Arrays.copyOfRange(X,(int) Math.floor(centerIndex), (int) X.length-1); //the conquering part,taking the min from the two sets int distance = Math.min(closestPairAux(PL,Y),closestPairAux(PR,Y));->here Point[] shortDist = new Point[Y.length]; //part 4.b of the shamos algorithm int n = 0; for (int i = 0; i <Y.length; i++) { int Z = Y[i].getY(); if ((W-Z)*(W-Z) <= distance) { shortDist[n] = Y[i]; } } //part 4.c of the shamos algorithm // collecting those elements which are near the divider in the shortDist-array. for (int i =0; i< shortDist.length -1; i++) { for (int j = i+1; j <shortDist.length-1 && j< i + 7; j ++){ distance = Math.min(distance, shortDist[i].sqrDist(shortDist[j]));->here } } return distance; } }
package closestPair; public class Tests { public static void main(String [ ] args) throws InvalidNumberOfTestsException { ClosestPair.closestPairCheck(10, 400); } }
var
This content, along with any associated source code and files, is licensed under The Code Project Open License (CPOL)