Geolocating my parents

My parents are on an epic hiking journey from the north of the Netherlands to the south. For their last day, I built them a distance countdown.

The idea I envisioned is for them to be able to look at their phone at any point in the last stage of their journey, and know how many (kilo)meters are remaining, continuously updating this information as they go.

I also wanted to avoid using a third-party API, specifically Google Maps. I myself am quite sensitive about privacy, and while my parents would not care, I figured I should practice what I preach and build it from scratch, so their location never leaves the device - at least not through what I built.

Initially I thought I'd have to settle for calculating the straight-line distance to their end point, but as it so happens, I could do better! The trail they are walking is a well-know and well-documented one named the Pieterpad. I was pleasantly surprised to see the website having the entire trail laid out in exact coordinates, with the GPX files publicly available. Those are XML format - but it wasn't too difficult to convert it to a JavaScript array of {latitude, longitude} points.

For the actual location tracking, I naturally used the web's native Geolocation API. This is well-supported these days and has a handy-dandy method .watchPosition() that continuously provides geographic coordinates and various other types of information, like speed and altitude. I initially tested this to see how accurate it was, and found it to be accurate to about 100 meters, with periods of increased and decreased precision. Because this is not super accurate, and since I have an exact map of the hiking trail, it might be helpful if I "correct" the reported geographical location to the nearest one on the trail, and compute the distance from there.

Latitude and longitude

Unfortunately, the earth is not flat (or so the scientists claim) and this means we are working with an unconventional coordinate system. The "latitude" is how far north or south you are, as a number of degrees from the equator. The equator itself is therefore at latitude 0, the North Pole at 90, and the South Pole at -90. Longitude is the east-west direction, and here Greenwich is decided to be at 0, with positive angles up to 180 spanning in the eastern direction, and values down to -180 in the western direction.

Note

If you think about it, there's no real reason we visualize "North" as "up" besides convention; in space, it's all the same. I found it quite odd to think of a map (and the solar system) upside-down, knowing it is no more upside-down than the traditional perspective.

Since we later want to "snap" geographical positions to the trail, we're going to have to do some math - and because math is easiest on a flat surface (specifically x- and y-coordinates being proportional), I figured it would be a good idea to think of the hiking trail as a flat terrain, converting the latitude/longitude coordinates to x/y ones in meters.

To do this, the idea is to consider a rectangle around the hiking trail, then finding the side lengths, and pronouncing the top-left corner as (0, 0). To find the distance between two geographical coordinates, we can use the Haversine formula: this is my implementation of it.

function haversineDistance(from, to){
	// Create some degree-based trigonometric functions
	const cos = deg => Math.cos(deg * Math.PI / 180)
	const sin = deg => Math.sin(deg * Math.PI / 180)
	const hav = deg => sin(deg / 2) ** 2
	// The (mean) diameter of the earth in meters
	const D = 12_742_000
	// Compute the deltas in either direction
	const dx = to.longitude - from.longitude
	const dy = to.latitude - from.latitude
	// Compute the different parts of the formula
	const p = cos(from.latitude)
	const q = cos(to.latitude)
	const a = hav(dy) + p * q * hav(dx)
	return D * Math.atan2(Math.sqrt(a), Math.sqrt(1 - a))
}

The inputs to this function are {latitude, longitude} objects, as this is the format I converted the points into. I found this is a bit easier to understand than [latitude, longitude], especially because latitude comes first in geographical coordinates, even though it represents what I think of as the "y" direction.

Anyway, now we can pick our rectangle. We'll let the latitude range from about 50.87174 to 50.82603, and our longitude from 5.68177 to 5.81608. Using these points and the above implementation of the Haversine formula, we can compute the side lengths:

Perhaps unsurprisingly, the bottom edge is longer than the top edge. This makes sense if you think about the bounding longitude lines (i.e. the extended left and right edges); they meet at the poles, and are furthest apart at the equator. Since the Netherlands lies in the upper hemisphere, that means that the more north you go, the closer those longitude lines become. Of course, in a flat coordinate system, the rectangle will have to have opposite sides of the same length. So I decided to use 9430 with the assumption that this inaccuracy would end up being insignificant.

Now that we have this rectangle, we can linearly interpolate between its bounds and convert a geographical location to an (x, y) position within the rectangle. In a function, that looks something like

function convertPointToXY({latitude, longitude}){
	const width = 5.81608 - 5.68177
	const height = 50.82603 - 50.87174
	const x = 9430 * (longitude - 5.68177) / width
	const y = 5083 * (latitude - 50.87174) / height
	return [x, y]
}

With this, we can turn all of the geographical points on the trail to (x, y) ones. And this, I thought, would be a good time to see how inaccurate this "flattening" of the map really is. We can measure the length of the trail, both in geographical coordinates with the Haversine formula, as well as the flattened version with Euclidean distances (i.e. using Math.hypot()).

let haversineLength = 0;
for(let i = 0; i < points.length - 1; i++){
	const from = points[i]
	const to = points[i + 1]
	haversineLength += haversineDistance(from, to)
}

