ClosestPair.java

packagecom.thealgorithms.divideandconquer;

/**
 * For a set of points in a coordinates system (10000 maximum), ClosestPair
 * class calculates the two closest points.
 */
publicfinalclassClosestPair {

/**
 * Number of points
 */
intnumberPoints;
/**
 * Input data, maximum 10000.
 */
Location[] array;
/**
 * Minimum point coordinate.
 */
Locationpoint1 = null;
/**
 * Minimum point coordinate.
 */
Locationpoint2 = null;
/**
 * Minimum point length.
 */
privatestaticdoubleminNum = Double.MAX_VALUE;

publicstaticvoidsetMinNum(doubleminNum) {
ClosestPair.minNum = minNum;
 }

publicstaticvoidsetSecondCount(intsecondCount) {
ClosestPair.secondCount = secondCount;
 }

/**
 * secondCount
 */
privatestaticintsecondCount = 0;

/**
 * Constructor.
 */
ClosestPair(intpoints) {
numberPoints = points;
array = newLocation[numberPoints];
 }

/**
 * Location class is an auxiliary type to keep points coordinates.
 */
publicstaticclassLocation {

doublex;
doubley;

/**
 * @param xpar (IN Parameter) x coordinate <br>
 * @param ypar (IN Parameter) y coordinate <br>
 */
Location(finaldoublexpar, finaldoubleypar) { // Save x, y coordinates
this.x = xpar;
this.y = ypar;
 }
 }

publicLocation[] createLocation(intnumberValues) {
returnnewLocation[numberValues];
 }

publicLocationbuildLocation(doublex, doubley) {
returnnewLocation(x, y);
 }

/**
 * xPartition function: arrange x-axis.
 *
 * @param a (IN Parameter) array of points <br>
 * @param first (IN Parameter) first point <br>
 * @param last (IN Parameter) last point <br>
 * @return pivot index
 */
publicintxPartition(finalLocation[] a, finalintfirst, finalintlast) {
Locationpivot = a[last]; // pivot
inti = first - 1;
Locationtemp; // Temporarily store value for position transformation
for (intj = first; j <= last - 1; j++) {
if (a[j].x <= pivot.x) { // Less than or less than pivot
i++;
temp = a[i]; // array[i] <-> array[j]
a[i] = a[j];
a[j] = temp;
 }
 }
i++;
temp = a[i]; // array[pivot] <-> array[i]
a[i] = a[last];
a[last] = temp;
returni; // pivot index
 }

/**
 * yPartition function: arrange y-axis.
 *
 * @param a (IN Parameter) array of points <br>
 * @param first (IN Parameter) first point <br>
 * @param last (IN Parameter) last point <br>
 * @return pivot index
 */
publicintyPartition(finalLocation[] a, finalintfirst, finalintlast) {
Locationpivot = a[last]; // pivot
inti = first - 1;
Locationtemp; // Temporarily store value for position transformation
for (intj = first; j <= last - 1; j++) {
if (a[j].y <= pivot.y) { // Less than or less than pivot
i++;
temp = a[i]; // array[i] <-> array[j]
a[i] = a[j];
a[j] = temp;
 }
 }
i++;
temp = a[i]; // array[pivot] <-> array[i]
a[i] = a[last];
a[last] = temp;
returni; // pivot index
 }

/**
 * xQuickSort function: //x-axis Quick Sorting.
 *
 * @param a (IN Parameter) array of points <br>
 * @param first (IN Parameter) first point <br>
 * @param last (IN Parameter) last point <br>
 */
publicvoidxQuickSort(finalLocation[] a, finalintfirst, finalintlast) {
if (first < last) {
intq = xPartition(a, first, last); // pivot
xQuickSort(a, first, q - 1); // Left
xQuickSort(a, q + 1, last); // Right
 }
 }

/**
 * yQuickSort function: //y-axis Quick Sorting.
 *
 * @param a (IN Parameter) array of points <br>
 * @param first (IN Parameter) first point <br>
 * @param last (IN Parameter) last point <br>
 */
publicvoidyQuickSort(finalLocation[] a, finalintfirst, finalintlast) {
if (first < last) {
intq = yPartition(a, first, last); // pivot
yQuickSort(a, first, q - 1); // Left
yQuickSort(a, q + 1, last); // Right
 }
 }

/**
 * closestPair function: find closest pair.
 *
 * @param a (IN Parameter) array stored before divide <br>
 * @param indexNum (IN Parameter) number coordinates divideArray <br>
 * @return minimum distance <br>
 */
publicdoubleclosestPair(finalLocation[] a, finalintindexNum) {
Location[] divideArray = newLocation[indexNum];
System.arraycopy(a, 0, divideArray, 0, indexNum); // Copy previous array
intdivideX = indexNum / 2; // Intermediate value for divide
Location[] leftArray = newLocation[divideX]; // divide - left array
// divide-right array
Location[] rightArray = newLocation[indexNum - divideX];
if (indexNum <= 3) { // If the number of coordinates is 3 or less
returnbruteForce(divideArray);
 }
// divide-left array
System.arraycopy(divideArray, 0, leftArray, 0, divideX);
// divide-right array
System.arraycopy(divideArray, divideX, rightArray, 0, indexNum - divideX);

doubleminLeftArea; // Minimum length of left array
doubleminRightArea; // Minimum length of right array
doubleminValue; // Minimum lengt

minLeftArea = closestPair(leftArray, divideX); // recursive closestPair
minRightArea = closestPair(rightArray, indexNum - divideX);
// window size (= minimum length)
minValue = Math.min(minLeftArea, minRightArea);

// Create window. Set the size for creating a window
// and creating a new array for the coordinates in the window
for (inti = 0; i < indexNum; i++) {
doublexGap = Math.abs(divideArray[divideX].x - divideArray[i].x);
if (xGap < minValue) {
ClosestPair.setSecondCount(secondCount + 1); // size of the array
 } else {
if (divideArray[i].x > divideArray[divideX].x) {
break;
 }
 }
 }
// new array for coordinates in window
Location[] firstWindow = newLocation[secondCount];
intk = 0;
for (inti = 0; i < indexNum; i++) {
doublexGap = Math.abs(divideArray[divideX].x - divideArray[i].x);
if (xGap < minValue) { // if it's inside a window
firstWindow[k] = divideArray[i]; // put in an array
k++;
 } else {
if (divideArray[i].x > divideArray[divideX].x) {
break;
 }
 }
 }
yQuickSort(firstWindow, 0, secondCount - 1); // Sort by y coordinates
/* Coordinates in Window */
doublelength;
// size comparison within window
for (inti = 0; i < secondCount - 1; i++) {
for (intj = (i + 1); j < secondCount; j++) {
doublexGap = Math.abs(firstWindow[i].x - firstWindow[j].x);
doubleyGap = Math.abs(firstWindow[i].y - firstWindow[j].y);
if (yGap < minValue) {
length = Math.sqrt(Math.pow(xGap, 2) + Math.pow(yGap, 2));
// If measured distance is less than current min distance
if (length < minValue) {
// Change minimum distance to current distance
minValue = length;
// Conditional for registering final coordinate
if (length < minNum) {
ClosestPair.setMinNum(length);
point1 = firstWindow[i];
point2 = firstWindow[j];
 }
 }
 } else {
break;
 }
 }
 }
ClosestPair.setSecondCount(0);
returnminValue;
 }

/**
 * bruteForce function: When the number of coordinates is less than 3.
 *
 * @param arrayParam (IN Parameter) array stored before divide <br>
 * @return <br>
 */
publicdoublebruteForce(finalLocation[] arrayParam) {
doubleminValue = Double.MAX_VALUE; // minimum distance
doublelength;
doublexGap; // Difference between x coordinates
doubleyGap; // Difference between y coordinates
doubleresult = 0;

if (arrayParam.length == 2) {
// Difference between x coordinates
xGap = (arrayParam[0].x - arrayParam[1].x);
// Difference between y coordinates
yGap = (arrayParam[0].y - arrayParam[1].y);
// distance between coordinates
length = Math.sqrt(Math.pow(xGap, 2) + Math.pow(yGap, 2));
// Conditional statement for registering final coordinate
if (length < minNum) {
ClosestPair.setMinNum(length);
 }
point1 = arrayParam[0];
point2 = arrayParam[1];
result = length;
 }
if (arrayParam.length == 3) {
for (inti = 0; i < arrayParam.length - 1; i++) {
for (intj = (i + 1); j < arrayParam.length; j++) {
// Difference between x coordinates
xGap = (arrayParam[i].x - arrayParam[j].x);
// Difference between y coordinates
yGap = (arrayParam[i].y - arrayParam[j].y);
// distance between coordinates
length = Math.sqrt(Math.pow(xGap, 2) + Math.pow(yGap, 2));
// If measured distance is less than current min distance
if (length < minValue) {
// Change minimum distance to current distance
minValue = length;
if (length < minNum) {
// Registering final coordinate
ClosestPair.setMinNum(length);
point1 = arrayParam[i];
point2 = arrayParam[j];
 }
 }
 }
 }
result = minValue;
 }
returnresult; // If only one point returns 0.
 }

/**
 * main function: execute class.
 *
 * @param args (IN Parameter) <br>
 */
publicstaticvoidmain(finalString[] args) {
// Input data consists of one x-coordinate and one y-coordinate
ClosestPaircp = newClosestPair(12);
cp.array[0] = cp.buildLocation(2, 3);
cp.array[1] = cp.buildLocation(2, 16);
cp.array[2] = cp.buildLocation(3, 9);
cp.array[3] = cp.buildLocation(6, 3);
cp.array[4] = cp.buildLocation(7, 7);
cp.array[5] = cp.buildLocation(19, 4);
cp.array[6] = cp.buildLocation(10, 11);
cp.array[7] = cp.buildLocation(15, 2);
cp.array[8] = cp.buildLocation(15, 19);
cp.array[9] = cp.buildLocation(16, 11);
cp.array[10] = cp.buildLocation(17, 13);
cp.array[11] = cp.buildLocation(9, 12);

System.out.println("Input data");
System.out.println("Number of points: " + cp.array.length);
for (inti = 0; i < cp.array.length; i++) {
System.out.println("x: " + cp.array[i].x + ", y: " + cp.array[i].y);
 }

cp.xQuickSort(cp.array, 0, cp.array.length - 1); // Sorting by x value

doubleresult; // minimum distance

result = cp.closestPair(cp.array, cp.array.length);
// ClosestPair start
// minimum distance coordinates and distance output
System.out.println("Output Data");
System.out.println("(" + cp.point1.x + ", " + cp.point1.y + ")");
System.out.println("(" + cp.point2.x + ", " + cp.point2.y + ")");
System.out.println("Minimum Distance : " + result);
 }
}