[BE] 지도 클러스터링 기능 추가

[kpeel5839]

📄 작업 대상

지도 위 핀들을 군집화하여 반환할 수 있도록 합니다.

✅ 작업 내용

킹녕하세요!

세인과 함께 클러스터링을 구현하다보니 복잡도가 생각보다 높아진 것 같아, 이해를 조금이라도 더 돕기 위해 선택에 대한 근거와 어떻게 했는지에 대해 자세히 적느라 이슈가 좀 길어진 것 같습니다.

미리 죄송합니당~

---

클러스터링이 무엇인가?

출처 : 네이버지도

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

괜찮을지도에서 클러스터링은 왜 할까?

저희는 성능개선을 위해, DB 와의 통신 시간을 줄이고, 더 나아가서 코드의 시간 복잡도도 관리합니다.

하지만, 너무 바쁜 나머지 신경쓰지 못한 부분이 있는데요.

바로, 화면 렌더링 문제입니다.

붕어빵 지도를 아래와 같습니다.

화면에 핀이 무수하게 찍혀있는 것을 확인할 수 있고, 수 많은 핀들은 지도가 조금씩 움직일 때마다 리렌더링 됩니다.

즉, 붕어빵 지도에 찍힌 핀이 800 개 화면이 조금 움직이더라도 리렌더링 되고 있는 것입니다.

그렇다면, 당연히 성능이 떨어질 수 밖에 없겠죠.

이 외에도 지도를 봤을 때, 난잡한 느낌이 있습니다. (쥬니가 이미 한번 지적해줬던 부분이죠 알러뷰 쥬니짱)

이를 깔끔하게 잡아주기 위해서, 꼭 진행해야 하는 작업이라 생각하고, 무엇보다 굉장히 재미있을 것 같았습니다. (두근두근)

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

클러스터링이 적용되는 순간은 핀의 이미지들이 서로 겹칠 때 적용할 예정입니다.

이를 적용하기 위해 해결해야 했던 문제들에 대해서 먼저 나열한 뒤, 설명드리겠습니다.

해결해야 했던 문제들

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 개이니, 그리 오랜 시간이 걸리지 않을 것이라 예상합니다.

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

하나의 집합의 대표 좌표

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

원의 크기는 모두 동일하다고 봐주세용... 그림 못그려서 죄송합니다

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

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

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

현재는 후자를 선택하여 구현한 상태입니다.

하지만 현재의 선택에 있어, 추후 우려가 되는 부분이 있긴합니다.

평균값으로 진행하게 되는 경우 새로운 좌표값이 생기게 되고, 실제로는 현재 집합의 핀들과 전혀 겹치지 않는 핀과, 겹쳐보이게 렌더링 될 수도 있을 것 같다는 부분입니다.

킹치만, 하나의 전자보다 조금 더 자연스러울 것 같다고 생각하여 이와 같은 선택을 하게 되었습니다.

여러분은 어떤 것 같나요?

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

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

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

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

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

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

그렇기 때문에 저는 따로 보정을 하지 않는 것으로 결정했습니다!

---

이슈인데, 너무 길게 작성했네요 봐주셔서 감사합니다.

📎 참고 자료

No response

⏰ 추정 시간

낙관적 추정 시간 - 2일
비관적 추정 시간 - 7일