let rectangleLength = 0
for(let i = 0; i < points.length - 1; i++){
	const from = convertPointToXY(points[i])
	const to = convertPointToXY(points[i + 1])
	const dx = to[0] - from[0]
	const dy = to[1] - from[1]
	rectangleLength += Math.hypot(dx, dy)
}

console.log(haversineLength) // 16992.908…
console.log(rectangleLength) // 16994.266…

The trail's website itself reports a length of 17km, which is incredibly close to both of these results, and the loss off accuracy ends up being a little over a meter. That's pretty good! And if you are curious - the inaccuracy comes more from rounding to whole numbers than from the globe-to-flat conversion. Retaining the decimals throughout the process gives results that are less than 20cm apart. For my parents' experience though, the inaccuracies are imperceptible either way.

Correcting reported geolocations

The bigger inaccuracy is the location tracking. The Geolocation API seemed, in my testing, to report only vaguely the correct location, usually being within 100m of the real position. In an attempt to make the overal distance calculations more accurate, I thought it'd be a good idea to "snap" the reported location to the nearest point on the trail.

The trail, however, consists of line segments. We'll need to calculate the (minimum) distance to each of the line segments, and then pick the point with the smallest distance, that is, the closest one. There are ways to do this calculation involving equations; first, represent the segment's extended line as ax + by = c, then find the line that is perpendicular to that and crosses the reported geolocation, then compute the point on the original extended line segment, calculate the distance, etcetera. I'll admit, I always start this way, but it always devolves into a pile of cryptic mathematical expressions (likely containing mistakes) so this time I decided I'd throw linear algebra at it instead. We take the starting point (call it S) and the end point E of the line segment. We can then transform them, together with the reported geolocation G, so that S lies on the origin and E lies on the x-axis. To do so, first, translate by -S; this brings S to the origin. Now we rotate the end point, that now lies at E - S, so that it lies on the x-axis (this point is R in the graphic below). Once we've done this rotation, the original point G has moved to a very convenient place (F) where its distance to the line segment is effectively its y-coordinate, and the progress along said line segment is its x-coordinate.

This is (at least for me) much easier to reason about, and implement in a function. So here we go:

// The input parameters match with G, S and E respectively
function getSegmentInfo(point, from, to){
	// The point [dx, dy] represents E-S.
	const dx = to[0] - from[0]
	const dy = to[1] - from[1]
	// The angle to rotate over is therefore
	const angle = Math.atan2(dy, dx)
	// This is the length of the original line segment
	const length = Math.hypot(dx, dy)
	// The point [dpx, dpy] represets G-S.
	const dpx = point[0] - from[0]
	const dpy = point[1] - from[1]
	// Now we rotate G-S over the computed angle.
	// The x-coordinate of the resulting point is...
	const walked = dpx * Math.cos(angle) + dpy * Math.sin(angle)
	// And the y-coordinate is...
	const offset = dpy * Math.cos(angle) - dpx * Math.sin(angle)
	// This is "progress left to make", i.e. "0" means the
	// whole segment has been walked.
	const progress = 1 - walked / length
	// If the "snapped" point is not on the trail, then map
	// to the segment's start or end point instead.
	let distance = Math.abs(offset)
	if(progress > 1) distance = getDistance(point, from)
	if(progress < 0) distance = getDistance(point, to)
	return {progress, distance, length, walked}
}

We can run this function over every segment in the trail, and compare their distances; the smallest distance found wins. And once we have that segment, we even know how far along the segment we are, and this allows us to compute the exact distance to the final destination. In fact, we can do these two things within the same loop!

navigator.geolocation.watchPosition(position => {
	const point = convertPointToXY(position.coords)
	let best = Infinity
	let remainder = 0
	for(let i = 0; i < coordinates.length - 1; i++){
		const from = coordinates[i]
		const to = coordinates[i + 1]
		const segment = getSegmentInfo(point, from, to)
		remainder += segment.length
		if(best.distance <= segment.distance) continue
		remainder = segment.progress * segment.length
		best = segment
	}
	console.log(`${remainder} meters left to go!`)
})

Here it should be noted that this is very inaccurate when far away; a very far location will still get mapped onto the trail, but if this happens to map directly onto the line segment, this will give a distance like as if you were on the trail itself. Even if you are clearly not. This could presumably be resolved by only correcting by a maximum amount. The Geolocation API does provide an accuracy property on its measurements, so this should be doable. But for my use-case, this wasn't relevant, as it was safe to assume my parents were at least close enough to the trail that an over-correction would not be problematic.

Final words

This being my introduction to the Geolocation API, I had a lot of fun! I rarely use these more niche hardware features of a device, so it was great to have an excuse to try it out. I was pleasantly surprised how easy the Geolocation API was to use, and the inaccuracies from it really are my device's fault (other devices seemed to have much better accuracy). Really, the "worst" part of it all was having to go outside to test it ;)

By the way, my parents have now finished their 500km+ hike (congratulations to them!) and the distance countdown worked well for them. A double victory!