배경
댕댕워크는 강아지 산책 어플로 산책 경로를 산책 일지에서 확인할 수 있는 기능을 제공하고 있습니다.
이 때 산책 경로를 위도, 경도로 표현된 GPS 포인트의 배열로 저장하게 되는데,
3시간 산책시 최대 크기가 420KB까지 커질 수 있어 줄일 방법을 고민하게 되었습니다.
기존 방식
각 Point는 댕댕워크에서 사용한 카카오 지도 API의 정의에 따라 {lat: number, lng: number} 타입으로 정의했습니다.
이 객체의 배열을 백엔드에서 JSON.stringify로 문자열로 변환해 저장하게 됩니다.
GPS 표준인 WGS84에서 위도는 -90~90, 경도는 -180~180의 범위를 가집니다.
정밀도는 기기에 따라 다르지만 저장된 데이터를 확인해 봤을 때 대체로 소수점 7자리까지 저장되는 경우가 많았습니다.
1초에 한번씩 Point를 저장하고, 최대 산책 시간은 3시간입니다. 3시간을 쉬지 않고 산책시 10,800개의 포인트가 찍힐 수 있습니다.
이를 바탕으로 계산해보면,
{} 괄호: 2바이트
"lat:","lng:": 13바이트
위도 / 경도 각각 최대 10자리, 11자리: 21바이트
소수점 2개: 2바이트
= 하나의 포인트 당 38바이트
38 * 10800 = 410,400 바이트
여기에 전체 배열의 앞뒤 괄호 ([] - 2바이트)와, 포인트 사이 쉼표(9999개)를 더하면,
총 420,401 바이트, 약 420KB까지 데이터가 커질 수 있습니다.
1. 포인트 저장 단위를 1m -> 10m로, 1초 -> 2초로 변경
프론트엔드 개발자 @이준형 님이 다른 어플들을 찾아보니, 대체로 10m 단위로 포인트를 저장하고 있다는 것을 알게 되었습니다.
10m 단위로 저장하도록 변경하고, 포인트 저장 단위도 2초에 한번씩 저장하도록 변경하였습니다.
최대 Point 갯수가 절반인 5400까지 줄어들었습니다. 최대 포인트는 3시간동안 쉬지않고 2초에 10m 이상 이동했을때의 수치이므로 실제로는 더 작을 것으로 생각됩니다.
2. 포인트 타입을 객체 -> 숫자 배열로 변경
바이트를 줄이기 위해 기존 {lat: number, lng: number}[] 타입에서 lat, lng를 뺀 [number, number][] 타입으로 변경하였습니다.
1, 2번을 적용해 데이터 크기를 다시 계산해보면,
대괄호 2개 : 2바이트,
쉼표: 1바이트,
위도/경도 각각 최대 10, 11자리 : 21바이트
소수점: 2바이트
총 26바이트 * 최대 5400 포인트 = 140400
여기에 전체 배열의 바깥 대괄호 ([] - 2바이트)와 포인트 사이 쉼표 (5399)를 더하면 총 145,801로 약 145KB 까지 줄어들었습니다.
3. line-simplification 알고리즘 적용
기존 산책 경로를 보면, 10m 단위로 계속 점이 찍히기에 자잘하게 점이 찍혀있는 경로가 생성됨을 알 수 있습니다.
비슷한 위치의 점들의 경우 시작과 끝만 저장하면 될 것 같다는 생각이 들어 찾아보니 line-simplification 이라는 카테고리의 알고리즘이 있었습니다.
https://martinfleischmann.net/line-simplification-algorithms/
- Visvalingam-Whyatt 알고리즘은 좀 더 정확한 결과물을 내지만 상대적으로 성능이 좋지 않습니다. 자연 지형의 line-simplication에 주로 사용합니다.
- Ramer-Douglis-Peuker 알고리즘은 뾰족한 선들을 만드는 경향이 있지만 상대적으로 성능이 좋습니다.
이 중 Ramer-Douglas-Peuker 알고리즘이 GPS 경로 데이터 단순화에는 충분한 결과를 내면서도 성능이 좋아 선택했습니다.
위 그림처럼, 어떤 범위 내에 있는 점들은 하나의 선분으로 단순화 해줍니다.
코드에 적용하기
export const rdpAlgorithm = (points: Coords[], startIndex: number, lastIndex: number, epsilon: number): boolean[] => {
const stack: [number, number][] = [[startIndex, lastIndex]];
const bitArray = new Array(lastIndex - startIndex + 1).fill(true);
while (stack.length > 0) {
const [start, end] = stack.pop()!;
let dmax = 0;
let index = start;
const startPoint: Position = { lat: points[start]![0], lng: points[start]![1] };
const endPoint: Position = { lat: points[end]![0], lng: points[end]![1] };
for (let i = start + 1; i < end; i++) {
const currentPoint: Position = { lat: points[i]![0], lng: points[i]![1] };
if (bitArray[i - startIndex]) {
const d = pointLineDistance(currentPoint, startPoint, endPoint);
if (d > dmax) {
index = i;
dmax = d;
}
}
}
if (dmax > epsilon) {
stack.push([start, index]);
stack.push([index, end]);
} else {
for (let i = start + 1; i < end; i++) {
bitArray[i - startIndex] = false;
}
}
}
return bitArray;
};재귀 버전-> 반복문 버전으로 변경해 RAM 사용량을 줄인 코드를 찾아 사용했습니다.
(https://namekdev.net/2014/06/iterative-version-of-ramer-douglas-peucker-line-simplification-algorithm/)
산책 중지 버튼을 눌렀을 때 이 알고리즘을 기존 경로에 적용하고 단순화된 경로를 덮어씌우는 방식으로 적용했습니다.
프론트 개발자분들이 취업 이슈로 할 수 있는 분이 없어 직접 적용했습니다ㅎㅎ
엡실론 테스트
| 원본 | 0.0001 | 0.00005 |
|---|---|---|
 |  |  |
| 원본 | 0.0001 | 0.00005 |
엡실론을 통해 알고리즘의 적용 범위를 결정할 수 있습니다. 값이 작아질수록 범위도 작아져 단순화의 정도가 낮아집니다.
처음에는 0.0001로 적용했는데, 위화감이 있는 것 같아 반절인 0.00005로 변경했습니다.
실제 적용 모습
|
|
- 산책 일지 저장 시 단순화된 경로가 저장된 것을 확인할 수 있습니다.
우글거림이 사라지는 정도의 차이지만, '산책 경로가 최적화되었습니다.'와 같은 메세지를 띄우면 좋을 것 같다는 생각이 들었습니다.
경량화 결과
기존에 저장되어있던 경로 데이터 다섯개에 알고리즘을 적용한 결과
78 -> 18 (약 77% 감소)
83 -> 22 (약 73% 감소)
41 -> 7 (약 82% 감소)
14 -> 4 (약 71% 감소)
5 -> 2 (약 60% 감소)
평균 72.6 % 감소에 성공했습니다.
앞서 구한 최대 바이트인 145KB에 적용하면, 한 산책당 (대략)최대 39KB 정도로 줄어들게 됩니다.
Text 타입이 최대 65.535KB까지 저장할 수 있어 Text 타입으로도 충분히 저장할 수 있는 사이즈가 되었습니다. 경로 데이터 컬럼의 타입을 Medium Text -> Text로 변경하였습니다.
