지도 서비스와 마커는 뗄 수 없는 관계다. 어떤 특정 지점을 표시하거나 지도와 데이터를 연결하는 방식이다. 이때 지도 view에 마커가 많이 렌더링 되는 경우도 빈번하게 등장한다.
이는 어떤 데이터를 가진 마커인지 알 수 없게하는 사용자 경험을 떨어트린다. 따라서 이를 해결하기 위해 대부분의 지도 서비스들은 마커 클러스터 기법을 사용한다.
마커 클러스터란 같은 영역에 마커를 모아서 하나의 마커로 대체하는 방식을 말한다. 대부분 대체한 마커에 해당영역에 존재하는 마커의 숫자를 표기한다.
구글지도를 사용하는 나는 마커 클러스터를 어떻게 적용할 수 있을까?
google Maps API 공식 홈페이지에서는 marker Cluster 구현을 위해 위와 같은 라이브러리 사용을 권장한다.
markerclusterer 라이브러리는 어떤 방식으로 클러스터를 적용하는지 살펴봤다.
우선 Cluster를 어떻게 판별할까? 이는 k-d tree라는 자료구조로 Euclidean clustering을 진행한다.
간략하게 k-d tree는 이진 탐색 트리를 k차원으로 확장한 데이터 구조다.
그러니까 이진 트리의 각 계층을 차원에 매핑시켜 비교한다. 보통 각 차원의 중앙값을 사용한다.
위의 그림을 보면서 2D k-d tree를 만들어보자.