Skip to content

Commit 3ade5d6

Browse files
MarisaAfueraMarisaAfuera
committed
Refactorized ClosestPair.java in order to be compliant with java sun rules
1 parent 826e7b5 commit 3ade5d6

File tree

3 files changed

+424
-0
lines changed

3 files changed

+424
-0
lines changed

‎divideconquer/ClosestPair.java

Lines changed: 317 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,317 @@
1+
package divideconquer;
2+
3+
/**
4+
5+
* For a set of points in a coordinates system (10000 maximum),
6+
* ClosestPair class calculates the two closest points.
7+
8+
* @author: anonymous
9+
* @author: Marisa Afuera
10+
*/
11+
12+
public final class ClosestPair {
13+
14+
15+
/** Number of points */
16+
int numberPoints = 0;
17+
/** Input data, maximum 10000. */
18+
private Location[] array;
19+
/** Minimum point coordinate. */
20+
Location point1 = null;
21+
/** Minimum point coordinate. */
22+
Location point2 = null;
23+
/** Minimum point length. */
24+
private static double minNum = Double.MAX_VALUE;
25+
/** secondCount */
26+
private static int secondCount = 0;
27+
28+
/**
29+
* Constructor.
30+
*/
31+
ClosestPair(int points) {
32+
numberPoints = points;
33+
array = new Location[numberPoints];
34+
}
35+
36+
/** xPartition function: arrange x-axis.
37+
* @param a (IN Parameter) array of points <br/>
38+
* @param first (IN Parameter) first point <br/>
39+
* @param last (IN Parameter) last point <br/>
40+
* @return pivot index
41+
*/
42+
43+
public int xPartition(
44+
final Location[] a, final int first, final int last) {
45+
46+
Location pivot = a[last]; // pivot
47+
int pIndex = last;
48+
int i = first - 1;
49+
Location temp; // Temporarily store value for position transformation
50+
for (int j = first; j <= last - 1; j++) {
51+
if (a[j].x <= pivot.x) { // Less than or less than pivot
52+
i++;
53+
temp = a[i]; // array[i] <-> array[j]
54+
a[i] = a[j];
55+
a[j] = temp;
56+
}
57+
}
58+
i++;
59+
temp = a[i]; // array[pivot] <-> array[i]
60+
a[i] = a[pIndex];
61+
a[pIndex] = temp;
62+
return i; // pivot index
63+
}
64+
65+
/** yPartition function: arrange y-axis.
66+
* @param a (IN Parameter) array of points <br/>
67+
* @param first (IN Parameter) first point <br/>
68+
* @param last (IN Parameter) last point <br/>
69+
* @return pivot index
70+
*/
71+
72+
public int yPartition(
73+
final Location[] a, final int first, final int last) {
74+
75+
Location pivot = a[last]; // pivot
76+
int pIndex = last;
77+
int i = first - 1;
78+
Location temp; // Temporarily store value for position transformation
79+
for (int j = first; j <= last - 1; j++) {
80+
if (a[j].y <= pivot.y) { // Less than or less than pivot
81+
i++;
82+
temp = a[i]; // array[i] <-> array[j]
83+
a[i] = a[j];
84+
a[j] = temp;
85+
}
86+
}
87+
i++;
88+
temp = a[i]; // array[pivot] <-> array[i]
89+
a[i] = a[pIndex];
90+
a[pIndex] = temp;
91+
return i; // pivot index
92+
}
93+
94+
/** xQuickSort function: //x-axis Quick Sorting.
95+
* @param a (IN Parameter) array of points <br/>
96+
* @param first (IN Parameter) first point <br/>
97+
* @param last (IN Parameter) last point <br/>
98+
*/
99+
100+
public void xQuickSort(
101+
final Location[] a, final int first, final int last) {
102+
103+
if (first < last) {
104+
int q = xPartition(a, first, last); // pivot
105+
xQuickSort(a, first, q - 1); // Left
106+
xQuickSort(a, q + 1, last); // Right
107+
}
108+
}
109+
110+
/** yQuickSort function: //y-axis Quick Sorting.
111+
* @param a (IN Parameter) array of points <br/>
112+
* @param first (IN Parameter) first point <br/>
113+
* @param last (IN Parameter) last point <br/>
114+
*/
115+
116+
public void yQuickSort(
117+
final Location[] a, final int first, final int last) {
118+
119+
if (first < last) {
120+
int q = yPartition(a, first, last); // pivot
121+
yQuickSort(a, first, q - 1); // Left
122+
yQuickSort(a, q + 1, last); // Right
123+
}
124+
}
125+
126+
/** closestPair function: find closest pair.
127+
* @param a (IN Parameter) array stored before divide <br/>
128+
* @param indexNum (IN Parameter) number coordinates divideArray <br/>
129+
* @return minimum distance <br/>
130+
*/
131+
132+
public double closestPair(final Location[] a, final int indexNum) {
133+
134+
Location[] divideArray = new Location[indexNum];
135+
System.arraycopy(a, 0, divideArray, 0, indexNum); // Copy previous array
136+
int totalNum = indexNum; // number of coordinates in the divideArray
137+
int divideX = indexNum / 2; // Intermediate value for divide
138+
Location[] leftArray = new Location[divideX]; //divide - left array
139+
//divide-right array
140+
Location[] rightArray = new Location[totalNum - divideX];
141+
if (indexNum <= 3) { // If the number of coordinates is 3 or less
142+
return bruteForce(divideArray);
143+
}
144+
//divide-left array
145+
System.arraycopy(divideArray, 0, leftArray, 0, divideX);
146+
//divide-right array
147+
System.arraycopy(
148+
divideArray, divideX, rightArray, 0, totalNum - divideX);
149+
150+
double minLeftArea = 0; //Minimum length of left array
151+
double minRightArea = 0; //Minimum length of right array
152+
double minValue = 0; //Minimum lengt
153+
154+
minLeftArea = closestPair(leftArray, divideX); // recursive closestPair
155+
minRightArea = closestPair(rightArray, totalNum - divideX);
156+
// window size (= minimum length)
157+
minValue = Math.min(minLeftArea, minRightArea);
158+
159+
// Create window. Set the size for creating a window
160+
// and creating a new array for the coordinates in the window
161+
for (int i = 0; i < totalNum; i++) {
162+
double xGap = Math.abs(divideArray[divideX].x - divideArray[i].x);
163+
if (xGap < minValue) {
164+
secondCount++; // size of the array
165+
} else {
166+
if (divideArray[i].x > divideArray[divideX].x) {
167+
break;
168+
}
169+
}
170+
}
171+
// new array for coordinates in window
172+
Location[] firstWindow = new Location[secondCount];
173+
int k = 0;
174+
for (int i = 0; i < totalNum; i++) {
175+
double xGap = Math.abs(divideArray[divideX].x - divideArray[i].x);
176+
if (xGap < minValue) { // if it's inside a window
177+
firstWindow[k] = divideArray[i]; // put in an array
178+
k++;
179+
} else {
180+
if (divideArray[i].x > divideArray[divideX].x) {
181+
break;
182+
}
183+
}
184+
}
185+
yQuickSort(firstWindow, 0, secondCount - 1); // Sort by y coordinates
186+
/* Coordinates in Window */
187+
double length = 0;
188+
// size comparison within window
189+
for (int i = 0; i < secondCount - 1; i++) {
190+
for (int j = (i + 1); j < secondCount; j++) {
191+
double xGap = Math.abs(firstWindow[i].x - firstWindow[j].x);
192+
double yGap = Math.abs(firstWindow[i].y - firstWindow[j].y);
193+
if (yGap < minValue) {
194+
length = Math.sqrt(Math.pow(xGap, 2) + Math.pow(yGap, 2));
195+
// If measured distance is less than current min distance
196+
if (length < minValue) {
197+
// Change minimum distance to current distance
198+
minValue = length;
199+
// Conditional for registering final coordinate
200+
if (length < minNum) {
201+
minNum = length;
202+
point1 = firstWindow[i];
203+
point2 = firstWindow[j];
204+
}
205+
}
206+
}
207+
else {
208+
break;
209+
}
210+
}
211+
}
212+
secondCount = 0;
213+
return minValue;
214+
}
215+
216+
/** bruteForce function: When the number of coordinates is less than 3.
217+
* @param arrayParam (IN Parameter) array stored before divide <br/>
218+
* @return <br/>
219+
*/
220+
221+
public double bruteForce(final Location[] arrayParam) {
222+
223+
double minValue = Double.MAX_VALUE; // minimum distance
224+
double length = 0;
225+
double xGap = 0; // Difference between x coordinates
226+
double yGap = 0; // Difference between y coordinates
227+
double result = 0;
228+
229+
if (arrayParam.length == 2) {
230+
// Difference between x coordinates
231+
xGap = (arrayParam[0].x - arrayParam[1].x);
232+
// Difference between y coordinates
233+
yGap = (arrayParam[0].y - arrayParam[1].y);
234+
// distance between coordinates
235+
length = Math.sqrt(Math.pow(xGap, 2) + Math.pow(yGap, 2));
236+
// Conditional statement for registering final coordinate
237+
if (length < minNum) {
238+
minNum = length;
239+
240+
}
241+
point1 = arrayParam[0];
242+
point2 = arrayParam[1];
243+
result = length;
244+
}
245+
if (arrayParam.length == 3) {
246+
for (int i = 0; i < arrayParam.length - 1; i++) {
247+
for (int j = (i + 1); j < arrayParam.length; j++) {
248+
// Difference between x coordinates
249+
xGap = (arrayParam[i].x - arrayParam[j].x);
250+
// Difference between y coordinates
251+
yGap = (arrayParam[i].y - arrayParam[j].y);
252+
// distance between coordinates
253+
length =
254+
Math.sqrt(Math.pow(xGap, 2) + Math.pow(yGap, 2));
255+
// If measured distance is less than current min distance
256+
if (length < minValue) {
257+
// Change minimum distance to current distance
258+
minValue = length;
259+
if (length < minNum) {
260+
// Registering final coordinate
261+
minNum = length;
262+
point1 = arrayParam[i];
263+
point2 = arrayParam[j];
264+
}
265+
}
266+
}
267+
}
268+
result = minValue;
269+
270+
}
271+
return result; // If only one point returns 0.
272+
}
273+
274+
/** main function: execute class.
275+
* @param args (IN Parameter) <br/>
276+
* @throws IOException If an input or output
277+
* exception occurred
278+
*/
279+
280+
public static void main(final String[] args) {
281+
282+
//Input data consists of one x-coordinate and one y-coordinate
283+
284+
ClosestPair cp = new ClosestPair(12);
285+
cp.array[0]=new Location(2,3);
286+
cp.array[1]=new Location(2,16);
287+
cp.array[2]=new Location(3,9);
288+
cp.array[3]=new Location(6,3);
289+
cp.array[4]=new Location(7,7);
290+
cp.array[5]=new Location(19,4);
291+
cp.array[6]=new Location(10,11);
292+
cp.array[7]=new Location(15,2);
293+
cp.array[8]=new Location(15,19);
294+
cp.array[9]=new Location(16,11);
295+
cp.array[10]=new Location(17,13);
296+
cp.array[11]=new Location(9,12);
297+
298+
System.out.println("Input data");
299+
System.out.println("Number of points: "+ cp.array.length);
300+
for (int i=0;i<cp.array.length;i++){
301+
System.out.println("x: " + cp.array[i].x + ", y: " + cp.array[i].y);
302+
}
303+
304+
cp.xQuickSort(cp.array, 0, cp.array.length-1); // Sorting by x value
305+
306+
double result; // minimum distance
307+
308+
result = cp.closestPair(cp.array, cp.array.length);
309+
// ClosestPair start
310+
// minimum distance coordinates and distance output
311+
System.out.println("Output Data");
312+
System.out.println("(" + cp.point1.x + ", " + cp.point1.y + ")");
313+
System.out.println("(" + cp.point2.x + ", " + cp.point2.y + ")");
314+
System.out.println("Minimum Distance : " + result);
315+
316+
}
317+
}

0 commit comments

Comments
 (0)