[Spring]지도 경로 로딩 최적화 문제 해결하기 (feat. PostGIS, Ramer-Douglas-Peucker)

들어가며

안녕하세요. 현재 크래프톤 정글에서 "넌! 런"이라는 러닝앱을 개발하고 있습니다. GPS를 많이 사용하는 러닝앱 특성상 수많은 좌표들을 최적화하는 문제에 직면하여 고생한 내용을 글로 남기고자 합니다.

 

어떤 문제가 있었나요?

그림 1. 개발 버전 예시 사진

저희 앱에 지정된 경로들을 사용자에게 제시해주고 그중 하나를 선택하여 그걸 경로 안내와 함께 달리고 랭킹을 세우는 기능이 있었습니다.

이 기능을 위해 지도의 경로를 리스트형식으로 띄워야 했습니다.

 

딱 이 기능을 구상했을 때, 정말 쉬울 거라고 생각했습니다. 

경로는 위경도 좌표들의 배열이니까..  배열로 저장하면 되지 않을까..??

근데 잠깐만 이러면 DB Table을 어떻게 구성해야 하는 거지??

 

그렇습니다.

첫 번째 난관: 어떻게 수많은 좌표들을 DB에 저장하는가? 

단순하게 생각해 보면 다음과 같이 DB 테이블을 구성할 수 있습니다.

CREATE TABLE gps_coordinates (
    point_id SERIAL PRIMARY KEY,
    track_id INT NOT NULL,
    point_order INT NOT NULL,
    latitude DECIMAL(10, 8) NOT NULL,
    longitude DECIMAL(11, 8) NOT NULL,
    timestamp TIMESTAMP WITH TIME ZONE DEFAULT NOW()
);

테이블의 한 행이 한 좌표가 되는 것이지요.

 

여기서 문제가 있습니다.

경로의 정확성을 보장하기 위해 1초에 한 번씩 GPS 좌표를 저장하고 속도는 7분 페이스로 가정해 보겠습니다.

러너들은 보통 한 번 달릴 때, 1km~ 7km를 많이 달립니다.

가장 짧은 1km 기준 7분 페이스일 경우 420개의 좌표, 3km면? 1460개, 7km면? 2940개...

기하급수적으로 좌표의 수가 늘어나게 되고 이 gps_coordinates 테이블의 크기는 미친 듯이 커질 겁니다.

그림 2. 미친듯이 증가하는 게 뻔한 테이블 구조

 

심지어 이 수많은 좌표가 결국 하나의 경로만 표시하는 것이니 제공하는 경로가 많아지면??.. 펑 터지게 되는 건 두 눈뜨고 뻔한 상황이었습니다.

 

이를 해결하기 위해 수 많은 탐색 끝에 찾은 것이 바로 PostGIS라는 친구였습니다.

PostGIS??? 그게 뭔가요?

그림 3. PostGIS

PostgreSQL 데이터베이스를 공간 데이터베이스로 확장시켜 주는 오픈 소스 소프트웨어로 이걸 통해 PostgreSQL은 지리적 객체를 저장하고, 인덱싱하며, 쿼리 할 수 있게 됩니다.

 

여기서 뭘 사용할 수 있길래? 이걸 선택하게 된 걸까요?

대표적으로 지원하는 기능들은 다음과 같습니다.

• 공간 데이터 타입 (Spatial Data Types)
• 공간 인덱스 (Spatial Indexes)
• 공간 함수 (Spatial Functions)

여기서 집중한 부분이 "공간 데이터 타입"입니다.

점(Point), 선(LineString), 다각형(Polygon)과 같은 기본적인 2D 도형은 물론, 3D 객체와 래스터(Raster) 데이터까지 저장할 수 있습니다.

제가 원했던 경로인 "선"을 저장할 수 있었습니다.

선을 어떻게 저장하나요?

하나의 바이너리 스트림 형식으로 저장합니다. 그 많은 좌표들의 배열을 단 한 줄의 텍스트가 되는 겁니다.

이는 PostGIS가 WKB(Well-Known Binary) 기법으로 공간의 좌표들을 압축하여 저장하기에 가능합니다.

그림 4. 실제 데이터와 DB에 저장된 모습

