경계 상자보다 더 좋은 것이 있습니까?
-
13-09-2019 - |
문제
x 백만의 경도 위도 포인트가있는 시나리오가 있습니다.
새로운 Long/Lat Point가 추가되면 알고 싶습니다. 효율적으로 다른 포인트가 사용자 구성 거리 매개 변수 내에 있으므로 목록에 추가 할 수 있습니다.
경계 상자보다 더 좋은 것이 있습니까?
알고리즘, 참조 및 몇 가지 구현을보고 싶습니다.) 친절하게 감사합니다!
다른 팁
한 동료는 그가 사용하는 경험이 좋은 경험이 있다고 말했습니다. 모튼 코드 GIS 데이터에 대한 공간 색인으로서, 아마도 조사 할 가치가있을 것입니다.
이 빠른 접근 방식은 당신에게 슬픔을 구할 수 있습니다. 지구의 표면을 1도 상자로 나눕니다. 그런 다음 180x360 요소 배열이 있으면 새로운 포인트가 포함 된 상자와 모서리 중 하나가 사용자 지정 거리 내에있는 모든 상자를 포함하여 적은 수의 상자 만 검색하면됩니다. 당신은 그들 모두를 고려하지 않고 어떤 상자를 사용할 것인지 빠르게 알아내는 데 사용할 수있는 몇 가지 트릭이 있음을 알게 될 것입니다. 위도와 경도 랩 어라운드를 잊지 마십시오.
"만"에 수백만 포인트가 있고 핫스팟으로 클러스터되지 않으면이를 통해 당신을 통과시킬 수 있습니다.
이론적으로 우수한 방법 : 각 지점을 3 차원 공간에 매핑 한 다음 보관할 수 있습니다. Octree, 이로 인해 근처의 지점은 임의의 거리 내에서 빠르게 찾을 수 있습니다. 물론, 3 차원 공간에서의 거리는 지구의 큰 원 거리는 약간 다르므로 변환 계수를 계산해야합니다. 그래도 간단해야합니다. 구현 언어를 언급하지는 않지만 작업중인 모든 언어에 대해 잘 테스트 된 Octree 구현이있을 것입니다. 타사 코드를 삽입하는 것이 마음에 들지 않으면이 솔루션은 다음과 같습니다. 가다.