위도, 경도 좌표 비교

StackOverflow https://stackoverflow.com/questions/35870

  •  09-06-2019
  •  | 
  •  

문제

15,000개 이상의 위도 및 경도 좌표 목록이 있습니다.X, Y 좌표가 주어지면 목록에서 가장 가까운 좌표를 찾는 가장 빠른 방법은 무엇입니까?

도움이 되었습니까?

해결책

당신은 보로노이 다이어그램.이렇게 하면 평면이 각 지점마다 하나씩, 주어진 각 지점에 가장 가까운 모든 지점을 포함하는 여러 영역으로 나뉩니다.

보로노이 다이어그램을 생성하고 데이터 구조 조회를 정렬하는 정확한 알고리즘에 대한 코드는 너무 커서 이 작은 편집 상자에 맞지 않습니다.:)

@리노르:이는 본질적으로 Voronoi 다이어그램을 만든 후 수행하는 작업입니다.그러나 직사각형 그리드를 만드는 대신 보로노이 다이어그램의 선과 거의 일치하는 분할선을 선택할 수 있습니다(이렇게 하면 분할선을 교차하는 영역이 더 적어집니다).각 하위 다이어그램에 가장 적합한 구분선을 따라 보로노이 다이어그램을 반으로 재귀적으로 나누면 조회하려는 각 지점에 대해 트리 검색을 수행할 수 있습니다.이를 위해서는 사전에 약간의 작업이 필요하지만 나중에 시간을 절약할 수 있습니다.각 조회는 로그 N 순서로 진행됩니다. 여기서 N은 포인트 수입니다.16번의 비교는 15,000번의 비교보다 훨씬 낫습니다!

다른 팁

나는 웹사이트를 위해 이것을 한 번 했다.즉.우편번호로부터 50마일 이내의 대리점을 찾으세요.나는 대권 계산 북쪽으로 50마일, 동쪽으로 50마일, 남쪽으로 50마일, 서쪽으로 50마일의 좌표를 구합니다.그것은 나에게 최소 및 최대 위도와 최소 및 최대 길이를 제공했습니다.그런 다음 데이터베이스 쿼리를 수행했습니다. 

select *
    from dealers
    where latitude  >= minlat
      and latitude  <= maxlat
      and longitude >= minlong
      and longitude <= maxlong

일부 결과는 여전히 50마일 이상 떨어져 있기 때문에 대권 공식 작은 좌표 목록을 다시 한 번 살펴보겠습니다.그런 다음 대상으로부터의 거리와 함께 목록을 인쇄했습니다.

물론 날짜 변경선이나 극 근처의 지점을 검색하려는 경우에는 이 방법이 작동하지 않습니다.하지만 북미 내 검색에는 효과적입니다!

당신이 설명하는 일반적인 개념은 가장 가까운 이웃 검색, 이러한 유형의 쿼리를 정확하거나 대략적으로 해결하는 다양한 기술이 있습니다.기본 아이디어는 공간 분할 기술을 사용하여 쿼리당 O(n)에서 쿼리당 (대략) O(log n)로 복잡성을 줄이는 것입니다.

KD-트리 및 KD-트리의 변형은 매우 잘 작동하는 것처럼 보이지만 쿼드 트리도 작동합니다.이러한 검색의 품질은 15,000개의 데이터 포인트 세트가 정적인지(참조 세트에 많은 데이터 포인트를 추가하지 않음) 여부에 따라 달라집니다.마운트(Mount)와 아리아(Arya)의 연구 대략적인 가장 가까운 이웃 라이브러리는 수학에 대한 기초 지식이 없어도 사용하고 이해하기 쉽습니다.또한 쿼리 유형 및 허용 범위에 유연성을 제공합니다.

오히려 수행하려는 횟수와 사용 가능한 리소스에 따라 다릅니다. 테스트를 한 번 수행하는 경우 O(log N) 기술이 좋습니다.서버에서 이 작업을 수천 번 수행하는 경우 결과를 직접 제공하거나 첫 번째 단계로 비트맵 조회 테이블을 구성하는 것이 더 빠릅니다.2GB의 비트맵은 전 세계 위도를 0.011도 픽셀(적도에서 1.2km)의 32비트 값으로 매핑할 수 있으며 메모리에 적합해야 합니다.단일 국가만 수행하거나 극을 제외할 수 있는 경우 지도가 더 작거나 해상도가 더 높을 수 있습니다.15,000개 지점의 경우 훨씬 더 작은 지도를 갖게 될 것입니다. 더 높은 해상도가 필요한 위도 우편번호 검색을 수행하기 위한 첫 번째 단계로 먼저 크기를 조정했습니다.요구 사항에 따라 매핑된 값을 사용하여 결과를 직접 가리키거나 후보 목록을 짧게 지정합니다(더 작은 맵이 허용되지만 더 큰 후속 처리가 필요함 - 더 이상 O(1) 조회 영역에 있지 않음) ).

가장 빠른 것이 무엇을 의미하는지 지정하지 않았습니다.코드를 작성하지 않고 빠르게 답변을 얻으려면 gpsbabel 반경 필터 전에.

