가장 가까운 점을 계산하는 효율적인 방법은 무엇입니까?

Question

핵심 데이터에 위치 데이터가 저장된 객체가 있는데, 가장 가까운 지점을 가져 와서 현재 위치에 표시하고 싶습니다. 현재 위도/경도에서 저장된 위도/경도까지의 거리를 계산하는 수식이 있음을 알고 있습니다. 그러나 핵심 데이터에 저장된 1000 개 이상의 점 집합에 대해이를 수행하는 가장 좋은 방법이 궁금합니다. 코어 데이터에서 배열로 포인트를 반환 한 다음 점 사이의 거리에 대한 최소값을 찾는 루프를 반복 할 수는 있지만 더 효과적인 방법이 있다고 생각합니다. 코어 데이터를 어떤 방식 으로든 활용할 수 있습니다.

어떤 통찰력도 인정 될 것입니다.

EDIT : 초기 검색에서 이것을 놓쳤는 지 모르겠지만 this SO question은 핵심 데이터 개체 배열을 반복하면서 현재 위치를 기반으로 테두리 상자로 배열 크기를 제한하는 것을 제안합니다. 이게 내가 할 수있는 최선인가?

Answer 1

를 가진 동일한 버킷에 매핑되는, 그것은 본다 현재 위치 주변의 경계 상자를 사용하여 점의 수를 계산합니다.

반환 된 배열이 비어있는 경우 현재 위치의 특정 범위 내의 점을 검색 한 다음 상자의 크기를 늘릴 수 있습니다. 일부 결과가 다시 나오면 배열에서 가장 가까운 것을 계산하고 그 점을 사용하십시오.

Answer 2

내가 코어 데이터에 대한 것을 잘 모르겠지만, Quadtree 같은 알려진 알고리즘이 문제를 해결하기 위해 잘있다

Answer 3

당신이 Nearest neighbor search라고 만들고있어와 방법을 계산하는 데 사용할 설명하는 위키 백과 항목이 그것. 난 당신이

이

NNS 문제에 대한 가장 간단한 해결책은 쿼리에서의 거리 를 계산하는 방법을 구현 : 얼마나에 대한 복잡성을 측정 할 수 있도록 각 방법에 대한 복잡한 상태이기 때문에 좋은 시작이라고 생각 데이터베이스에있는 모든 지점을 가리키며 의 "최고 지금까지"추적하십시오. 이 알고리즘은 때때로 순 접근라고도 O의 주행 시간 ND()이

소재지 성 해싱 (LSH)는 몇몇 거리에 따라 "버킷"에 공백 의 포인트들을 그룹화하는 기법 포인트에 대해 미터법이 작동합니다. 이 경우 가장 좋은 방법은 배열을 반환하는 것처럼 메트릭 선택한 에서 서로 가까운 점 가 높은 확률 내가 무엇을 수집 할 수 있습니다에서