경계 상자보다 더 좋은 것이 있습니까?

Question

x 백만의 경도 위도 포인트가있는 시나리오가 있습니다.

새로운 Long/Lat Point가 추가되면 알고 싶습니다. 효율적으로 다른 포인트가 사용자 구성 거리 매개 변수 내에 있으므로 목록에 추가 할 수 있습니다.

경계 상자보다 더 좋은 것이 있습니까?

알고리즘, 참조 및 몇 가지 구현을보고 싶습니다.) 친절하게 감사합니다!

Answer 1

주로 주변을 기반으로 더 나은 옵션이 꽤 있습니다. 우주 분할.

일반적이고 종종 아주 좋은 옵션 (구현하기가 어렵지 않음)은 KD-Tree. 쿼드 트리 구현하기 쉽지만 검색 속도가 느립니다. 데이터 분포에 따라 요구 사항에 따라 요구 사항에 따라 다른 공간 파티셔닝 알고리즘이 더 잘 수행되거나 메모리 요구 사항이 낮거나 관련된 기타 문제가있을 수 있습니다.

Answer 2

한 동료는 그가 사용하는 경험이 좋은 경험이 있다고 말했습니다. 모튼 코드 GIS 데이터에 대한 공간 색인으로서, 아마도 조사 할 가치가있을 것입니다.

Answer 3

이 빠른 접근 방식은 당신에게 슬픔을 구할 수 있습니다. 지구의 표면을 1도 상자로 나눕니다. 그런 다음 180x360 요소 배열이 있으면 새로운 포인트가 포함 된 상자와 모서리 중 하나가 사용자 지정 거리 내에있는 모든 상자를 포함하여 적은 수의 상자 만 검색하면됩니다. 당신은 그들 모두를 고려하지 않고 어떤 상자를 사용할 것인지 빠르게 알아내는 데 사용할 수있는 몇 가지 트릭이 있음을 알게 될 것입니다. 위도와 경도 랩 어라운드를 잊지 마십시오.

"만"에 수백만 포인트가 있고 핫스팟으로 클러스터되지 않으면이를 통해 당신을 통과시킬 수 있습니다.

이론적으로 우수한 방법 : 각 지점을 3 차원 공간에 매핑 한 다음 보관할 수 있습니다. Octree, 이로 인해 근처의 지점은 임의의 거리 내에서 빠르게 찾을 수 있습니다. 물론, 3 차원 공간에서의 거리는 지구의 큰 원 거리는 약간 다르므로 변환 계수를 계산해야합니다. 그래도 간단해야합니다. 구현 언어를 언급하지는 않지만 작업중인 모든 언어에 대해 잘 테스트 된 Octree 구현이있을 것입니다. 타사 코드를 삽입하는 것이 마음에 들지 않으면이 솔루션은 다음과 같습니다. 가다.