2 Java-метода java.lang.NullPointerException

Question

Я получаю сообщение об ошибке java.lang.NullPointerException в следующем коде.

Алгоритм:

1. Если n ≤ 3, найдите ближайшие точки по грубой силе истоп.
2. Найдите вертикальную линию V, которая делит входной набор на два непересекающихся подмножества PL и PR размера как можно более точного. Точки слева или на линии принадлежат PL и указывают вправо или налиния принадлежит PR. Ни одна точка не принадлежит обоим, поскольку множества не пересекаются.
3. Рекурсивно найдите расстояние δL ближайшей пары точек в PL и расстояние δR ближайшей пары в PR.
4. Пусть δ = min (δL, δR). Расстояние пары ближайших точек во входном наборе P равно расстоянию между точками, найденными на рекурсивном шаге (т. Е. Δ), или состоит из расстояния между точкойв PL и точка в PR.
   1. Единственные подходящие точки, одна из PL и одна из PR, должны быть в вертикальной полосе, состоящей из линии на расстоянии δ слева от линии V и линииe на расстоянии δ справа от V
   2. Пусть YV - массив точек в полосе, отсортированных по неубывающей координате y (т. е. если i ≤ j, то YV [i] ≤ YV [j]).
   3. Начиная с первой точки в YV и проходя через все, кроме последней, проверьте расстояние этой точки со следующими 7 точками (или с любой остающейся точкой, если их не так много, как 7).Если пара найдена с расстоянием, строго меньшим δ, тогда присвойте это расстояние δ.
5. Return δ.

Суть в том, что она используетКонцептуальная линия развертки и рекурсия для нахождения ближайших точек в евклидовом пространстве.

Теперь методы, которые я должен написать:

• public static int cP(pointSet P).

  Это делает методы подготовительной работы для рекурсивной части алгоритма и вызывает метод closestPairAux для рекурсивной части.

• public static int cPA(Point [] X, Point [] Y). Этот метод выполняет рекурсивную часть алгоритма;то есть основная часть работы.

Другие методы и классы

Точка представлена ​​в плоскости объектом класса Point.Это делает очевидную вещь;он хранит координаты x и y в виде чисел, так что если P является объектом типа Point, то Px и Py

Множество входных точек представляется объектом класса PointSet.Поскольку это набор, повторение точки не может быть выполнено, и мы не можем предполагать упорядочение элементов.

• public static PointSet gP(String f).

  Откроется файл с именем f.и считывает из него точки.

• public Point nP(PointSet P).

  Используется для перебора точек в P. Алгоритм closestPair реализован методом

• общедоступная статическая точка closestPair (PointSet P).

  1. , если n = 2, вернуть (x1 - x2) ^ 2 + (y1 - y2) ^ 2
  2. else
  3. d ← 0
  4. для i ← 1 до n - 1 do
  5. для j ← i + 1 до n do
  6. t ← (xi - xj) ^ 2 + (yi - yj) ^ 2
  7. , если t
  8. d ← t
  9. return d

• public static PointSet generatePoints(int n).

  Возвращает набор из n точек, координаты которых являются целыми числами.

• public Point[] sort(char c).

  Возвращает точки в наборе точек в массиве, отсортированном в неубывающем порядке по координатам, указанным параметром c.Этот параметр принимает либо значение «x», либо значение «y», иначе возникает исключение UnknownSortOptionException.

Это то, что я написал до сих пор:

Я решаючто первый метод должен выполнить тривиальный случай, n = <3, а затем вызвать метод aux. </p>

  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и получает в квадрате расстояние заявленной ближайшей пары, используя вашу реализацию метода closestPair для каждого набора.Если все результаты верны, то возвращается сообщение, сообщающее об этом, иначе сообщается об ошибке.Никакой дополнительной информации не предоставлено.Обратите внимание, что t должно быть строго положительным (в противном случае возникает исключение Invalid- NumberOfTestsException).}}

Я получаю следующее исключение в потоке "main" java.lang.NullPointerException в 3 местах, когда я даю переменные значения расстояния (я отмечаю это выше) ... Что мне делать

Answer 1

Хорошо, давайте посмотрим на ваш код. Во-первых, небольшая подсказка: для размещения кода в stackoverflow (и на других сайтах stackExchange) лучше использовать только пробелы для отступов, поскольку вкладки выглядят плохо.

Итак, здесь снова ваш код, с правильными отступами (кстати, Emacs с JDEE сделал это - похоже, я не настроил его правильно, или у него были некоторые проблемы с вычислением вашего кода), и мои комментарии разбросаны.

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 в следующих двух утверждениях.

    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 к int, они уже есть. (И снова взгляните на документацию 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;
}

Вообще, это похоже на реализацию вашего алгоритма, да. Подумайте немного о моих вопросах и, по крайней мере, запустите компилятор кода, чтобы убедиться, что в нем нет очевидных синтаксических ошибок (через опечатки). Добавьте комментарии в свой код в нужных местах (перед блоком кода) и протестируйте свой алгоритм для некоторых (возможно, случайных) примеров входных данных, сравнивая его с реализацией naive (они должны возвращать оба одинаковых результата , но ваш, надеюсь, быстрее.)