마커 클러스터링을 알고리즘을 활용해서 구현해보자

클러스터링을 구현하게 된 계기

저는 우아한테크코스에서 괜찮을지도라는 프로젝트를 진행했었습니다.

시간이 많이 늦긴했지만, 그 때 인상 깊은 족적을 남겼던 것을 지금에서라도 기록을 남겨보려 합니다.

괜찮을지도라는 프로젝트는 각자 토픽을 정하고 해당 토픽에 본인이 좋아하는 위치를 기록하며, 서로 공유하고, 각각의 토픽에 맞춰 기록한 위치들을 뽑아서 새로운 지도를 구성할 수도 있게하여 사용자들에게 편의를 제공하는 서비스였습니다.

그렇다보니, 지도와 위치를 나타내는 이미지는 필수였습니다.

그렇게 해당 서비스 오픈을 앞둔 찰나에, 사용자들의 이목을 집중시킬 무언가가 필요했습니다. 저희는 그것을 대동붕어빵여지도로 정했습니다.

대동붕어빵여지도는 트위터에서 여러명의 사람들이 전국에 있는 붕어빵 집을 기록해 만든 지도입니다. 저희는 저작자에게 허락을 맡은 뒤에 저희 서비스로 해당 지도 데이터를 완전히 이관했습니다.

하지만, 여기서 문제가 발생했습니다. 지금까지는 하나의 토픽에 해당하는 위치 정보들이 그리 많지 않았는데, 대동 붕어빵 여지도는 위치 정보가 1000개 이상이 되었습니다.

이러한 상황으로 인해, 조금만 움직여도 버벅임에 사용성이 굉장히 떨어졌습니다. 또한 이미지를 보시면 아시겠지만, 수 많은 위치정보로 인해 가시성도 굉장히 떨어지는 것을 볼 수 있었고, 이는 분명한 개선포인트로 여겨졌습니다.

물론 사용하고 있던 지도 API에서 클러스터링 기능을 활용하면 되지 않느냐라고 할 수 있겠지만, 해당 API에서는 클러스터링 기능을 제공하지 않았습니다. 그렇기에, 직접 구현해야겠다고 마음먹었죠.

클러스터링이 무엇인가?

출처 : 네이버지도

클러스터링은 위 사진과 같이, 밀집된 위치 정보가 있다면 하나로 합쳐서 보여주는 것입니다. (가게 상호명 옆에 숫자가 보일 것입니다.)

자 그러면 이제부터 클러스터링을 어떻게 할 것인지 디테일을 잡아보겠습니다.

클러스터링이 진행되는 기준

클러스터링이 적용되는 순간은 핀의 이미지들이 서로 겹칠 때, 적용하였습니다. 단순하게 이게 가장 일반적인 방법이고,사용자가 예측하기에 좋은 방법이라고 생각했기 때문입니다.

이를 적용하기 위해 해결해야 했던 문제들에 대해 먼저 나열해볼까요?

해결해야 했던 문제들

1. 핀의 이미지 크기를, 실제 지구상의 거리 로 치환한 값이 필요했습니다.
2. 핀들의 이미지가 겹쳐있는지 판단할 수 있어야 했습니다.
3. 핀들의 이미지가 겹쳐있는 경우, 하나의 집합 으로 만들어줘야 했습니다.
4. 집합의 대표 좌표를 정해야했습니다.
5. 실제 핀의 좌표는 이미지의 중심이 아닌 하단에 위치한다는 문제가 있었습니다.

위와 같이 해결해야 하는 문제들이 총 5가지가 있었습니다.

핀의 이미지의 크기를, 실제 지구상의 크기로 치환

지도가 축소, 혹은 확대되더라도 화면상에 표시되는 이미지의 크기는 60 px * 60 px 로 동일했습니다.

이 말은, 현 줌 레벨에서의 1px 의 실제 거리 를 알면 이미지의 실제 크기를 알 수 있다는 것입니다.

물론 이미지의 크기가 굉장히 크다면 현재 방식의 계산은 오차가 생길 우려가 있긴 하지만, 크지 않을 것이라 판단하고 진행했습니다. (지구는 곡선이니까요.)

현재 줌 레벨에서의 1px 의 실제 거리를 알아낸 방법은 아래와 같습니다.

1. 현재 Screen 의 Width(픽셀 단위) 를 알아낸다.
2. (Height, Width 라고 할 때), Screen 에서의 (0, 0), (0, Width) 들의 좌표를 알아냅니다.
3. 알아낸 두 좌표간의 거리를 Tmap API 를 통해서 구합니다.
4. 두 좌표간의 거리 / Width 를 구합니다.

위 과정을 거치면서 현재 줌 레벨에서의 1px 의 실제 거리를 알아낼 수 있었습니다. (이 부분은 동적으로 변경이 되는 부분이기 때문에 API 요청으로 넘겨줍니다.)

핀들의 이미지가 겹쳤는지 확인

