위도 및 경도 값에 대한 근접 검색을 구현하는 방법은 무엇입니까?

Question

내 응용 프로그램 (Qt 기반 모바일 응용 프로그램)은 위도, 경도, 설명 형식으로 서버에서 데이터를 가져옵니다.

빠른 검색을 위해 나중에이 데이터를 데이터 구조에 저장해야합니다. 이제지도가 생겼고 사용자가지도상의 지점을 클릭하면 해당 지점의 위도, 경도를 얻습니다. 이 2 개의 가치를 사용하여 나는 빨리 나의 자료 구조를 검사하고 관련 묘사를 만회한다. 내 문제는 .. 위도와 경도는지도에서 클릭하면 근사치 (터치 장치이므로 정확한 위도 + 길이를 얻지 못함)입니다. 따라서 데이터 구조에 대한 선형 검색을 수행하면 결코 찾을 수 없습니다. 이 값들. 게다가 너무 많은 데이터가있는 경우 선형 검색은 매우 느립니다. 데이터 구조는 내가 위도 + 길이 + 설명을 저장하는 데 사용할해야합니까

2. (해시 내 mind..but에 관해서 내가 키를 형성하기 위해 긴 + 위도 결합하는 방법을 단서가 없다) 데이터 구조에 대한 근사 검색은 어떻게합니까?

감사합니다!

Answer 1

찾고있는 데이터 구조는 kd-tree입니다. 해시가 실제로 필요한 경우 약간의 오류가 허용되는 경우 거리 기반 해싱에 대한 접근 방법을 설명하는 this paper(pdf)을 살펴볼 수 있습니다.

당신이 더 잘 작동하도록 시도해야합니다. 그 논문에서 알고리즘을 구현했는데 내 문제 때문에 제대로 작동하지 않았습니다. 아마도 데이터 포인트가 너무 고르게 분산되지 않았기 때문일 것입니다. 이는 귀하의 경우 다를 수 있으므로 시도해야합니다.

Answer 2

문제가 2 차원으로 만 구성되어 있으므로 이진 트리를 사용할 수 있습니다. 각 잎은 최대 "N"점을 가질 수 있습니다 (위도, 경도를 점으로 생각하십시오). 잎 노드에만 포인트가 있습니다. 점의

데이터 유형

class Point 
{ 
    float Latitude; 
    float Longitude; 
    string Description; 
} 

내부 노드 (잎이 아닌 노드)

class LeafNode 
{ 
    Point points[K]; // Array of points 
} 

동적 바이너리 트리를 생성하고, 분할 leafnode에의

class Node 
{ 
    Float MaxLatitude; 
    Float MinLatitude; 
    Float MaxLongitude; 
    Float MinLongitude; 
} 

데이터 유형의 데이터 유형 노드의 높이가 더 높으면 위도 e를 기준으로 나눕니다. lse는 경도에 따라 나눕니다.

입력 지점을 검색 할 때 관련 리프 노드를 찾으면 해당 리프 노드의 모든 점이 입력 지점에 가장 가까운 지점이됩니다.

이것은 인기있는 문제입니다. - http://en.wikipedia.org/wiki/Nearest_neighbor_search#Approximate_nearest_neighbor