Picture stitching dozens of GPX files — hiking stages, cycling segments, a long-distance trail — into one line on a map. Merging a courier's day from separate leg recordings, or lining up log fragments pulled from several servers, is the same job. Every piece has a start and an end, so the obvious approach is a nearest-neighbor greedy: "attach whichever piece starts closest to where the current one ends." When every piece is present, that works almost every time. But when even one piece is missing, merging track segments this way joins them in the wrong order and the polyline backtracks — the drawn route goes forward, doubles back, then goes forward again.
Why does nearest-endpoint joining backtrack around a missing piece?
Nearest-neighbor greedy assumes "the closest piece is the next piece," and that assumption only holds when nothing is missing. If piece 3 is absent, the nearest thing to the end of piece 2 is no longer the start of piece 4. On a winding route — a coastline, a mountain trail — piece 6 across a bay or valley is often closer than piece 4. The greedy grabs 6, then comes back for 5 and 4. No error is raised, and the result is a plausible single line that uses every piece.
What should you join by instead?
Do not infer order from distance; join by the order the source already has. Most data carries its order somewhere.
- Stage or segment numbers — the number inside a name like "Stage 12", or a sequence number in the file name
- Time — the
<time>on each GPX point (GPX 1.1 schema), or log timestamps - The source's list order — the array order an API returned, the stop sequence on a timetable
Use distance only after the order is fixed. If distance only decides each piece's direction ("make the end nearest the previous tail the head"), a bad distance cannot scramble the order.
Steps for joining by source order
- Extract an order number from the name or a field. Collect pieces with none (spurs, detours, connectors) separately
- Sort by that number. If a number has both a main route and a detour, use the main route; use the detour only when the main route is missing
- For the first piece, make the end closest to the official start the head
- For each following piece, make the end closest to the previous tail the head, reversing its points if needed
- Leave missing numbers as visible gaps and fill them separately — a straight line, geographic data (coastline, road network), or a re-request to the source
If you fill a gap with "whatever is closest," the greedy sneaks back in. A gap has to show up as a gap before anyone can fix it.
How do you measure backtracking as a number?
Backtracking is hard to see by eye. With dozens of pieces and short reversals, it still looks like one line. So measure two numbers.
- Pairs of points visited twice — count a pair when two points far apart along the route (say, several km of route distance) sit within a few tens of meters on the ground. A clean route scores near zero
- Total length versus the source's stated length — if there is an official total, compare. Backtracking inflates length
// A pair counts as 'visited twice' if points >= minGap apart along the route lie within 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; // for many points, use a grid to find neighbors
}
Put this number in a test, and backtracking gets caught the moment a data change brings it back.
What happened to us
We were drawing a trail several thousand kilometers long as a single brush stroke on a map, using public open data. The source provided GPX for only about half of the stages, and our stitching code was a greedy that took whichever stage had the nearest endpoint next. A person looking at the screen pointed out that along an island-heavy stretch of coast and at the far end of another coast, the stroke went forward, turned back, and went forward again.
- Measured: 47 point pairs visited twice, and total length inflated to 4,378 km
- Fix: join by the stage number in each name (spurs excluded, detours only when the main stage is missing), and fill missing stages with coastline data. The joining function got ten tests
There was not a single code error. A gap in the data had quietly broken the algorithm's assumption.
Checklist
- Does the joining code pick the next piece by distance alone?
- Does the source carry an order number, timestamps, or a list order — and do you use it?
- Do missing numbers show up as gaps, or are they silently skipped?
- Do your tests measure revisited point pairs and the length difference?