Closest Pair

Sample sets:
Set of 25 points
Set of 50 points

My classes:

Point - > double x, double y
Point1 -> int id
- This class inherits from Point and it will be instantiated in an array to be sorted by x values, for each point in my array I read in a x and y value and put it in the Xarray.
Point2 - int id
- This class inherits from Point and it will be instantiated in an array to be sorted by y values, initially I initialized this Yarray by using the sorted x array and the offset of my x array set the value of id.
PointPair ->holds the two points and the shortest distance.
Closest Pair - > This is my class that does all the work.

ClosestPair Class defined

This class has two methods that do most of the work.

Method 1 -> Non-recursive
1. Read in points into Xarray.
2. Sort the Xarray by it's x values
3. create Yarray with Point2's and put the values of each element in the Xarray and it's Xarray offset in the Point2's in the Yarray.
4. Sort the Yarray by it's Y values
5. Create a blank array of Point2's - I called it the Zarray.
6. Call the recursive method (method2 below) with (Xarray, Yarray, Zarray, 0, Xarray.length)
Method 2 - the recursive method
1. if(2 points in array) return distance
2. if(3 points in array) find the shortest distance between 3 points and return it.
3. find the middle of the Xarray.
4. in a for loop copy the values of the Yarray that are in the first half of the Xarray to the first half of the Zarray, and copy the values from the Yarray that are in the second half of the Xarray into the second half of the Zarray. Here is the code I used:
```
      int f = start;     
      int g = middle + 1; 
      for (int i = l; i <= r; i++)
         if (y[i].p > m) 
              z[g++] = y[i];
         else 
             z[f++] = y[i];
```
5. PairPoint distance1 = Call recursive method with (x, z, y, start, middle)
6. PairPoint distance2 = Call recursive method with (x, z, y, middle+1, end)
7. find smallest between distance1 and distance2
8. Then you check the distances of the points within the threshold of your midpoint.
  1. find all the points within the threshold and put them in Zarray.
  2. Check each point in the Zarray with the next fifteen if there are fifteen points in the array.
  3. If the distance is smaller than the best distance found in step 7 then change your best distance and points in the PointPair.
9. Return the best PairPoint