数学在Java中不使用距离公式就可以找到相对于对象的最近点

Question

如果我有一个属性为x和y的对象，我如何在不使用距离公式的情况下判断数组中哪个点最接近

Answer 1

如果不使用距离公式的某些变体，就无法得到准确的结果。但是你可以通过事后不取平方根来节省一些周期；这种比较仍然有效

r = dx² + dy²

Answer 2

如果您必须精确地找到最近的邻居，则无法计算距离公式，至少对于几个点。正如已经指出的，当简单地比较距离平方r^2=x^2+y^2时，可以避免在大多数情况下评估昂贵的sqrt

但是，如果有大量的点分布在很大的距离范围内，则可以首先使用类似于此处所示的http://www.flipcode.com/archives/Fast_Approximate_Distance_Functions.shtml的近似值。然后，您可以仅为近似值给出的最近点计算实际距离公式。在乘法也很昂贵的体系结构上，这会产生很大的不同。但是，在现代x86/x86-64体系结构上，这应该无关紧要

Answer 3

如果你不关心确切的距离，你也许可以利用你的源点和目的点的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;