가장 가까운 이웃 알고리즘을 사용하여 구글지도 찾기

Question

내가 예를 들어

PHP

를 사용하여 구현됩니다의 좌표 (위도/경도)에 의해 가장 가까운 이웃을 발견하는 알고리즘을 찾기 위해 도와주세요 조정합니다. 우리는 1 개의 클라이언트와 2 개의 노드를 가지고있다. 노드 1 = 32.9697, -96.8032이고 노드 2 = 42.9697, -97.80322

각 노드는 주어진 좌표 (맵상의 위치)를 가진다.

클라이언트는 위도를 보내드립니다와 경도 시스템에 좌표가 클라이언트에서 수신 좌표가 1 또는 노드 2

내 문법을 용서하십시오 노드에 가까운 경우 시스템이 발견 할 것이다. 너의 친절한 반응을 바라 네. 사전에 감사합니다.

Answer 1

(가능한 한 적은 수의 대상이있는 경우) 다음 함수 (copied from here)를 사용하여 가장 가까운 대상을 찾기 위해 반복 할 수 있습니다.

function distance($lat1, $lng1, $lat2, $lng2, $miles = false) 
{ 
    $pi80 = M_PI/180; 
    $lat1 *= $pi80; 
    $lng1 *= $pi80; 
    $lat2 *= $pi80; 
    $lng2 *= $pi80; 

    $r = 6372.797; // mean radius of Earth in km 
    $dlat = $lat2 - $lat1; 
    $dlng = $lng2 - $lng1; 
    $a = sin($dlat/2) * sin($dlat/2) + cos($lat1) * cos($lat2) * sin($dlng/2) * sin($dlng/2); 
    $c = 2 * atan2(sqrt($a), sqrt(1 - $a)); 
    $km = $r * $c; 

    return ($miles ? ($km * 0.621371192) : $km); 
} 

가능한 많은 위치 (> = 10^4)가있는 경우 일부 데이터 만 계산하면 일부 구조 만 평가하면됩니다. 비록 데이터베이스 경계뿐만 아니라 폴에 대해서는 작동하지 않지만이 경우 Quadtree을 제안합니다. 그러한 경우에 필요한 경우 더 나은 솔루션을 찾을 수있을 것이라고 확신합니다 (귀하가 필요하지 않다고 가정 함).