등산로·자전거길·둘레길 코스를 GPX 파일 수십 개로 받아 지도 위에 한 줄로 이어 그리는 일을 떠올려 보자. 배송 기사의 하루 경로를 구간 기록으로 합치는 일이나, 여러 서버에서 나눠 받은 로그 조각을 한 흐름으로 맞추는 일도 같다. 조각에는 시작점과 끝점이 있으니, 가장 쉬운 방법은 "지금 끝점에서 가장 가까운 시작점을 가진 조각을 다음으로 붙인다"는 최근접 이웃(nearest neighbor) 그리디다. 조각이 다 있으면 이 방법은 거의 늘 맞는다. 그런데 조각이 하나라도 빠지면 GPX 트랙 이어 붙이기가 역주행을 만든다 — 조각을 합친(merge track segments) 폴리라인(polyline)을 그려 놓고 보면, 순서가 틀린(wrong order) 채로 경로가 앞으로 가다가 뒤로 돌아왔다가 다시 간다.
왜 최근접 연결은 빠진 조각 앞에서 되돌아가나
최근접 그리디는 "가장 가까운 것이 다음 것"이라는 가정에 기대는데, 그 가정은 조각이 하나도 빠지지 않았을 때만 성립한다. 3번 조각이 없으면 2번의 끝에서 가장 가까운 것은 더 이상 4번의 시작이 아니다. 해안선이나 산길처럼 굽은 경로에서는 만(灣)이나 골짜기 건너편의 6번이 4번보다 가까운 일이 흔하다. 그리디는 6번을 물고, 5번과 4번을 주우러 되돌아온다. 오류는 하나도 안 나고, 결과는 조각을 전부 쓴 그럴듯한 한 줄이다.
무엇으로 이어야 하나
순서를 거리로 추정하지 말고, 원천이 이미 가진 순서로 잇는다. 대부분의 데이터에는 순서가 어딘가 적혀 있다.
- 코스 번호·구간 번호 — "12코스" 같은 이름 속 숫자, 파일명의 일련번호
- 시각 — GPX 의 각 점에 붙은
<time>(GPX 1.1 스키마), 로그의 타임스탬프 - 원천이 준 목록 순서 — API 가 돌려준 배열 순서, 노선표의 정류장 순번
거리는 이 순서가 정해진 뒤에 쓴다. 조각의 방향(정방향·역방향)을 정할 때 "앞 조각의 꼬리에 가까운 끝을 머리로" 고르는 데에만 거리를 쓰면, 거리가 틀려도 순서는 안 무너진다.
순서 번호로 이을 때의 순서
- 이름·필드에서 순서 번호를 뽑는다. 뽑히지 않는 조각(지선·우회로·연결로)은 따로 모은다
- 번호순으로 정렬한다. 같은 번호에 본선과 우회로가 같이 있으면 본선을 쓰고, 본선이 없을 때만 우회로를 쓴다
- 첫 조각은 기점(출발점)에 가까운 끝을 머리로 둔다
- 다음 조각마다 앞 조각의 꼬리에 가까운 끝을 머리로 삼아, 필요하면 점 순서를 뒤집는다
- 번호가 비는 자리는 빈칸으로 남겨 두고 따로 메운다 — 직선, 지형 데이터(해안선·도로망), 또는 원천에 다시 요청
빈칸을 "가장 가까운 것"으로 메우려 들면 그리디가 다시 들어온다. 빈칸은 빈칸으로 드러나야 고칠 수 있다.
역주행은 어떻게 숫자로 재나
눈으로 보면 역주행은 잘 안 보인다. 조각이 수십 개고 되돌아가는 구간이 짧으면 한 줄로 이어진 것처럼 보인다. 그래서 두 숫자로 잰다.
- 같은 자리를 두 번 지나는 점 쌍의 수 — 경로상에서 멀리 떨어진(예: 경로 거리로 몇 km 이상) 두 점이 지리적으로는 몇십 m 안에 있으면 한 쌍으로 센다. 정상 경로라면 0 에 가깝다
- 총 길이와 원천이 밝힌 길이의 차 — 공식 총연장이 있으면 견준다. 역주행은 길이를 부풀린다
// 경로 거리로 minGap 이상 떨어진 두 점이 radius 안에 있으면 '두 번 지난 쌍'
function revisits(points, { radius = 50, minGap = 5000 } = {}) {
const along = [0];
for (let i = 1; i < points.length; i++) along.push(along[i - 1] + dist(points[i - 1], points[i]));
let pairs = 0;
for (let i = 0; i < points.length; i++)
for (let j = i + 1; j < points.length; j++)
if (along[j] - along[i] >= minGap && dist(points[i], points[j]) < radius) pairs++;
return pairs; // 점이 많으면 격자로 이웃만 찾는다
}
이 숫자를 시험에 넣어 두면 데이터가 바뀌어도 역주행이 돌아오는 순간 잡힌다.
우리가 겪은 일
수천 km 짜리 둘레길 코스를 공공 데이터로 받아 지도 위에 한 획으로 긋는 일이었다. 원천은 코스의 절반 정도만 GPX 로 주었고, 이어 붙이는 코드는 끝점이 가까운 코스를 다음으로 무는 그리디였다. 섬과 반도가 많은 남해안 구간과 서해안 끝에서 획이 앞으로 갔다가 뒤로 돌아오는 것을 화면을 본 사람이 짚었다.
- 실측: 같은 자리를 두 번 지나는 점 쌍이 47 개, 총 길이가 4,378 km 로 부풀어 있었다
- 고친 것: 코스 이름의 번호순으로 잇고(지선 제외, 우회로는 본코스가 없을 때만), 빠진 코스 자리는 해안선 데이터로 메웠다. 이어 붙이는 함수에 시험 열 개를 붙였다
코드 오류는 한 줄도 없었다. 데이터의 빈칸이 알고리즘의 가정을 조용히 깨뜨린 것이었다.
확인 목록
- 조각을 잇는 코드가 거리만으로 다음을 고르고 있지 않은가
- 원천에 순서 번호·시각·목록 순서가 있는가 — 있으면 그것을 쓰는가
- 빠진 번호가 빈칸으로 드러나는가, 아니면 조용히 건너뛰어지는가
- '두 번 지난 점 쌍'과 총 길이 차를 시험으로 재고 있는가