나는 위도, 경도 및 시간 스탬프로 구성된 n 개의 위치 목록을 가지고 있습니다. 이 위치는지도에 고정됩니다.알고리즘 -지도상의 위치 그룹화
그러나 인접한 위치를 가장 최근에 변경된 위치를 중심으로 그룹화하여지도에 핀이 넘치지 않도록해야합니다.
내 초기 생각은 다음과 같습니다 타임 스탬프에 의해
이 방법은 효과가 있지만 매우 비효율적입니다. 최악의 경우는 ~ O (n^2)입니다.
더 나은 알고리즘이 있습니까?
2 차 런타임을이기려면 인덱스를 사용하십시오.
위도와 경도에서는 k 트리가 haversine이 아닌 유클리드 거리에서만 작동하므로 위도와 경도에서 R 트리, 공 나무, 덮개 나무 또는 이와 유사한 것을 사용할 수 있습니다.
R - 트리가 올바른 키워드입니다. 여기 https://github.com/davidmoten/rtree 구현을 사용하여 성능이 뛰어납니다. 감사합니다 –
하지만 마지막으로 확인, 그것은 Haversine 거리를 아주 잘 할 수 없습니다. ELKI 버전은 가능합니다. Schubert E., Zimek A., Kriegel HP가이 접근 방식을 사용한다고 생각합니다. 지리 데이터 인덱싱을위한 R-Trees에 대한 측지 거리 쿼리. SSTD 2013. –
대략적인 답변으로 정상적으로 작동하는 경우 작동하지 않을 수있는 해킹 해결책이 있습니다.
일반적으로 위도 경도는 (12.9877949,77.6095064)와 같이 여러 소수점을 초과하여 여러 개갑니다. 이제 소수점 다음에 소수 자릿수 만 선택할 수 있으며 일반적으로 수 킬로미터 내에 있습니다.
12.9877979,77.6095054가 12.9877949,77.6095064에 가까우므로 소수점 2 자리까지 가져 가면 둘 다 12.98,77.60이됩니다. 이제 목록을 살펴보고 동일한 값을 가진 것들을 선택합니다.
당신은 매우 정확한 계산을
해야하는 경우가 있지만 작동하지 않습니다
https://blog.mapbox.com/clustering-millions-of-points-on-a-map-with-supercluster-272046ec5c97 –