2 Java methods java.lang.NullPointerException

Question

I"m getting an error java.lang.NullPointerException error on the following code.

The algorithm:

1. If n ≤ 3 find the closest points by brute force and stop.
2. Find a vertical line V such that divides the input set into two disjoint subsets PL and PR of size as equal as possible. Points to the left or on the line belong PL and points to the right or on the line belong to PR. No point belongs to both since the sets are disjoint.
3. Recursively find the distance δL of a closest pair of points in PL and the distance δR of a closest pair in PR.
4. Let δ = min(δL, δR). The distance of a pair of closest points in the input set P is either that of the points found in the recursive step (i.e., δ) or consists of the distance between a point in PL and a point in PR.
   1. The only candidate points one from PL and one from PR must be in a vertical strip consisting of a line at distance δ to the left of the line V and a line at distance δ to the right of V
   2. Let YV be an array of the points within the strip sorted by non-decreasing y coordinate (i.e., if i ≤ j then YV [i] ≤ YV [j]).
   3. Starting with the first point in YV and stepping trough all except the last, check the distance of this point with the next 7 points (or any that are left if there are not as many as 7). If a pair is found with distance strictly less than δ then assign this distance to δ.
5. Return δ.

Bottom line is that,it uses a conceptual sweep line and recursion to find the closest points in the Euclidean space.

Now the methods that I have to write:

• public static int cP(pointSet P).

  This does methods the preparatory work for the recursive part of the algorithm and calls the method closestPairAux for the recursive part.

• public static int cPA(Point [] X, Point [] Y). This method carries out the recursive part of the algorithm; that is, the bulk of the work.

Other methods and classes

A point is represented in the plane by an object of the class Point. This does the obvious thing; it holds the x and y coordinates as numbers so that if P is an object of type Point then P.x and P.y

The set of input points is represented by an object of the class PointSet. As this is a set there can be no repetition of a point and we cannot assume any ordering on the elements.

• public static PointSet gP(String f).

  This opens a file called f and reads points from it.

• public Point nP(PointSet P).

  This is used to iterate over the points in P. The algorithm closestPair is implemented by the method

• public static Point closestPair(PointSet P).

  1. if n = 2 then return (x1 − x2)^2 + (y1 − y2)^2
  2. else
  3. d ← 0
  4. for i ← 1 to n − 1 do
  5.    for j ← i + 1 to n do
  6.      t ← (xi − xj)^2 + (yi − yj)^2
  7.      if t < d then
  8.       d ← t
  9. return d

• public static PointSet generatePoints(int n).

  This returns a set of n points, whose coordinates are integers.

• public Point[] sort(char c).

  This returns the points in the point set in an array sorted in non-decreasing order by coordinate as indicated by the parameter c. This parameter takes either the value ’x’ or the value ’y’, an exception UnknownSortOptionException is raised otherwise.

This what I wrote so far:

I decide that the first method should do the trivial case,n=<3, and then call the aux method.

  public static int cP(PointSet P) 
        throws TrivialClosestPairException, UnknownSortOptionException
{
           int distance = 0;// a method form the Poirnt class that calculate the square                              distance between this point and another point
           Point[] x = P.sort('x');
    Point[] x = P.sort('y');

        distance = cPA(x, y); **->here**

    return distance;

}

Is this method defined as it should?

An the second one: Which I need big time help on this one.

public static int cPA(Point[] X, Point[] Y) 
        throws TrivialClosestPairException, UnknownSortOptionException
{
    if (X.length<4){
         return PointSet.nCP(new PointSet (X));

 }

    int V = X[(int) Math.ceil(( (double) X.length/2)-1)].getX();


    Point[] PL = Arrays.copyOfRange(X,(int) 0,(int) Math.ceil(X.length/2));
    Point[] PR = Arrays.copyOfRange(X,(int) Math.floor(X.length/2), (int) X.length-1);


     int distance = Math.min(cPA(PL,Y),cPAPR,Y));**->here**

    Point[] shortDist = new Point[Y.length];


       int n = 0;


     for (int i = 0; i <Y.length; i++)
{

     int A = Y[i].getY();
      if ((V-A)*(V-A) <= distance)
  {

   shortDist[n] = Y[i];

       }
    }


    for (int i =0; i< shortDist.length -1; i++)
   {


  for (int r = i+1; r <shortDist.length-1 && r< i + 7; r ++){
     distance = Math.min(d, shortDist[i].sqrDist(shortDist[r]));**->here**

 }
  }

 return distance;**->here**

 }