귀하의 설명을 바탕으로 KD-트리 또는 R-트리와 같은 기하학적 데이터 구조를 사용하겠습니다.MySQL에는 이를 수행하는 SPATIAL 데이터 유형이 있습니다.다른 언어/프레임워크/데이터베이스에는 이를 지원하는 라이브러리가 있습니다.기본적으로 이러한 데이터 구조는 직사각형 트리에 포인트를 포함하고 반경을 사용하여 트리를 검색합니다.이는 충분히 빠르며 보로노이 다이어그램을 작성하는 것보다 더 간단하다고 생각합니다.나는 Voronoi 다이어그램의 추가 성능을 선호하여 추가된 복잡성을 지불할 준비가 될 수 있는 몇 가지 임계값이 있다고 생각합니다.

이 문제는 여러 가지 방법으로 해결될 수 있습니다.나는 먼저 이 문제에 접근하여 들로네 가장 가까운 지점을 서로 연결하는 네트워크.이는 오픈 소스 GIS 애플리케이션의 v.delaunay 명령을 사용하여 수행할 수 있습니다. 잔디.다음 중 하나를 사용하여 GRASS에서 문제를 완료할 수 있습니다. 네트워크 분석 모듈 잔디에서.또는 무료 공간 RDBMS를 사용할 수도 있습니다. PostGIS 거리 쿼리를 수행합니다.PostGIS 공간 쿼리는 BBOX 작업에 제한되지 않으므로 MySQL의 쿼리보다 훨씬 더 강력합니다.예를 들어:

SELECT network_id, ST_Length(geometry) from spatial_table where ST_Length(geometry) < 10;

경도와 위도를 사용하고 있으므로 아마도 회전타원체 거리 함수.공간 인덱스를 사용하면 PostGIS는 대규모 데이터세트에 대해 매우 잘 확장됩니다.

보로노이 다이어그램을 생성하더라도 x, y 좌표를 생성된 15,000개 영역 모두와 비교해야 한다는 의미입니다.더 쉽게 만들기 위해 내 마음에 가장 먼저 떠오른 것은 가능한 값 위에 일종의 그리드를 만들어서 동일한 경우 그리드의 상자 중 하나에 쉽게 배치하고 x/y 좌표를 지정할 수 있다는 것이었습니다. 영역 목록을 완료하려면 비교할 수 있는 후보를 빠르게 줄여야 합니다(그리드가 더 직사각형이기 때문에 영역이 여러 그리드 위치에 있을 수 있음).

성급한 최적화는 모든 악의 근원입니다.

15K 좌표는 그다지 많지 않습니다.15K 좌표를 반복하여 이것이 실제로 성능 문제인지 확인하는 것은 어떨까요?많은 작업량을 절약할 수 있고 알아차릴 수 없을 정도로 느려지는 일도 없을 것입니다.

이 좌표가 퍼져 있는 면적은 얼마나 됩니까?그들은 어느 위도에 있습니까?어느 정도의 정확도가 필요합니까?서로 상당히 가깝다면 지구가 둥글다는 사실을 무시하고 구형 기하학과 큰 원 거리를 다루기보다는 이것을 데카르트 평면으로 취급할 수 있습니다.물론, 적도에서 멀어질수록 경도는 위도에 비해 작아지기 때문에 일종의 스케일링 인자가 적절할 수도 있습니다.

상당히 간단한 거리 공식과 무차별 대입 검색으로 시작하여 시간이 얼마나 걸릴지, 결과가 충분히 정확한지 알아보고 마음에 들도록 하세요.

답변해 주신 모든 분들께 감사드립니다.

@톰, @크리스 업처치:좌표는 서로 상당히 가깝고, 약 800평방 킬로미터라는 비교적 작은 면적에 있습니다.표면이 평평하다고 가정할 수 있을 것 같습니다.요청을 계속해서 처리해야 하며 더 많은 웹 경험을 위해서는 응답이 충분히 빨라야 합니다.

그리드는 매우 간단하고 매우 빠릅니다.기본적으로 목록의 2D 배열입니다.각 배열 항목은 그리드 셀 내부에 있는 점을 나타냅니다.그리드 설정이 매우 쉽습니다.

for each point p
  get cell that contains p
  add point to that cell's list

물건을 찾는 것은 매우 쉽습니다.

given a query point p
  get cell that contains p
  check points in that cell (and its 8 neighbors), against query point p

알레호

역설적으로 말하자면, 거리가 가깝거나 (운전) 시간이 가깝다는 뜻인가요?도시 지역에서는 다른 방향으로 4마일(20분 정차 후 이동)보다 고속도로에서 5마일(5분)을 운전하는 것이 더 좋습니다.

따라서 필요한 '가장 가까운' 측정항목이라면 이동 시간 측정항목을 사용하여 GIS 데이터베이스를 살펴보겠습니다.

라이센스 : CC-BY-SA ~와 함께 속성
제휴하지 않습니다 StackOverflow
scroll top