그림 4와 같이 수많은 좌표가 단 한 줄로 저장되는 모습을 보실 수 있습니다.

특히 그림 4에 나오는 소공원은 총길이가 10km에 육박하는 데이터로 엄청난 배열의 크기를 보실 수 있습니다.

좋아 보이는데 어떻게 Spring에서 사용하나요?

먼저 PostgreSQL의 확장 프로그램이므로 PostgreSQL을 사용해야 합니다.

이 글에선 PostGIS 설치법은 생략하고 Spring에서의 활용에 집중합니다.

 

Spring의 Gradle Dependencies는 다음과 같습니다.

(Spring Boot 3.5.3 기준)

implementation 'org.locationtech.jts:jts-core:1.18.2' // PostGIS 공간 객체 등의 사용을 위해
implementation 'org.hibernate.orm:hibernate-spatial:6.4.1.Final' // 공간 객체 hibernate를 위해

 

다행히도 JPA와 호환이 잘 됩니다. 따라서 기존 JAP Repository 방식을 그대로 사용할 수 있습니다.

@Entity
@Getter // Lombok 어노테이션만 유지
@Table(name = "track")
@AllArgsConstructor
@NoArgsConstructor
@Builder
public class RunningTrack {
    @Id
    @GeneratedValue(strategy = GenerationType.IDENTITY)
    private Long id;
    
    @Column(columnDefinition = "geometry(LineString, 4326)")
    private LineString path;
    
    //...
}

사용할 Entity에다가 위 코드처럼 columnDefinition을 붙여주면 자동으로 DB에 hibernate가 됩니다.

(LineString 자료형은 jts 라이브러리 사용)

@Column(columnDefinition = "geometry(LineString, 4326)")

위 어노테이션에 대해 조금 더 상세히 보겠습니다.

Geometry는 PostGIS에서 지원하는 큰 범위의 공간 객체 중 하나로 유클리드 좌표계 (평면 지도)를 기반으로 작동합니다. 이에 반해 구면 좌표계 (지구의 곡률 고려) 기반으로 작동하는 Geography가 있습니다.

넌!런 프로젝트에선 평면 지도로 충분히 구현할 수 있으므로 Geometry를 사용하였습니다.

 

이 Geometry에는 더 깊은 계층 구조를 가지고 있습니다.

Geometry
기본 도형(Atomic Geometries)		다중 도형(Multi-Part Geometries)
POINT	공간 상의 단일 지점	MULTIPOINT	여러 개의 점을 하나의 집합으로
LINESTRING	두 개 이상의 점을 순서대로 연결한 선	MULTILINESTRING	여러 개의 선을 하나의 집합으로
POLYGON	하나 이상의 닫힌 선(Ring) 정의되는 면	MULTIPOLYGON	여러 개의 면을 하나의 집합으로

 

여기서 현재 LineString만 사용한 것입니다.

그렇다면 뒤의 4326은 뭘까요??

이는 WGB 84(SRID 4326)을 의미하는 것으로 3차원 지구 모델에서 위도와 경도로 위치를 표현하는 GCS(Geographic Coordinate System, 지리 좌표계)의 한 종류입니다.

일상적으로 사용하는 GPS가 이 좌표계를 사용하고 있기 때문에 PostGIS에 적용하였습니다.

 

멀리멀리 돌아온 것 같지만 테이블이 무차별적으로 커지는 참사는 막을 수 있었습니다.

하지만.. 난관은 여기가 시작이었습니다..

두 번째 난관: 결국 불러오는 건 길고 긴 좌표 배열

그림 5. 지도에 경로 그리기

어쨌든 DB에 저장한 건 하나의 String이지만 결국 지도상에 이를 그리기 위해선 좌표 배열로 변환하고 모두 읽어야 했습니다.

이를 예상하지 못한 건 아니었습니다. 

사버와 DB에 페이지네이션과 인덱스를 도입하여 조금이라도 불러야 할 데이터를 적게 만들고 최적화하였습니다.

그림 6. 무려 10초나 걸리는 로딩

 

하지만.. 한 페이지에 10km짜리 트랙이 2개만 있어도 앱에서 로딩 속도는 미친 듯이 걸리기 시작했습니다.

