Hi everyone,
I have an assignment where, given a list of points in 1 dimension (that is, they are points (x,0)), to find the closest pair recursively. I've been moving along pretty well and I think I have a sound algorithm in place, but I hit a roadblock.
My algorithm finds a median and divides the list about that median, then keeps dividing it down until the list has <3 points, then it calls a method called shortest, which calculates the distance and returns a 2 element array of the closest points. But this last time i've tried it, I've gotten a nullPointerException when it calls shortest. I was wondering if any of you guys could help.
Attached is my code, ClosestPair1D.java
///////////////
//Tom George
//Problem Set 4
//1 Dimensional Closest Pair Problem
///////////////
import java.awt.Point;
import java.util.Random;
import java.util.Arrays;
public class ClosestPair1D
{
public static void main(String[] args)
{ //Creates random number generator, array of points, and randomly sets their
//x and y values
Random randomGen = new Random();
Point[] points = new Point[8];
for (int i=0; i<points.length; i++)
points[i] = new Point(randomGen.nextInt(100),0);
sortPoints(points);
for(int i=0; i<points.length; i++)
System.out.println(points[i]);
for(int i=0; i<points.length-1; i++)
System.out.println(points[i].distance(points[i+1]));
Point[] closestPair = findClosestPairDC(points);
}
//Brute force Closest Pair implementation. Scans entire array for smallest point, returns
//a 2 element array of the closest pair of points. Expected running time is Theta(n)
static Point[] findClosestPairBF(Point[] points)
{
Point[] closestPair = new Point[2];
double minDistance = points[0].distance(points[1]); //assumes first 2 elements are
//closest pair
for (int i=0; i<points.length-1; i++){
if(points[i].distance(points[i+1])<minDistance){
minDistance = points[i].distance(points[i+1]);
Point min1 = new Point(points[i]);
Point min2 = new Point(points[i+1]);
closestPair[0] = min1;
closestPair[1] = min2;
//If it finds a smaller distance, it creates 2 points and places them
//into the closestPair array
}
}
return closestPair;
}
//Divide and conquer algorithm. Recursively divides the list about a median until the base
//case is reached, then the lists are merged together, and the closest pair is found and
//returned
static Point[] findClosestPairDC(Point[] points)
{
int median;
Point[] points1, points2;
if(points.length <=3)
return shortest(points);
else{
median = points.length/2;
if(points.length%2 == 1) //Checks for odd number of elements
{
points1 = new Point[median];
points2 = new Point[median+1];
for(int i=0;i<median;i++)
points1[i] = points[i];
for (int i=median;i<points.length; i++)
points2[i/2] = points[i];
}
else{
points1 = new Point[median];
points2 = new Point[median];
System.out.println(points1.length+" "+points2.length);
for(int i=0; i<median; i++)
points1[i] = points[i];
for (int i=median; i<points.length; i++)
points2[i/2] = points[i];
}
Point [] minLeft = findClosestPairDC(points1);
Point [] minRight = findClosestPairDC(points2);
System.out.println(minLeft[0]+" "+minRight[1]);
}
return points;
}
//Takes an array of 3 or less points and calculates their distance, returns closest pair
static Point[] shortest(Point[] points)
{
Point[] closest = new Point[2];
double minimum = points[0].distance(points[1]);
if(points.length < 1)
return points;
else{
for(int i = 0; i<points.length-1; i++)
{
if(points[i].distance(points[i+1])<minimum){
minimum = points[i].distance(points[i+1]);
Point min1 = new Point(points[i]);
Point min2 = new Point(points[i+1]);
closest[0] = min1;
closest[1] = min2;
}
}
}
return closest;
}
//Making my own sort for the array because I'm apparently not clever enough to use
//java.util.Arrays sort method. It's a O(n^2) Insertion Sort, which sorts the points
//by their x-coordinates.
static void sortPoints(Point[] points)
{
int in,out;
for (out = 1; out<points.length; out++)
{
double temp = points[out].getX();
in = out;
while(in>0 && points[in-1].getX() >=temp)
{
swap(points[in],points[in-1]);
in--;
}
double temp2 = points[in].getX();
temp2=temp;
}
}
//Swaps 2 Point objects in an array
static void swap(Point p1, Point p2)
{
Point temp = new Point ();
temp.setLocation(p2.getX(), p2.getY());
p2.setLocation(p1.getX(), p1.getY());
p1.setLocation(temp.getX(), temp.getY());
}
}