Javaの距離式を使用せずにオブジェクトに最も近いポイントを見つける

Question

xとyのプロパティを持つオブジェクトがある場合、距離式を使用せずに配列のどのポイントが最も近いかをどのようにして知ることができますか？

Answer 1

一部のバリアント式を使用せずに正確な結果を得ることはできません。しかし、あなたはすることができます事実の後に平方根を取っていないことによっていくつかのサイクルを保存します。比較は有効なままです。

Answer 2

DY R = DX +あなたが正確な距離を気にしない場合、あなたはおそらく、あなたの元の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

最も近いネイバーを正確に見つけなければならない場合は、少なくとも2つの点について距離式を評価する方法はありません。すでに指摘したように、距離平方根r^2 = x^2 + y^2を単に比較すると、ほとんどの場合、高価なsqrtを評価することは避けられます。

ただし、大きな距離の範囲に広がっている点数が多い場合は、ここに示すhttp://www.flipcode.com/archives/Fast_Approximate_Distance_Functions.shtmlのような近似値を使用することができます。次に、近似によって与えられた最も近い点についてのみ、実際の距離式を計算することができます。乗算にもコストがかかるアーキテクチャでは、これは大きな違いを生む可能性があります。現代のx86/x86-64アーキテクチャでは、このことはあまり重要ではありません。