그래서 문제를 해결하려고합니다. 나는 선수가 될 수있는 지점을 가지고 있으며, 나는 몇 개의 물체를 가지고 있으며, 어떤 것은 더 가까운 곳에있다. 멀리있는 모든 점을 제외하고 거리를 사용하는 거리를 더 가깝게 포함시키고 싶습니다. 어떻게 하나의 클러스터 또는 개체를 필터링합니다. 공간 분할에 대해 생각하고 있습니다. 객체는 지리적 좌표에 있습니다. 객체 수는 10.000이 될 수 있습니다.WGS84의 클러스터링 또는 필터링 포인트 좌표
모든 단일 지점을 이동할 수 있으면 kd- 트리 또는 유사한 적응 구조에 대한 업데이트가 비쌀 수 있습니다. 나는 정적 파티셔닝 접근법을 찾아야한다고 생각합니다. 공간을 일련의 셀 (2 차 또는 직사각형)로 나누고 각 셀 저장소에 대해 포함 된 점 집합의 최대 및 최소 좌표와 함께 포함 된 점에 대한 참조를 지정합니다. 포인트가 움직이는 경우 현재 셀을 쉽게 계산할 수 있습니다. 거리 계산에 관해서는 관련 셀을 결정한 다음 선형 시간으로 포함 된 포인트까지의 거리를 계산하면됩니다. 그렇지 않다면 당신은 쉽게 여부의 빈 확인할 수 있습니다 전체 세트를 현재 포함 된 분 살펴보면
및 최대 각 셀 좌표 :
나는이 방법으로 세 가지 기본 이점 참조 포함 된 포인트는 플레이어의 현재 위치와 관련이 있습니다.
정적 셀을 트리 구조 (예 : 쿼드 트리)로 완벽하게 균형있게 구성 할 수 있습니다. 트리의 각 내부 노드에 대해 하위 노드의 결합 된 최소 및 최대 좌표를 저장하고 업데이트합니다. 트리의 구조가 전혀 영향을 미치지 않기 때문에 업데이트가 매우 저렴합니다.
포인트를 정렬 할 필요가 없습니다 (다른 구조 또는 특정 구현에 필요함). 객체가 빠르게 움직이는 경우 많은 성능을 절약 할 수 있습니다.
데이터 구조를 만들고 유지 관리하는 것은 간단합니다. 이국적인 테스트 케이스와 복잡한 구조 업데이트로 인해 뇌를 망칠 필요가 없습니다.
있다, 물론,이 때문에, 잘, 비 적응을 비 적응 적 데이터 구조를 선택하는 몇 가지 단점. 예를 들어, 그리드 셀의 크기에 크게 의존합니다. 너가 너무 작 으면 (최악의 경우 : 세포 당 1 점), 수목의 깊이가 올라가고 횡단이 비싸게된다. 다른 한편으로는 너무 커서 (최악의 경우 : 모든 포인트가 같은 셀에있는 경우), 불필요하고 잠재적으로 값 비싼 거리 계산을 많이 수행하게됩니다.
전체적으로 데이터의 종류에 따라 다릅니다. 제가 여러분에게 준 제안서는 합리적으로 좋은 결과를 주어야하지만, 아마도 그것을 할 수있는보다 효율적인 방법이있을 것입니다. 시간이 충분하다면 적응과 정적 파티셔닝 접근법을 구현하고 몇 가지 대표적인 테스트를 만들고 서로 비교하십시오.
희망 하시겠습니까?)
공간 분할은 여기에 적합한 키워드이지만 좀 더 자세한 정보를 제공해야합니다. 예를 들어, "플레이어"가 움직이고 있다고 가정하지만 다른 점도 있습니까? 선택한 3D 정보가 정말로 필요합니까? 또한 WGS84는 프로젝션 기반의 길이가 유지되지 않는 좌표계이며 플레이어에 대한 미터 거리를 계산해야하는지 여부에 따라 파티션을 선택하는 데 영향을 줄 수 있습니다. –
개체가 너무 움직이고 있습니다. 아니오, 선택을 위해 3D 정보가 필요 없습니다. 구면 좌표를 미터 거리에 대해 데카르트로 변환합니다. –
@FelixLauer 아이디어가 있습니까? 어떻게 진행할 것인가?kd-tree knn? –