2 Java方法java.lang.NullPointerException

Question

我在以下代码中收到错误java.lang.NullPointerException错误.

算法:

1. 如果n≤3通过蛮力找到最近的点并停止.
2. 找到垂直线V,使得将输入集分成两个不相交的子集PL和PR,其大小尽可能相等.左侧或线上的点属于PL并指向右侧或线上属于PR.没有一点属于两者,因为集合是不相交的.
3. 递归地找到PL中最接近点对的距离δL和PR中最近对的距离δR.
4. 设δ= min(δL,δR).输入集P中的一对最近点的距离是在递归步骤中找到的点的距离(即,δ),或者由PL中的点与PR中的点之间的距离组成.
   1. 来自PL的唯一候选点和来自PR的一个候选点必须位于垂直条带中,该垂直条带由线V左侧的距离δ处的线和V的右侧的距离δ处的线组成.
   2. 设YV是条带内的点的数组,按非递减y坐标排序(即,如果i≤j,则YV [i]≤YV[j]).
   3. 从YV中的第一个点开始,然后踩到除最后一个之外的所有点,检查该点与接下来的7个点的距离(如果没有多达7个点,则检查剩余的点).如果发现距离严格小于δ,则将该距离指定为δ.
5. 返回δ.

底线是,它使用概念扫描线和递归来找到欧几里德空间中最近的点.

现在我要编写的方法:

• public static int cP(pointSet P).

  这确实为算法的递归部分的准备工作提供方法,并为递归部分调用方法nearestPairAux.

• public static int cPA(Point [] X, Point [] Y). 该方法执行算法的递归部分; 也就是说,大部分工作.

其他方法和类

点在Point中由Point类的对象表示.这是显而易见的事情; 它将x和y坐标保持为数字,这样如果P是Point类型的对象,那么Px和Py

输入点集由PointSet类的对象表示.因为这是一个集合,所以不能重复一个点,我们不能假设元素的任何排序.

• public static PointSet gP(String f).

  这将打开一个名为f的文件并从中读取点.

• public Point nP(PointSet P).

  这用于迭代P中的点.该算法closestPair由该方法实现

• public static Point nearestPair(PointSet P).

  1. 如果n = 2则返回(x1-x2)^ 2 +(y1-y2)^ 2
  2. 其他
  3. d←0
  4. 因为我←1到n - 1做
  5.    对于j←i + 1到n做
  6.      t←(xi-xj)^ 2 +(yi-yj)^ 2
  7.      如果t <d那么
  8.       d←t
  9. 返回d

• public static PointSet generatePoints(int n).

  这将返回一组n个点,其坐标为整数.

• public Point[] sort(char c).

  这将返回按照参数c所示的坐标以非递减顺序排序的数组中的点中的点.此参数采用值"x"或值"y",否则引发异常UnknownSortOptionException.

这是我到目前为止写的:

我决定第一种方法应该做普通的情况,n = <3,然后调用aux方法.

  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;

}

这个方法是否应该定义？

第二个:我需要大量的时间来帮助这个.

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**

 }

现在,当我定义以下类来测试我的方法时

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

//生成t组大小为n的点,并使用您对每个set的方法nearestPair的实现获得声明的最近对的平方距离.如果所有结果都正确,则返回报告此消息的消息,否则报告失败.没有提供进一步的信息.请注意,t必须严格为正(否则会引发Invalid- NumberOfTestsException异常).}}

当我给出变量距离值时,我在3个点中的线程"main"java.lang.NullPointerException中得到以下异常(我在上面注意到了)......我该怎么办？

Answer 1

好的，让我们看看你的代码。首先，一个小提示：对于要在 stackoverflow（和其他 stackexchange 站点）上发布的代码，最好仅使用空格进行缩进，因为制表符看起来很糟糕。

因此，这里再次是您的代码，正确缩进（通过带有 JDEE 的 Emacs 的方式做到这一点 - 看起来我没有正确配置它，或者它在计算您的代码时遇到了一些问题），并散布着我的评论。

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

那么，问题又来了：这两个参数数组的含义是什么？它们都包含相同的点还是其他的点？为什么要提供两个数组？当你回答完这个问题后，给他们起更好的名字。

除此之外，给你的方法一个文档注释。它接收什么参数，返回什么？（如果我理解正确的话，它不会返回距离，而是返回距离的平方。）

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

好的，小数组的递归到此结束。

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

如果我理解正确的话，您正在尝试在这里获取数组的中间元素。这种方式会更清晰：

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

在 Java 中，整数除法通过向零舍入进行工作 - 因此middleIndex长度为 20 或 21 的数组都是 10。（如果您希望在第一种情况下它是 9，请在除法之前减去 1。）

当然，您可以将其写为int V = X[X.length/2].getX();，但您可以middleIndex在接下来的两个语句中使用 Again 。

    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);

如前所述，middleIndex像以前一样使用 重写这两个。您也不需要强制转换0和X.length-1强制转换，它们已经是这样了。（再次查看 Arrays.copyOfRange 的文档 -to索引是独占的。）

所以，在这里你将你的 X 数组分成两个（大约）相同大小的数组，好吧。

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

这是您的递归调用。事实上，你在这里做什么？为什么要将这些参数提供给递归调用？（特别是，为什么两者都收到相同的 Y 数组？）

    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];
                }
        }

所以，现在您正在遍历 Y 数组，收集新数组中靠近分隔线的那些元素shortDist。

    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]));
            }
        }

和以前d一样吗distance？

    return d;
}

无论如何，它看起来像是你的算法的实现，是的。思考一下我的问题，请至少对代码运行编译器，以确保它没有一些明显的语法错误（通过拼写错误）。在代码中的正确位置（在代码块之前）添加注释，并针对一些（可能是随机的）示例输入测试您的算法，将其与简单的实现进行比较（它们应该返回相同的结果，但希望您的结果是快点。）