README
[맵시] : 아름답고 보기 좋은 모양새 🌻
사용자의 경험을 극대화한 수백만 개 이상의 POI를 표시하는 클러스터링 앱
✨ 맵시 있는 사람들
| @SeungeonKim | @A-by-alimelon | @rnfxl92 | @DonggeonOh | @eunjeongS2 |
|---|---|---|---|---|
 |
 |
 |
 |
 |
| S010_김승언 |
S016_문성주🙇🏻♀️ | S017_박성민 |
S033_오동건 |
S040_이은정 |
개요
| Point Of Interest - 관심지점, 관심지역정보 | Clustering |
|---|---|
 |
 |
| 주요 시설물, 역, 공항, 터미널, 호텔 등을 좌표로 전자수치지도에 표시하는 데이터 | 개체들이 주어졌을 때, 개체들을 몇 개의 클러스터 (부분 그룹)으로 나누는 과정 |
지도 상의 대량의 POI들 중 사용자가 관심 있는 지역을 손 쉽게 접근 할 수 있도록 클러스터링 하여 나타내 더 좋은 경험을 제공
기술스택
📆 프로젝트 기간
2020년 11월 16일 ~ 2020년 12월 18일
⛳️ 프로젝트 목표
- 대량의 데이터를 빠른 속도로 클러스터링 할 수 있는 알고리즘 적용
- 실제 프로토타입을 작성하여 비교해가며 기능 적용
- 사용자의 편의를 고려한 UX, UI
- 간단한 사용자 이벤트만으로 다양한 기능을 구현
기능 소개
[Launch Screen]
| 화면 | 구현 내용 |
|---|---|
 |
• BezierPath를 통해 통통 튀어 오는 애니메이션 • UILabel의 Text를 딜레이를 줘서 한 글자씩 나오도록 구현 |
[Main Scene]
- 클러스터링
| 화면 | 구현 내용 |
|---|---|
 |
• Naver SDK에서 제공하는 TileCoverHelper의 onTileChanged 이벤트에 맞춰 새로 클러스터링 • CAAnimation으로 Fade in / out 자연스러운 화면 전환 • 클러스터 내의 데이터 수에 따라 원의 크기 및 색상 조정 • 클러스터 마커 터치 시 해당 클러스터의 데이터 범위로 카메라 이동 |
- 마커 추가
| 화면 | 구현 내용 |
|---|---|
 |
• 지도에 롱 터치 이벤트 발생 시 마커 추가 Alert 표시 • 추가하고자 하는 장소의 이름을 입력받아 마커 생성 • 리프노드 마커에는 통통튀는 애니메이션 적용 |
- 마커 삭제
| 화면 | 구현 내용 |
|---|---|
 |
• 기본 앱 삭제 경험과 유사한 경험 제공 • 마커를 롱 터치 시 Edit 모드로 전환 • 마이너스 버튼으로 보이는 모든 마커 삭제 가능 • CAKeyframeAnimation으로 shake 애니메이션 구현• 각 마커마다 시작 value를 랜덤으로 주어 다르게 애니메이션 가능 |
- 클러스터 Zoom In
| 화면 | 구현 내용 |
|---|---|
 |
• 클러스터 마커를 터치 시 데이터 바운더리에 맞춰 카메라 이동 • 데이터 양이 많은 경우, 데이터 바운더리를 검색하는 시간이 오래걸리므로 일괄적으로 줌 레벨 2단계씩 카메라 이동 • 각 트리에 대한 탐색이 병렬로 진행되며, 각각의 트리의 클러스터링도 독립적으로 표현 |
- POI 정보 창
| 화면 | 구현 내용 |
|---|---|
 |
• 원하는 마커 선택 시 선택을 알리기 위해 마커 크기 확대 • 마커 지역 정보 customWindow 로 표시 • 장소 이름, 카테고리 정보 출력 |
- POI 리스트 목록
| 화면 | 구현 내용 |
|---|---|
 |
• 사용자 선택에 따라 BottomSheetView의 히든 여부를 선택 • 해당 클러스터 내 필터 리스트 출력 •필터 클릭 시, 해당 카테고리 리스트를 최상위에 출력 •URLSession DownloadTask를 이용한 이미지 다운로드, 이미지 캐싱 |
- 클러스터링 영역 표시
| 화면 | 구현 내용 |
|---|---|
 |