이는 크게 두 가지의 이유였습니다.

 

1. 좌표 배열이 너무 크다

2. 지도 뷰 자체가 많은 연산이 소모된다

 

이를 해결하기 위한 가장 좋은 방법은 2번을 해결하는 겁니다.

바로 Static Maps API 사용하여 지도 이미지 썸네일 이미지를 미리 만들어둔다면 단지 그걸 서버에서 불러오면 그만입니다.

하지만 구현할 당시에 2번을 위한 인프라가 덜 구성된 상태 + 중간 결과 발표를 위해 1번을 통해 성능 개선 급하게 해결했어야 했습니다.

좌표 배열이 너무 크다면 그걸 줄이면 됩니다.

경로를 단순화해 줄 알고리즘을 찾다가 알게 된 것이 바로 Ramer-Douglas-Peucker (RDP) 알고리즘이었습니다.

Ramer-Douglas-Peucker 알고리즘이 뭔가요??..

그림 7. 알고리즘 작동 예시

 

알고리즘 동작 과정을 간단히 요약하면 다음과 같습니다.

1. 경로의 첫 점과 끝 점을 이은 선에서 가장 먼 점을 중간점으로 잡는다. 이때 선에서의 거리가 ε 보다 커야만 한다. 만약 아니라면 선택하지 않는다.

2. 첫 점과 중간점에 선을 새로 긋는다. 그 선을 기준으로 그 사이에 있는 모든 점 중에서 사이가 거리가 ε  보다 큰걸 다 고른다.

3. 중간점과 끝 점을 기준으로 다시 1번을 진행한다.

 

복잡한 알고리즘이지만 이를 쉽게 해주는 라이브러리가 있습니다.

바로 이전에 설치했던 jts 라이브러리에 포함되어 있었습니다.

 

경로 단순화하는 법

public static TrackListItemDto from(RunningTrack track){
    double epsilon = 0.0003;
    LineString simplifiedLine = (LineString) DouglasPeuckerSimplifier.simplify(track.getPath(), epsilon);
    List<CoordinateDto> coordinateDtos = CoordinateConverter.convertLineStringToCoordinates(simplifiedLine);
    return new TrackListItemDto(track.getId(), track.getName(), track.getTotalDistance(),coordinateDtos);
}

 

아주 사용법도 쉽습니다.

DB에 저장해 둔 LineString을 꺼내서 DouglasPeuckerSimplifier.simplify 메서드에 ε (epsilon)과 넣어주면 끝!

여기서 좌표의 저장을 위경도로 했기 때문에 거리가 아주 미세하기 때문에  ε 을 0.0001부터 차근차근 올리는 것을 추천합니다.

값이 올라가면 더 경로가 단순화됩니다.

 

근데 경로가 단순화되면 실제 경로하고 많이 달라지지 않을까요?

그림 8. 왼쪽 실제 경로, 오른쪽 단순화된 경로

썸네일의 목적으로 사용했기 때문에 심하게 단순화되지 않는 이상 문제는 없었습니다.

또한 ε 0.0003 기준으로도 대략 원래 경로를 파악할 수 있었기에 괜찮다고 생각이 들었습니다.

결과

그림 9. 1초 조금 넘는 시간까지 줄어든 모습

 

끝내며

여기까지가 제가 개발 초기에 경험했던 경로 관련 문제였습니다.

문제는 엄청 많았지만 다른 글로 돌아오도록 하겠습니다.

 

---

최적화하는 게 재미있을 줄은 몰랐네요.

제 천직인가 봅니다.

사실 static maps로 변경하면 두 번째 문제는 쉽게 해결된다는 사실

 

출처

https://m.blog.naver.com/dorergiverny/223113215510

[C++] 다각형 근사화 Douglas-Peucker 알고리즘 원리 총정리 - DP Algorithm approxDP poly 간소화 간략화 polygon

https://en.wikipedia.org/wiki/Ramer%E2%80%93Douglas%E2%80%93Peucker_algorithm

Ramer–Douglas–Peucker algorithm - Wikipedia

 

https://postgis.net/docs/manual-3.3/postgis-ko_KR.html

PostGIS 3.3.9dev 사용자 지침서