javanullpointerexceptionmergesortdivide-and-conquerclosest-points

Java Find Closest Pair in Dataset gives NullPointerException


I am trying to find closest pair from a few different datasets. So far it works with the SmallerSet which has 12 points but when I change dataset which has 100 points . It's giving NullPointer Excepiton at the line that I add "--->" before the loop .I dont't figure it out to solve.

public static PointPair closestPair(Point2D.Double Px[], Point2D.Double Py[],int n) {
    PointPair closestpairLeft;
    PointPair closestpairRight;

    if (n <= 3) {
        if(n==2)
            return new PointPair(Px[0],Px[1]);
        else{
        PointPair p1=new PointPair(Px[0],Px[1]);
        PointPair p2=new PointPair(Px[0],Px[2]);
        PointPair p3=new PointPair(Px[1],Px[2]);

        if(p1.closerThan(p2)<0){
            if(p1.closerThan(p3)<0)
                return p1;
            else
                return p3;
        }
        else{
            if(p2.closerThan(p3)<0)
                return p2;
            else
                return p3;
        }
        }
    } else {
        int mid = n / 2;


        Point2D.Double Xl[] = Arrays.copyOfRange(Px, 0, mid);
        Point2D.Double Xr[] = Arrays.copyOfRange(Px, mid, n);

        Point2D.Double Yl[] = new Point2D.Double[Xl.length];
        Point2D.Double Yr[] = new Point2D.Double[Xr.length];


       ---> for (int i = 0, k = 0, j = 0; i < n; i++) {
            if (Py[i].getX() <= Xl[mid-1].getX()&& j<mid) {
                Yl[j++] = Py[i];
            } else if (k<mid){
                Yr[k++] = Py[i];

            }

        }

        closestpairLeft=closestPair(Xl,Yl,mid);
        closestpairRight=closestPair(Xr,Yr,n-mid);
    }

Solution

  • Do it as follows:

    for (int i = 0, k = 0, j = 0; i < n && i < Py.length && (mid - 1) < Xl.length && j < Yl.length
            && k < Yr.length; i++) {
        if (Py[i] != null && Xl[mid - 1] != null && Py[i].getX() <= Xl[mid - 1].getX() && j < mid) {
            Yl[j++] = Py[i];
        } else if (k < mid) {
            Yr[k++] = Py[i];
        }
    }
    

    Note that I have checked not just Py[i] and Xl[mid-1] for null but also the bounds of the arrays to avoid ArrayIndexOutOfBoundsException.