위 문제를 해결하면서 문제가 굉장히 간단해졌습니다.

우리는 핀 이미지의 지름을 알고 있기 때문에

두 좌표간의 거리만 안다면, 현재 두 핀의 이미지가 겹쳐있는지 알 수 있습니다.

계산은 편의상 정사각형이 아닌 원이라고 생각하고 구하였습니다. (오히려 핀 이미지의 외곽선을 따라 그려보면 사각형으로 생각하여 계산하는 것보다 원으로 생각하여 계산하는 것이 여백이 적습니다.)

그림을 보면 알 수 있듯

두 원이 닿아있는지 빠르게 확인하기 위해서는 두 좌표간의 거리 가 원의 반지름 * 2 보다 이하이면 되죠

즉, 두 좌표간의 실제 거리 <= 원이 지름 이 수식으로 두개의 핀 이미지가 겹치는지 알 수 있습니다.

핀들의 이미지가 겹쳐있는 경우, 하나의 집합으로

핀들의 이미지가 겹처있는지를 위와 같이 알 수 있었습니다.

이제 하나의 집합으로 만들면되고, 이를 구현하기 위해 union-find 알고리즘을 사용할 것입니다. 분리집합 알고리즘 설명)

대신, 완벽하게 집합을 구성하기 위해서 각각의 Pin 하나가 다른 모든 Pin 들과 겹치는지 확인해야하고, 결론적으로 2중 반복문을 돌게 됩니다.

즉, Pin 의 개수가 N 이라고 했을 때 O(N * N) 의 시간 복잡도를 가지게 됩니다.

그래도 대충 해당 서비스의 최대 핀 개수는 1000 개이니, 그리 오랜 시간이 걸리지 않을 것을 예상하고 진행했습니다.

또, 렌더링 문제를 크게 개선하기 때문에, 오히려 성능상으로 크게 이득을 볼 수 있지 않을까 예상하고 있습니다.

실제 핀의 좌표는 원의 중심이 아닌 하단에 위치

소제목이 뜻하는 바는 아래와 같습니다.

그래서 총 이미지의 크기가 60px 이기에, 집합을 계산할 때, 모든 좌표들의 위도를 30px 만큼 올린다음 계산을 진행하려 했는데, 그렇게 하지 않아도 될 것 같다는 생각이 들었습니다.

실제로 모든 핀의 위치를 30px 을 올리게 된다면, 결국 올리지 않은 것과 동일하기 때문입니다.

이를 증명하기 위해서는, 모든 핀들간의 거리를 30px 올리기 전, 30px 올리고 난 후의 좌표간의 거리을 계산해보면 됩니다.

해본다면 똑같다라는 것을 알 수 있습니다.

그렇기 때문에, 따로 보정은 넣지 않는 것으로 결정했습니다.

하나의 집합의 대표 좌표

핀들의 집합을 만들었습니다.

원의 크기는 모두 동일하다고 봐주세요. 그림을 직접 그려서 일정하지 않습니다.

다음 그림과 같이 집합이 구성되어 있을 때, 실제로 지도에는 핀이 어디 위치에 찍혀있어야 할까요?

아래와 같이 두 가지 선택사항이 있었습니다.

1. 집합에 속한 핀들 중 하나의 좌표를 활용 (대표값)
2. 집합에 속한 모든 핀들의 평균 좌표를 구함 (평균값)

여기서 2번을 선택하게 되면, 핀의 위치가 군집을 이룰 때마다 통통 튈 것입니다. 조금 더 안정적인 클러스터링 기능을 제공하기 위해, 대표 핀을 가장 왼쪽의 핀으로 고정하여 표현합니다.

클러스터링 범위 최적화

처음에 구현했던 방법은 위에서 설명하였듯, 이미지가 겹치기만 하면 모든지 하나의 집합으로 묶어주었습니다.

이 동영상에서 더 극적으로 보이는 이유는, 이 때는 집합에 속한 모든 핀들의 평균 좌표를 사용자에게 보여주고 있었기 때문입니다.

그러니 위와 같이 동작했습니다.

너무 범위가 넓지 않나요? 이는, 집합 안에 숨겨져 있는 핀들로 인해, 저 많은 핀들이 하나의 집합을 이룬 것입니다. (위에서 보여드린 사진처럼 연속적으로 말이죠)

조금도 정밀도를 올려볼 필요가 있다고 생각했습니다.

이를 행하기 위해, 집합 안에 숨겨져 있는 핀들은 클러스터링에 사용하지 않는 것으로 결정했습니다. 즉, 대표 핀(가장 왼쪽)의 이미지가 다른 핀과 겹친다면 그제서야 클러스터링을 진행해주는 것이죠.

이렇게 구현하니 결과물은 다음과 같았습니다.

훨씬 정밀한 것을 볼 수 있습니다.

이로써, 클러스터링 구현을 마칠 수 있었습니다.

그 때 제가 구현했던 코드는 여기에 있습니다.