小编Pat*_*k88的帖子

我在以下代码中收到错误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 …