주어진 Lat Lng 위치에서 특정 거리 내에있는 모든 Latitude Longitude 위치를 찾는 알고리즘

주어진 Lat Lng 위치에서 특정 거리 내에있는 모든 Latitude Longitude 위치를 찾는 알고리즘

---

위도 + 경도 위치가있는 장소 데이터베이스 (예 : 40.8120390, -73.4889650)가 주어지면 특정 위치에서 주어진 거리 내에있는 모든 위치를 어떻게 찾을 수 있습니까?

DB에서 모든 위치를 선택한 다음 하나씩 살펴보고 시작 위치에서 거리를 가져와 지정된 거리 내에 있는지 확인하는 것은 그리 효율적이지 않은 것 같습니다. DB에서 처음에 선택한 위치를 좁히는 좋은 방법이 있습니까? 좁혀진 위치 세트가있는 경우 (또는없는 경우) 여전히 거리를 확인하기 위해 하나씩 이동합니까, 아니면 더 좋은 방법이 있습니까?

내가 이것을하는 언어는별로 중요하지 않습니다. 감사!

---

위도 사이의 거리를 비교하여 시작하십시오. 각 위도는 약 111km (69 마일) 떨어져 있습니다. 범위는 (지구의 약간 타원 모양으로 인해) 적도에서 110.567km (68.703 마일)에서 극에서 69.407 (111.699km)까지 다양합니다. 두 위치 사이의 거리는 위도 사이의 거리와 같거나 더 큽니다.

이것은 경도에 대해서는 사실이 아닙니다. 각 경도의 길이는 위도에 따라 다릅니다. 그러나 데이터가 일부 지역 (예 : 단일 국가)에 한정된 경우 경도에 대한 최소 및 최대 경계도 계산할 수 있습니다.

---

계속하면 구형 지구를 가정하는 낮은 정확도의 빠른 거리 계산이 수행됩니다.

좌표가 {lat1, lon1} 및 {lat2, lon2} 인 두 점 사이의 대원 거리 d는 다음과 같이 지정됩니다.

d = acos(sin(lat1)*sin(lat2)+cos(lat1)*cos(lat2)*cos(lon1-lon2))

단거리에서 반올림 오차가 덜 발생하는 수학적으로 동등한 공식은 다음과 같습니다.

d = 2*asin(sqrt((sin((lat1-lat2)/2))^2 +
    cos(lat1)*cos(lat2)*(sin((lon1-lon2)/2))^2))

d는 라디안 단위의 거리입니다.

distance_km ≈ radius_km * distance_radians ≈ 6371 * d

(6371km 는 지구의 평균 반경입니다. )

이 방법 계산 요구 사항은 미미합니다. 그러나 결과는 작은 거리에서 매우 정확합니다.

---

그런 다음 주어진 거리에 있으면 더 정확한 방법을 사용하십시오.

Vincenty 역 공식 도 사용할 수 있지만 GeographicLib 는 내가 아는 가장 정확한 구현 입니다.

---

RDBMS를 사용하는 경우 위도를 기본 키로 설정하고 경도를 보조 키로 설정합니다. 위에서 설명한대로 위도 범위 또는 위도 / 경도 범위를 쿼리 한 다음 결과 집합에 대한 정확한 거리를 계산합니다.

모든 주요 RDBMS의 최신 버전은 기본적으로 지리적 데이터 유형 및 쿼리를 지원합니다.

---

현재 사용자의 위도, 경도 및 찾고자하는 거리를 기반으로 SQL 쿼리는 아래와 같습니다.

SELECT * FROM(
    SELECT *,(((acos(sin((@latitude*pi()/180)) * sin((Latitude*pi()/180))+cos((@latitude*pi()/180)) * cos((Latitude*pi()/180)) * cos(((@longitude - Longitude)*pi()/180))))*180/pi())*60*1.1515*1.609344) as distance FROM Distances) t
WHERE distance <= @distance

@latitude 및 @longitude는 지점의 위도와 경도입니다. 위도와 경도는 거리 테이블의 열입니다. pi 값은 22/7입니다.

---

PostgreSQL GIS 확장 이 도움이 될 수 있습니다. 이미 구현하려고 생각하는 많은 기능을 이미 구현했을 수 있습니다.

---

Tank´s Yogihosting

내 데이터베이스에는 Open Streep Maps의 테이블이 하나 있고 성공적으로 테스트했습니다.

거리는 미터 단위로 잘 작동합니다.

SET @orig_lat=-8.116137;
SET @orig_lon=-34.897488;
SET @dist=1000;

SELECT *,(((acos(sin((@orig_lat*pi()/180)) * sin((dest.latitude*pi()/180))+cos((@orig_lat*pi()/180))*cos((dest.latitude*pi()/180))*cos(((@orig_lon-dest.longitude)*pi()/180))))*180/pi())*60*1.1515*1609.344) as distance FROM nodes AS dest HAVING distance < @dist ORDER BY distance ASC LIMIT 100;

---

다음 질문이 도움이 될 수 있습니다.

• 지리적 근접성을 계산하는 공식
• 소수점 위도 / 경도의 최대 길이도?

---

biziclop이 언급했듯이 일종의 메트릭 공간 트리가 아마도 최선의 선택이 될 것입니다. 저는 kd- 트리와 쿼드 트리를 사용하여 이러한 종류의 범위 쿼리를 수행 한 경험이 있으며 놀랍도록 빠릅니다. 그들은 또한 쓰기가 그렇게 어렵지 않습니다. "내 데이터 세트에서이 다른 지점에 가장 가까운 지점은 무엇입니까?"와 같은 다른 흥미로운 질문에 답할 수 있으므로 이러한 구조 중 하나를 살펴 보는 것이 좋습니다.

---

필요한 것은 공간 검색입니다. Solr Spatial 검색을 사용할 수 있습니다 . 또한 lat / long 데이터 유형이 내장되어 있습니다 . 여기 에서 확인하십시오 .

---

위도-경도를 거리 계산에 도움이 될 수있는 미터법 형식 인 UTM 형식으로 변환 할 수 있습니다. 그러면 포인트가 특정 위치에 속하는지 쉽게 결정할 수 있습니다.

---

모든 언어가 허용된다고 말 했으므로 자연스러운 선택은 PostGIS입니다.

SELECT * FROM places
WHERE ST_DistanceSpheroid(geom, $location, $spheroid) < $max_metres;

WGS 데이텀을 사용하려면 다음과 같이 설정해야 $spheroid합니다.'SPHEROID["WGS 84",6378137,298.257223563]'

당신이 색인했다고 가정 places에 의해 geom열이 합리적으로 효율적이어야한다.

---

이 방정식을 확인하면 도움이 될 것 같습니다.

SELECT id, ( 3959 * acos( cos( radians(37) ) * cos( radians( lat ) ) * cos( radians( lng ) - radians(-122) ) + sin( radians(37) ) * sin( radians( lat ) ) ) ) AS distance FROM markers HAVING distance < 25 ORDER BY distance LIMIT 0 , 20;

참고 URL : https://stackoverflow.com/questions/5031268/algorithm-to-find-all-latitude-longitude-locations-within-a-certain-distance-fro