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

Question

Так представьте себе, я создал Vector класс с двумя переменными x и y в Java:

public class Vector { 
    private int x; 
    private int y; 

    public Vector(int x, int y) { 
     this.x = x; 
     this.y = y; 
    } 

    public int getX() { 
     return this.x; 
    } 

    public int getY(){ 
     return this.y; 
    } 
} 

Тогда я craeted в ArrayList векторов :

private List<Vector> vecs = new ArrayList<Vector>(); 

Я создал в этом списке:

8,9 
10,5 
83473834,938849584985 
etc ... 

Теперь я хочу получить ближайший вектор к другому вектору. Пример:

private List<Vector> vecs = new ArrayList<Vector>(); 
private Vector vec = new Vector(1,1); 

for(Vector vector:vecs) { 
    //What do i put here?? 
} 

Так что я положил в цикл, чтобы сделать его выбрать ближайший вектор из списка вектора?

Answer 1

Я хотел бы начать с добавлением методы к Vector классу, distanceTo, который вычисляет расстояние от этого вектора в другой:

public double distanceTo(Vector vec) { 
    double dx = x - vec.x;    //calculate the diffrence in x-coordinate 
    double dy = y - vec.y;    //calculate the diffrence in y-coordinate 
    return Math.sqrt(dx*dx + dy*dy);  //use the distance formula to find the difference 
} 

И тогда вы можете написать следующий метод, который возвращает ближайший вектор в список для данного вектора:

public static Vector closest(Vector target, List<Vector> list) { 
    Vector closest = list.get(0);         //this variable will kep track of the closest vector we have found yet. We simply start with the first one 

    for(int i = 1; i < list.size(); i++) {      //loop over the list, skipping the first entry 
     Vector curr = list.get(i);        //get the current vector from the list 
     if (target.distanceTo(curr) < target.distanceTo(closest)) //if the current vector is closer to target than the closest one yet 
      closest = curr;          //keep the current vector as the new closest one 
    } 

    return closest;            //return the resulting vector 
} 

Этот метод может быть использован, как это:

Vector target = new Vector(1, 2); 

List<Vector> vecs = new ArrayList<Vector>(); 
vecs.add(new Vector(-2, 6)); 
vecs.add(new Vector(1, 3)); 
vecs.add(new Vector(4, 0)); 
vecs.add(new Vector(8, -1)); 

Vector closest = findClosest(target, vecs); 

Как вы можете видеть, я попытался объяснить код как можно лучше, но не стесняйтесь задавать дополнительные вопросы!

EDIT другой метод:

public double distanceTo(Vector vec1,Vector vec2) { 
     double dx = vec2.x - vec1.x;    //calculate the diffrence in x-coordinate 
     double dy = vec.y - vec1.y;    //calculate the diffrence in y-coordinate 
     return Math.sqrt(dx*dx + dy*dy);  //use the distance formula to find the difference 
    } 

Это если вы не можете поместить его в вектор класса

Answer 2

Это основное программирование вопрос. Он не связан с OpenGL. Простой линейный поиск может выглядеть следующим образом:

private List<Vector> vecs = new ArrayList<Vector>(); 

private Vector vec = new Vector(1,1); 

Vector minDistanceVector = null; 
int minDistanceSquared = Integer.MAX_VALUE; 
for(Vector vector : vecs) { 
    //Calculate the distance 
    //This could be a member function of Vector 
    int dx = vector.getX() - vec.getX(); 
    int dy = vector.getY() - vec.getY(); 
    int squaredDistance = dx * dx + dy * dy; 

    if(squaredDistance < minDistanceSquared) { 
     minDistanceSquared = squaredDistance; 
     minDistanceVector = vector; 
    } 
} 

После этого, вы будете иметь самый близкий вектор в minDistanceVector. Я выбрал евклидово расстояние, потому что это, вероятно, то, что вы хотите. Но, конечно, можно использовать любое другое расстояние.

Если вы хотите что-то более эффективное, вам может понадобиться построить некоторую структуру данных ускорения над точками и запросить ее (например, сетку, kd-дерево, квадрант ...).