Java에서 거리 공식을 사용하지 않고 객체에 가장 가까운 점 찾기

Question

x와 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 아키텍쳐에서는 이것은별로 중요하지 않습니다.