3. 경로 최적화로 좌표 데이터 약 73% 감소

 

 

 

경로를 최적화하여 좌표 데이터 175개를 46개로 약 73% 감소시킨 경험과 고민했던 부분에 대해서 설명드리려 합니다.

 

 

 

 

문제 인식

---

 

 

러닝 앱에서 4~5초마다 현재 위치를 좌표 리스트에 추가해주고, 이 좌표 리스트로 경로를 그려주었습니다.

하지만, 위치 정보는 오차가 존재합니다. (확인한 결과 latitude는 현재 위치에서 약 0.0005 정도, longitude는 약 0.0002 정도 오차가 있는 걸로 확인 됩니다.) 오차가 존재하기 때문에 유저가 일직선으로 뛰어도 경로에는 일직선으로 보이지 않고 삐뚤빼둘하게 그려집니다.

 

 

 

왼쪽) 위치 정보 오차에 따른 문제, 오른쪽) 그리고 싶은 경로

 

위 사진에서 오른쪽의 빨간 선과 같이 직선으로 진행하는 경로에서 직선에서 시작하는 점과, 끝나는 점을 하나로 이어주고, 중간에 있는 점들을 제거해주기만 해도 경로를 더 보기 좋게 그릴 수 있으며, 좌표 데이터도 많이 줄일 수 있다고 생각했습니다.

 

 

 

💡 latitude는 현재 위치에서 약 0.0005 정도, longitude는 약 0.0002 정도 오차가 있는 걸로 확인한 이유

현재 위치에서 움직이지 않고 45분부터 약 4분간 계측한 52개의 Location 정보입니다.

이를 txt 파일로 만들고 latitude와 longitude만 가져와 각각 최대,최소를 비교해주었습니다.

 

 

latitude는 최소 37.367360, 최대 37.368002, 차이는 약 0.001

longitude는 최소 126.931544, 최대 126.931904, 차이는 약 0.0004 입니다.

 

 

즉, 파란 원의 위도 범위는 약 0.001, 경도 범위는 약 0.0004 만큼 입니다.

현재 위치에서의 오차이기 때문에 이를 반으로 쪼갠

latitude는 현재 위치에서 약 0.0005 정도, longitude는 약 0.0002 정도 오차가 있는 걸로 생각하게 되었습니다.

 

 

 

 

고민점

---

 

 

1. 네비게이션 경로 알고리즘 이용

 

https://prezi.com/p/zosd6vh3813l/hidden-markov-model/

https://www.slideshare.net/ifkakao/gps-113145463

 

네비게이션 경로 알고리즘을 찾아보면서 카카오에서 적용한 맵매칭 방식에 대한 자료를 찾아볼 수 있었습니다. 위 사진처럼 세모의 좌표 점들을 도로네트웍에 링크하여 경로를 표시하는 방법이었습니다.

 

 

하지만, 러닝을 하는 사람들은 자유롭게 움직일 수 있는데 인도, 주택가 골목길, 건물 내부 등에 따라 실제 경로와 다를 수 있기 때문에 저희 러닝 앱에서는 사용할 수 없다고 생각했습니다.

 

 

실제 예시입니다.

 

 

 

맵매칭을 사용한다면 도로 정보에 따라 파란색 경로로 이동하게 될 것입니다.

 

하지만 실제로는 빨간색 경로에 계단이 존재하기 때문에 계단으로 내려간 사람에게 파란색 경로로 지도에 표시해주게 된다면 괴리감이 들 수 있다고 생각했습니다.

도로 정보가 없는 건물을 통과할 때에도 마찬가지이기 때문에 러닝 경로를 표시해주기 위해서는 네비게이션처럼 맵매핑을 사용하는 것보다 실제 러닝 경로를 도로 정보 없이 최적화 해주는 것이 낫다고 생각했습니다.

 

 

 

 

2. 불필요한 좌표 제거

 

위 그림처럼 직선 러닝 경로를 그리는 데에 불필요한 좌표를 지우고자 했습니다.

 

 

불필요한 좌표 a

 

위 그림처럼 진행 방향에서 파란 선과 빨간 선의 각도 차이가 크지 않다면 중간 좌표를 버려도 경로를 그리는 데에 크게 영향을 미치지 않습니다.

 

 

 

불필요한 좌표 b

 

너무 가까운 좌표입니다. 그림에 보이는 회색 좌표처럼 가까운 좌표는 직선 거리를 그리는 데에 크게 영향을 미치지 않습니다.

 

 

 

추가로 고려해야 할 점 : 거리에 따라 영향을 받는 각도

 

불필요한 좌표 a 에서 각도로 불필요한 좌표인지 판단하게 됩니다. 하지만 이전 직선 거리가 충분히 긴 거리라면 다음 좌표에 따라 영향을 크게 받기 시작합니다.

 

위처럼 각도가 완만한 좌표들을 버리고 1km 거리의 직선 경로가 생겼다고 가정하겠습니다.

 

그리고 새로운 추가할 좌표를 빨간 점으로 나타내겠습니다.

 

빨간 점이 각도가 완만하다고 판단되면 위처럼 이전 좌표를 버리고 직선 거리를 그리게 될 것입니다. 짧은 직선보다 변경되는 게 눈에 크게 보이게 될 것입니다. (방향을 천천히 전환하는 경우에 특히 문제가 됩니다) 그렇기 때문에 직선 거리가 길어지게 되면 완만하다고 보는 각도의 수치를 줄였습니다.

 

 

 

 

 

 

 

3. 거리 구하기

 

불필요한 좌표를 버리기 위해 현재 직선 거리를 구해야했습니다.

 

(https://www.ibm.com/docs/ko/db2/11.5?topic=systems-geographic-coordinate)

지구는 타원형이기 때문에 위 사진처럼 위도에 따라 경도 1도의 거리는 다릅니다.

그렇기 때문에 위도에 따른 경도의 거리도 생각하여 거리를 구해주어야 했습니다.

 

 

https://developer.android.com/reference/android/location/Location#distanceTo(android.location.Location)

운이 좋게도 Location class 내에서 정확한 직선 거리를 구하는 함수가 구현되어 있었습니다.

(WGS84는 지구의 형태, 위치를 정확하게 나타내기 위한 좌표 체계 중 하나로 GPS에서도 사용되는 현재 가장 정확한 좌표 체계입니다.)

 

 

 

 

결과

---

 

위처럼 뛰는 방향이 완전한 직선이 아니더라도 일직선으로 나타내주는 최적화를 할 수 있게 되었고

 

좌표 데이터를 약 73% 감소한 것을 볼 수 있었습니다.