Поиск ближайшей точки

В своей программе я пытаюсь найти ближайшую точку от начальной позиции (0,0), а затем снова "двигаться" к следующей точке. Точки считываются через файл. Следующая точка, к которой я пытаюсь перейти, - это «ближайшая» точка. Я использую теорему Пифагора, чтобы найти расстояние. Но что я могу сделать, чтобы «проверить» точку, в которую я собираюсь определить, был ли я уже в ней. Например, если точка 0,0, а затем она переходит в 1,1, как проверить, чтобы «сообщить» программе, что 0,0 больше не является вариантом?

public class PointsNStuff {
    public static void main(String [] args) {

        final int P = StdIn.readInt();
        double [] x = new double[P];
        double [] y = new double[P];
        double [] visit= new double[P]; //Set an array that stores points that have been visited already
        double [] math= new double[P]; //Set an array that stores the distance to all the points


        for( int i= 0; i< P; i++){ //Store the values from the text file
            x[i] = StdIn.readDouble();
            y[i] = StdIn.readDouble();
        }

        double lowX = x[0];

        double lowY = y[0];

        double highX = x[0];

        double highY = y[0];

        //Find the lowest X and the lowest Y values:

        for (int i = 0; i < P; i++){
            if (lowX > x[i])
                lowX = x[i];
        }for (int i = 0; i < P; i++){
            if (lowY > y[i])
                lowY = y[i];
        }
        for (int i = 0; i < P; i++){
            if (highX < x[i])
                highX = x[i];
        }
        for (int i = 0; i < P; i++){
            if (highY < y[i])
                highY = y[i];
        }
        System.out.println(lowX + " " + lowY);
        System.out.println(highX + " " + highY);
        System.out.println("");
        System.out.println(P);

        //Determine the closest point
        double xCoord=0.0;
        double yCoord=0.0;
        double dist = -1.0;
        for (int i= 0; i < P; i ++){ //Repeat entire section for all P (number of points)
            for (int j = 0; j < P; j++){ //Find the distance between current point and all other points. Go through all points (do the math).
                xCoord = x[j]; // # x point
                yCoord = y[j]; // # y point
                double save= Math.sqrt( ( (xCoord+x[j]) * (xCoord+x[j]) ) + ( (yCoord + y[j]) * (yCoord + y[j]) ) ); //Pythagorean theorem
                save = math[j]; //store the distance in the array slot
            }
            for (int j = 0; j < P; j++){
                if (dist < math[j]){
                    dist = math[j];

                    //What boolean check can I put here to double check whether I have visited this point already?

                    xCoord = x[j]; // set the two points to what number they should be at.
                    yCoord = y[j];
                }
            }
            System.out.println(xCoord + " " + yCoord);
        }
    }
}

Я не использовал никаких точек в массиве, который я назвал «визит». Любая помощь приветствуется! Спасибо!


java distance
person Darron Martinez    schedule 17.09.2014    source источник

Ответы (2)


arrow_upward
1
arrow_downward

Используйте ArrayList для хранения точек,

ArrayList<Double> x = new ArrayList<Double>();
ArrayList<Double> y = new ArrayList<Double>();

добавить точки в arraylist,

for( int i= 0; i< P; i++){ //Store the values from the text file
  x.add(StdIn.readDouble());
  y.add(StdIn.readDouble());
}

выберите точку в арайлисте,

x.get(i); insted of x[i];
y.get(i); insted of y[i];

и удалить уже использованные точки,

x.remove(new Double(used_x_value));
y.remove(new Double(used_y_value));

см. Class ArrayList

person snvrthn    schedule 17.09.2014

arrow_upward
1
arrow_downward

То, что у вас есть, является идеальным кандидатом для инкапсуляции! Я бы начал с размышлений о другом объекте, чтобы инкапсулировать концепцию «точки», о которой вы все время говорите:

class Point {
    private final double x;
    private final double y;

    public Point(double x, double y) {
        this.x = x;
        this.y = y;
    }

    public double getX() {
        return x;
    }

    public double getY() {
        return y;
    }
}

Одно небольшое предостережение: это предполагает, что у вас не будет дублирующихся пар x, y во входном файле. Если вы это сделаете, вам может потребоваться переопределить хэш-код и равно. Но если нет, это должно сработать. Затем вы можете поместить эти точки в структуру данных (см. HashSet) вот так:

import java.util.Set; import java.util.HashSet;

public class PointsNStuff {

    public static void main(String args[]) {

        Set<Point> pointsVisited = new HashSet<>();

        //when you visit a point, put it in the set like this
        //the numbers are just for example
        Point currentPoint = new Point(10.0, 12.0);
        pointsVisited.add(currentPoint);

        //now in the future you can check if you 'visited' this point
        if(!pointsVisited.contains(currentPoint)) {
            System.out.println("Haven't been to current point yet...");
        }

    }

}
person md_rasler    schedule 17.09.2014