Now when I define the following class to test my methods

     public class Test{
public static void main(String [ ] args)
 {
   ClosestPair.closestPairCheck( 10, 10);

//Generates t sets of points of size n and obtains the squared distance of a claimed closest pair using your implementation of the method closestPair for each set. If all results are correct then a message reporting this is returned, else failure is reported. No further information is given. Note that t must be strictly positive (an exception Invalid- NumberOfTestsException is raised otherwise). } }

I get the following Exception in thread "main" java.lang.NullPointerException in the 3 spots when I give the variable distance values(I note it above)...What should I do?

Answer 1

Okay, lets have a look at your code. First, a small hint: for code to be posted on stackoverflow (and other stackexchange sites) better use only spaces for indentation, since tabs look bad.

So, here your code again, properly indented (by the way Emacs with JDEE did it - looks like I didn't configure it right, or it had some problems figuring out your code), and with my comments interspersed.

public static int closestPairAux(Point[] X, Point[] Y) 

So, again the question: what are the meanings of those two parameter arrays? Are they both containing the same points, or other ones? Why are you giving both arrays? When you have answered this, give them better names.

Other than this, give your method a documentation comment. What arguments does it receive, what does it returns? (It does not return the distance, but the square of the distance, if I understand right.)

    throws TrivialClosestPairException, UnknownSortOptionException
{
    if (X.length<4){
        return PointSet.naiveClosestPair(new PointSet (X));
    }

Okay, here you have the end of recursion for small arrays.

    int V = X[(int) Math.ceil(( (double) X.length/2)-1)].getX();

If I understand right, you are trying to get the middle element of the array here. This way would be clearer:

int middleIndex = X.length/2;
int V = X[middleIndex].getX();

In Java, integer division works by rounding-towards-zero - so the middleIndex for an array of length 20 or 21 is both 10. (If you want it to be 9 in the first case, subtract 1 before dividing.)

Of course you could write it as int V = X[X.length/2].getX();, but you'll be able to use the middleIndex again in the next two statements.

    Point[] PL = Arrays.copyOfRange(X,(int) 0,(int) Math.ceil(X.length/2));
    Point[] PR = Arrays.copyOfRange(X,(int) Math.floor(X.length/2), (int) X.length-1);

As said, rewrite those two using the middleIndex as before. You also don't need to cast 0 and X.length-1 to int, they already are. (And have again a look at the documentation of Arrays.copyOfRange - the to index is exclusive.)

So, here you are splitting your X array into two (about) same-sized arrays, okay.

    int distance = Math.min(closestPairAux(PL,Y),closestPairAux(PR,Y));

Here is your recursive call. What are you doing here, in fact? Why are you giving these parameters to the recursive call? (Specially, why do both receive the same Y array?)

    Point[] shortDist = new Point[Y.length];

    int n = 0;
    for (int i = 0; i <Y.length; i++)
        {
            int A = Y[i].getX();
            if ((V-A)*(V-A) <= distance)
                {
                    shortDist[n] = Y[i];
                }
        }

So, now you are going through your Y array, collecting those elements which are near the divider in your new shortDist-array.

    for (int i =0; i< shortDist.length -1; i++)
        {
            for (int r = i+1; r <shortDist.length-1 && r< i + 7; r ++){
                d = Math.min(d, shortDist[i].sqrDist(shortDist[r]));
            }
        }

Is d the same as distance before?

    return d;
}

At all, it looks like an implementation of your algorithm, yes. Think a bit about my questions, and please at least run a compiler on the code to make sure it does not have some evident syntax errors (through typos). Add comments in your code at the right places (before a block of code), and test your algorithm for some (maybe random) example inputs, comparing it to the naive implementation (they should return both the same result, but your one is hopefully faster.)