Найти ближайшую точку относительно объекта без использования формулы расстояния в Java

Question

Если у меня есть объект со свойствами x a y, как я могу определить, какая точка массива является ближайшей, не используя формулу расстояния?

Answer 1

Вы не можете получить точный результат без использования некоторого варианта формулы расстояния.Но вы можете сохранить несколько циклов, не забирая квадратный корень по факту;сравнение останется действительным.

r = dx ² + dy ²

Answer 2

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

//The following code does not return the closest point, 
//but it somewhat does what you need and complies with 
//your requirement to not use the distance formula
//it finds the sum of x and y displacements

Point destination=...  
Point nearestPoint= points.get(0);
for (Point p : points){
    closenessCoefficient= Math.abs(destination.x-p.x) + Math.abs(a.destination-p.y);
    nearestPoint=Math.Min(closenessCoefficient, nearestPoint);
}
return nearestPoint;

Answer 3

Если вам нужно найти именно ближайшего соседа, нет способа обойти формулу расстояния, по крайней мере, для пары точек.Как уже указывалось, вы можете избежать оценки дорогостоящего sqrt в большинстве случаев, просто сравнивая квадрат расстояния r ^ 2 = x ^ 2 + y ^ 2.из точек, разбросанных по большому диапазону расстояний, вы можете сначала использовать приближение, как показано здесь http://www.flipcode.com/archives/Fast_Approximate_Distance_Functions.shtml.Тогда вы можете рассчитать формулу реального расстояния только для точек, ближайших, как указано в приближении.На архитектурах, где умножение также стоит дорого, это может иметь большое значение.На современных архитектурах x86 / x86-64 это не должно иметь большого значения.