• 클러스터링 마커 롱 터치 시 해당 클러스터링 영역 polygon 표시 •클러스터 마커 터치 시 카메라 zoom In 이벤트와 함께 클러스터링 영역 polygon 표시 |
기술 특장점
[CoreData]
- 병렬 처리를 통한 빠른 Fetch
- Migration을 이용한 버전 관리
[QuadTree]
- 많은 데이터를 빠르게 처리
GCD를 이용한 병렬 처리를 적극 활용- 클러스터링 횟수를 최소화
[User Interaction]
- Core Animation을 사용한 가벼운 애니메이션
- Layer로 한층 더 가볍게
- 다양한 제스쳐 이벤트에 대응하는 interaction
🏋️♂️ 저희는 다양한 도전을 했어요! 🏋️
앱 실행시 트리 생성 시간이 오래걸리는 문제를 해결하기 도전!
- 트리의 오브젝트 그래프를 CoreData에 저장하는 기능
앱 설치 후 처음 실행 시에만 트리를 생성하고,
이후에는 저장된 트리를 사용하면 트리 생성에 대한 시간을 줄일 수 있지 않을까 생각
1. NSManagedObject를 사용하기 위해서는 기존의 struct를 class로 변환해야하는 상황이 발생
→ 많은 양의 데이터를 Heap 메모리에 생성과 해제를 해야하기 때문에 리소스 낭비가 심했다.
2. fetch 및 save의 시간 소요가 트리를 생성하는 시간보다 빠르지 못했다.
[관련 PR] #67
- 트리를 JSON 파일로 변환해 디스크에 저장 / 트리를 아카이브해 UserDefault에 저장
CoreData에 저장하고 불러오는 것이 생각보다 느려서, 저장방식의 문제인지 확인해보려고 영구저장소에 저장하는 두 가지 방법을 더 시도했다.
→ 데이터를 읽고 decode, unarchive하는 과정이 트리를 생성하는 시간보다 느렸다.
- Coordinate Fetch시 전체 데이터를 한번에 불러온 뒤, 불러온 데이터를 Filter하여 사용
CoreData에서 Fetch를 여러번 하는 것이 성능에 안 좋은지 확인해보기 위해 한번에 불러오고 직접 필터하는 방법을 시도했다.
→ 전체 데이터를 한번에 Fetch하는 시간이 바운더리 영역에 대해 여러번 Fetch 했을 때 시간보다 느렸다.
[ 관련 PR ] [#71] [ 관련 PR ] [#59]
다양한 방법으로 클러스터링 알고리즘을 비교했어요! ( 📊 Kmeans/QuadTree )
KMeans
- KMeans 초기 중앙 점을 정하는 방법
1. 랜덤
2. 화면 기준 분할
3. ballCut
- KMeans 구현
1. 상태에 따라 클러스터링 종료
2. Coverage Distance 기준으로 클러스터링 종료
[ 관련 PR ] #31
- k값 검증 방법
1. 실루엣 검증
2. DBI 검증
QuadTree
- 구현 과정
🏆 Kmeans? QuadTree? 🏆
선정 : QuadTree
서버 없이 로컬 환경에서 최대한 많은 데이터를 빠르게 클러스터링하여 보여줄 수 있는 서비스를 목표하여 속도와 자원 활용 측면을 최우선으로 생각
- 같은 8000개의 데이터로 동일한 조건에서 돌려봤을 때, QuadTree가 트리만드는 속도를 감안하고도 눈으로 봐도 더욱 빨랐다.
- K-means는 알고리즘 자체로는 빠르지만, K값 검증 로직을 넣으면 급격히 속도가 떨어지는 것을 확인했다.
- K-means의 장점은 QuadTree에 비해 분포를 잘 나타낸다는 것인데, K 검증을 하지 못하면 무의미하게 되므로 QuadTree 알고리즘을 채택했다.
- QuadTree는 초기 트리 생성이 끝난 후 탐색할 때는 메모리나, CPU 사용량에서 매우 좋은 성능을 보였다.