Skip to content

Refactorized ClosestPair.java in order to be compliant with java sun rules #502

New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

Sign up for GitHub

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Merged
merged 1 commit into from
Sep 9, 2018
Merged

Refactorized ClosestPair.java in order to be compliant with java sun rules #502

Changes from all commits
Commits
Show all changes
1 commit
Select commit
File filter

Filter by extension

Filter by extension
Conversations
Failed to load comments.
Loading
Jump to
Jump to file
Failed to load files.
Loading
Diff view
Diff view
348 changes: 348 additions & 0 deletions divideconquer/ClosestPair.java
View file
Open in desktop
Original file line number Diff line number Diff line change
@@ -0,0 +1,348 @@
package divideconquer;

/**

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

* @author: anonymous
* @author: Marisa Afuera
*/

public final class ClosestPair {


/** Number of points */
int numberPoints = 0;
/** Input data, maximum 10000. */
private Location[] array;
/** Minimum point coordinate. */
Location point1 = null;
/** Minimum point coordinate. */
Location point2 = null;
/** Minimum point length. */
private static double minNum = Double.MAX_VALUE;
/** secondCount */
private static int secondCount = 0;

/**
* Constructor.
*/
ClosestPair(int points) {
numberPoints = points;
array = new Location[numberPoints];
}

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

public static class Location {

double x = 0;
double y = 0;

/**
* @param xpar (IN Parameter) x coordinate <br/>
* @param ypar (IN Parameter) y coordinate <br/>
*/

Location(final double xpar, final double ypar) { //Save x, y coordinates
this.x = xpar;
this.y = ypar;
}

}

public Location[] createLocation(int numberValues) {
return new Location[numberValues];

}

public Location buildLocation(double x, double y){
return new Location(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
*/

public int xPartition(
final Location[] a, final int first, final int last) {

Location pivot = a[last]; // pivot
int pIndex = last;
int i = first - 1;
Location temp; // Temporarily store value for position transformation
for (int j = 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[pIndex];
a[pIndex] = temp;
return i; // 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
*/

public int yPartition(
final Location[] a, final int first, final int last) {

Location pivot = a[last]; // pivot
int pIndex = last;
int i = first - 1;
Location temp; // Temporarily store value for position transformation
for (int j = 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[pIndex];
a[pIndex] = temp;
return i; // 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/>
*/

public void xQuickSort(
final Location[] a, final int first, final int last) {

if (first < last) {
int q = 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/>
*/

public void yQuickSort(
final Location[] a, final int first, final int last) {

if (first < last) {
int q = 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/>
*/

public double closestPair(final Location[] a, final int indexNum) {

Location[] divideArray = new Location[indexNum];
System.arraycopy(a, 0, divideArray, 0, indexNum); // Copy previous array
int totalNum = indexNum; // number of coordinates in the divideArray
int divideX = indexNum / 2; // Intermediate value for divide
Location[] leftArray = new Location[divideX]; //divide - left array
//divide-right array
Location[] rightArray = new Location[totalNum - divideX];
if (indexNum <= 3) { // If the number of coordinates is 3 or less
return bruteForce(divideArray);
}
//divide-left array
System.arraycopy(divideArray, 0, leftArray, 0, divideX);
//divide-right array
System.arraycopy(
divideArray, divideX, rightArray, 0, totalNum - divideX);

double minLeftArea = 0; //Minimum length of left array
double minRightArea = 0; //Minimum length of right array
double minValue = 0; //Minimum lengt

minLeftArea = closestPair(leftArray, divideX); // recursive closestPair
minRightArea = closestPair(rightArray, totalNum - 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 (int i = 0; i < totalNum; i++) {
double xGap = Math.abs(divideArray[divideX].x - divideArray[i].x);
if (xGap < minValue) {
secondCount++; // size of the array
} else {
if (divideArray[i].x > divideArray[divideX].x) {
break;
}
}
}
// new array for coordinates in window
Location[] firstWindow = new Location[secondCount];
int k = 0;
for (int i = 0; i < totalNum; i++) {
double xGap = 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 */
double length = 0;
// size comparison within window
for (int i = 0; i < secondCount - 1; i++) {
for (int j = (i + 1); j < secondCount; j++) {
double xGap = Math.abs(firstWindow[i].x - firstWindow[j].x);
double yGap = 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) {
minNum = length;
point1 = firstWindow[i];
point2 = firstWindow[j];
}
}
}
else {
break;
}
}
}
secondCount = 0;
return minValue;
}

/** bruteForce function: When the number of coordinates is less than 3.
* @param arrayParam (IN Parameter) array stored before divide <br/>
* @return <br/>
*/

public double bruteForce(final Location[] arrayParam) {

double minValue = Double.MAX_VALUE; // minimum distance
double length = 0;
double xGap = 0; // Difference between x coordinates
double yGap = 0; // Difference between y coordinates
double result = 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) {
minNum = length;

}
point1 = arrayParam[0];
point2 = arrayParam[1];
result = length;
}
if (arrayParam.length == 3) {
for (int i = 0; i < arrayParam.length - 1; i++) {
for (int j = (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
minNum = length;
point1 = arrayParam[i];
point2 = arrayParam[j];
}
}
}
}
result = minValue;

}
return result; // If only one point returns 0.
}

/** main function: execute class.
* @param args (IN Parameter) <br/>
* @throws IOException If an input or output
* exception occurred
*/

public static void main(final String[] args) {

//Input data consists of one x-coordinate and one y-coordinate

ClosestPair cp = new ClosestPair(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 (int i=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

double result; // 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);

}
}