← Blog

Contours every 10 m, bold every 50Shade: Horn's slope, twice as steepThe terrain is made up
Hillshading by Horn's method and contour lines by marching squares, computed on a made-up terrain with the same rules walker uses: lit from the north-west, slopes drawn twice as steep, a line every 10 m and a bold one every 50.
Under the hood

Contour lines and hillshading for an offline map

How walker turns open lidar terrain into hillshading and contour lines for its offline map: Horn's method, marching squares, Douglas–Peucker and MVT.

, updated · Malik · 16 min read

Why a hiking map needs the terrain

A map drawn from OpenStreetMap alone shows every path, but not the hill the path climbs. On a hike that is half the story: you want to see the valley you are walking up and how steep the next stretch will be.

walker, the walk, hike and ride tracker I make for Android, is written in Rust, and its map is built from OpenStreetMap. It had the terrain before it had any relief to show: to put a cleaned track's heights on the ground instead of wherever GPS guessed, it downloads the terrain of each map region beside its map (why that matters for the climb). This post is about the second use I found for those heights: a Topo layer, with hillshading and contour lines. How the layer looks from the walker's side is in offline maps for hiking.

Why make it ourselves

The obvious alternative is to download finished hillshading and contour tiles. But the tile servers behind OpenStreetMap's styles, Carto, CyclOSM, OpenTopoMap and Tracestrack, all forbid bulk or offline download. And walker's rule is that nothing is streamed while you walk: every layer is a download you start, and each download is logged.

So walker makes the relief itself, from open terrain data, and the work has moved twice. The first version made a whole region's relief on the phone once its terrain had arrived. It worked, but it was slow, and it could use only the coarser of the two terrain zooms: the fine one would have taken about half an hour per region on a phone. Then a tool of mine, the quarry, did the work once on a server for everyone, and walker downloaded hillshading and contour lines from its own map mirror beside the terrain, in blocks of about 25 × 39 km.

That cost space. On an alpine block near Innsbruck the terrain is 39.2 MB, its hillshading 8.7 MB and its contour lines 6.0 MB, so the two made from the terrain were 27 % of the download; on lowland blocks about a fifth. The phone holds the terrain anyway, so now it makes each tile of relief from it the moment the map draws that tile, and downloads only the terrain. Only what you look at is made. The code is the same Rust as on the server, and on the trail the relief is there wherever the terrain is, with or without a signal.

Where the heights come from

The terrain comes from Mapterhorn, an open project that collects national and regional elevation models into one tile set. Its tiles are Terrarium-encoded WebP images, 512 px across, bundled into PMTiles archives: one planet.pmtiles for zooms 0 to 12, and regional files for zooms 13 to 17.

Terrarium packs a height into a pixel's three colour channels. As Tilezen's documentation defines it, the height in metres is

h=256 red+green+blue256−32768h = 256\,\text{red} + \text{green} + \frac{\text{blue}}{256} - 32768
(1)

where red, green and blue are the pixel's channels, each a whole number from 0 to 255. That is whole metres in red and green and 1/256 m in blue, from −32,768 m up. A 32-bit float holds it exactly, so walker decodes into one.

The quarry takes zoom 12 (about 12 m per pixel at 51° N) from the planet file for each block, and zoom 14 (about 3 m) where a finer model covers the ground. PMTiles is a single-file archive read with HTTP range requests, so it fetches only the block's tiles and never the whole planet. Over Germany, every state's source is its lidar terrain model, DGM1, which measures the bare ground, so the contour lines follow the slope you walk on. Where there is no open national model, Mapterhorn uses Copernicus GLO-30, a surface model that follows tree tops and roofs. There the contour lines follow the tree tops through a wood, and walker's credits name Copernicus as a source. In Germany the question doesn't arise: all sixteen states are lidar.

How big a pixel is

Everything that follows measures slopes and lengths, so it needs a pixel's width on the ground, and on a Web Mercator tile that width depends on the latitude. The OpenStreetMap wiki gives the latitude φ\varphi of tile row yy at zoom zz, where the world is 2z2^z tiles across and the rows count down from the north, as

φ=arctan⁡ ⁣(sinh⁡ ⁣(π(1−2y2z)))\varphi = \arctan\!\left(\sinh\!\left(\pi\left(1 - \frac{2y}{2^z}\right)\right)\right)
(2)

Mercator stretches the map by 1/cos⁡φ1/\cos\varphi, so a pixel there is

Δ=2πRcos⁡φw⋅2z\Delta = \frac{2\pi R \cos\varphi}{w \cdot 2^z}
(3)

metres wide on the ground, where RR is the Earth's equatorial radius and w=512w = 512 the tile's width in pixels. At zoom 12 and 51° N that is 12.03 m; at zoom 14, 3.01 m. Across one tile the latitude changes too little to matter, so walker works it out once per tile.

85°79°67°41°0°Zoom 3, north half0°40°80°102019.11 m at 0°12.03 m at 51°Pixel width at zoom 12
Figure 1. Left: zoom 3's northern tile rows, equal on the map, with the latitude of each row's edge from the formula above; each orange bar is as long as the row's width is on the ground, cos⁡φ\cos\varphi of it. Right: a pixel's width Δ\Delta at zoom 12 against latitude.

walker doesn't resample the terrain for Topo: each pixel of the WebP is one height, one pixel of hillshading and one grid point for the contours.

Hillshading with Horn's method

Hillshading lights the terrain as if the sun stood low in the north-west, so slopes facing the light are bright and slopes facing away are dark. walker uses the standard hillshade light, from 315° and 45° above the horizon, which is also ArcGIS's default.

The slope at each pixel comes from its eight neighbours, by the 3×3 kernel known as Horn's method, after Berthold Horn's Hill shading and the reflectance map (Proceedings of the IEEE, 1981). It takes the heights of the three pixels to the east minus the three to the west, with the middle row weighted twice, and divides by 8Δ8\Delta: the weights add up to four, and east and west lie two pixel widths apart. Then the same from north to south. That gives two slopes, pp towards the east and qq towards the north, both in metres per metre. Why Horn's kernel? Zevenbergen and Thorne (1987) take the slope from the four direct neighbours alone. Horn's counts the diagonals too, which smooths out single noisy pixels, and it is the kernel ArcGIS's hillshade uses. At a tile's edge, where one side's neighbours are missing, walker falls back to a one-sided difference.

True to scale, a hill barely shows on a 512 px tile of lowland. walker draws every slope twice as steep as it is, an exaggeration of k=2k = 2, so a 10 % gradient is shaded as 20 %.

From the two slopes comes the surface's normal, the arrow standing straight out of the ground. The light is a unit vector too, pointing west and north in equal parts, and up. How lit the pixel is comes down to the cosine of the angle between the two:

L=max⁡(0, n⋅l)=max⁡ ⁣(0, 22+p2−q21+p2+q2)L = \max(0,\ \mathbf{n} \cdot \mathbf{l}) = \max\!\left(0,\ \frac{\tfrac{\sqrt2}{2} + \tfrac{p}{2} - \tfrac{q}{2}}{\sqrt{1 + p^2 + q^2}}\right)
(4)

where n\mathbf{n} is the normal, l\mathbf{l} the vector towards the light, and pp and qq the two slopes, with the exaggeration in them. LL runs from 0, facing away or in its own shadow, to 1, facing the light square on. Flat ground gets the sine of the light's altitude, about 0.707.

p: rises east−10+1−20+2−10+1q: rises north+1+2+1000−1−2−1North at the top; the centrepixel has no weightlight0.920.39flat 0.71
Figure 2. Left: Horn's weights for pp and qq, before the division by 8Δ8\Delta. Right: a made-up eight-sided pyramid seen from above, its faces rising 20 %, drawn as 40 % (k=2k = 2), shaded by LL with the light from 315° at 45°: the more orange, the more light. The face towards the light is lit most, the one away from it least, and flat ground gets 0.71.

A hillshade lies over the map, so it has to leave the map readable. walker stores each pixel's LL as one grey byte, and a table of every grey turns it into a colour as the tile is made. Ground close to flat is clear, so the map shows through the plains unchanged. Darker greys become black, growing more opaque into the deepest shadow, and lighter ones white, which matters only on the dark theme. The quarry's tiles were at first paletted PNG with a small fixed set of tones, because the number of tones set their size, and the steps between tones showed as bands. Made on the phone, a tile is never stored, so the shading runs smoothly from light to dark.

The terrain is shaded at zoom 14 and zoom 12 from its own heights, and the hillshading goes down to zoom 10, so the relief stays when you zoom out to see a whole valley. Every other zoom is shaded from heights averaged 2×2 from the next finer zoom; its pixels are twice as wide, so the slopes stay in metres per metre. Zoom 13 averages four zoom-14 tiles, and only where the fine terrain covers all four; elsewhere the map draws zoom 12's tile, scaled. Zoom 11 averages four zoom-12 tiles and zoom 10 four zoom-11 ones, so a zoom-10 tile reads sixteen terrain tiles. walker keeps the latest zoom-11 averages, so a zoom-10 tile next to the last one doesn't read them all again.

Made tiles are kept in memory only, and made again when the map comes back to them. A cache on the phone's storage would take back part of the space the change saved. The layer makes its tiles on a thread of its own, newest request first, and drops the oldest requests when too many wait: a fling across a valley asks for dozens of tiles the view has already left.

Contour lines by marching squares

Contours are traced by marching squares, the two-dimensional cousin of marching cubes (Lorensen and Cline, 1987). The grid of heights is cut into cells of four corners, one pixel apart. A cell is crossed by every level between its lowest and highest corner. For each level ℓ\ell, each corner is above or below. Reading the corners clockwise from the north-west as bits gives the case

κ=8 sNW+4 sNE+2 sSE+sSW\kappa = 8\,s_{\text{NW}} + 4\,s_{\text{NE}} + 2\,s_{\text{SE}} + s_{\text{SW}}
(5)

where each ss is 1 if that corner is at or above ℓ\ell and 0 if not. That is 16 cases. Cases 0 and 15 have no line. Each other case says which of the cell's edges the line crosses, and linear interpolation places the crossing along the edge. Between the edge's two corners uu and vv, of heights huh_u and hvh_v, the line crosses at

t=ℓ−huhv−hu,P=Pu+t (Pv−Pu)t = \frac{\ell - h_u}{h_v - h_u}, \qquad P = P_u + t\,(P_v - P_u)
(6)

where tt is the fraction of the way from uu to vv, and PuP_u, PvP_v and PP are points in pixels. An edge is crossed only when one end is above and the other below, so hv≠huh_v \ne h_u and the division is safe.

Two cases are ambiguous: 5 and 10, two opposite corners above and the other two below. That is a saddle, and the line could run either way (Figure 3). walker decides by the cell's middle, taken as the average of its corners:

hˉ=14 (hNW+hNE+hSE+hSW)\bar h = \tfrac14\,(h_{\text{NW}} + h_{\text{NE}} + h_{\text{SE}} + h_{\text{SW}})
(7)

If hˉ\bar h is on the same side of ℓ\ell as the north-west corner, the north-west and south-east corners join through the middle; otherwise the lines cut those two corners off.

412437428396t = 0.32PCase 6, level 420425408431414mean 419.5Case 10, a saddle
Figure 3. Two cells with made-up corner heights, traced at the level 420 m; filled corners are at or above it. Left: the line crosses the top and bottom edges, each crossing PP placed by tt. Right: a saddle. The centre's mean is below the level, unlike the north-west corner, so the lines (solid) cut the north-west and south-east corners off; the dashed pair is the other reading.

The pieces then have to be joined into lines. walker names each crossing by the edge it lies on, so two neighbouring cells give a shared edge one name, compute its crossing from the same two heights, and meet in exactly one point. Apart from sorting the ends, joining them end to end is then a single pass, open lines first and closed rings after.

walker draws a line every 10 m, and an index line every 50 m that carries its height as a label, so you can count the climb ahead of you on the map. On the layer sheet, the panel behind the map's layers button, Topo has two switches, Hillshading and Contour lines, and the second says so: every 10 m, labelled every 50 m.

The tricky part is the tile edge. Traced alone, each tile would stop one cell short of its neighbour, and the lines would have gaps. walker traces each tile with a column and a row of its east and south neighbours' heights added, so the two tiles share those heights and their lines meet exactly, across the edge of a block too. Where the neighbour isn't on the phone, the tile's own edge is repeated. Contours are traced at zooms 12 and 14; zoom 13 shows zoom 12's.

Fewer points: Douglas–Peucker

Marching squares gives a point in every cell a line crosses, far more than a drawing needs. walker simplifies each line with the algorithm of Douglas and Peucker (Cartographica, 1973). It keeps the two ends, finds the point farthest from the straight line between them, and keeps it if it lies further off than a tolerance. Then it repeats on each half.

The one deliberate change: the algorithm as usually written measures a point's distance to the endless line through the two ends, and walker measures it to the segment between them. Beyond an end, that distance is the larger, so walker may keep a point the usual version would drop, never the other way. It also settles closed rings, whose ends coincide: the distance becomes the plain distance from the start, with no special case in the code. Afterwards, tiny closed rings are dropped as noise in the terrain rather than knolls.

farthest: kept1. Chord, tolerance band2. Result: 4 of 16 points keptABPBeyond an endto segmentto line
Figure 4. Left, on a made-up line: the first step finds the point farthest from the chord between the ends, outside the band of the tolerance, so it is kept and each half is done again; the result keeps the orange points. Right: for a point PP beyond the end BB, the distance to the segment is ∣PB∣|PB|, larger than the distance to the endless line through AA and BB. When AA and BB coincide, as on a closed ring, it is the plain distance from AA.

Writing vector tiles

Contours are written as Mapbox Vector Tiles, the format of walker's OpenStreetMap maps, so one renderer draws both, with a separate style for the contours. walker had an MVT encoder only in its tests; for contours I made it a real one. Each line carries its height and whether it is an index line, because the map style can't compute a remainder.

What it costs

The first version made Sachsen-Anhalt's Topo layer from zoom 12 in 43 s on my desktop, and I estimated about half an hour on a phone for zoom 14. That is why it stayed at zoom 12: it made a whole region at once. One tile at a time is a different sum. On my desktop, over the alpine block near Innsbruck with nothing cached, a tile takes:

Zoom Hillshading Contour lines
10 108 ms none
11 4 ms none
12 9 ms 113 ms
13 24 ms from 12
14 8 ms 29 ms
Table 1

Zoom 10 reads sixteen terrain tiles and makes four averages, which zoom 11 then reuses. Zoom 12's contour lines are the slowest: in the Alps, a line every 10 m over 2 km of relief, traced over 512 × 512 heights and simplified. A phone is perhaps three to five times slower, so about half a second for that tile, on the layer's own thread while the map stays responsive. I haven't timed it on a phone yet; that is the next check.

The download is the terrain alone. Over Tyrol, a block's terrain is 36 to 41 MB. In Map packs it is the row Terrain & topo, which you add to a region or leave out, and the hillshading and contour lines come with it without a byte more.

The other two layers: TopPlusOpen and aerial photos

The layer sheet offers two more layers: TopPlusOpen, the official topographic map of Germany's Federal Agency for Cartography and Geodesy (BKG) and of other countries where theirs is open, and Aerial, aerial photos from the German states and other countries' survey offices. They come over WMS and WMTS, standards for map-image servers, and none of the services states terms for fetching many tiles. So the quarry fetches each area once, one request at a time and spaced apart, and packs the tiles into the same blocks. On the phone you frame an area and tap Download this area, and walker downloads the blocks it touches from the mirror. Mecklenburg-Western Pomerania stamps its copyright into every aerial image, so it is left out.

Credits

The layers stand on other people's open data, and walker names each source on the map while it is on screen. A tap lists the links.

What it bought

Making the relief per tile on the phone keeps what the quarry bought and gives back the space. The Topo layer still uses the fine terrain where there is one, because a tile at a time is cheap where a whole region at once was not. The download is a fifth to a quarter smaller. The phone does some work for it, but only for the tiles on screen. And nothing about the privacy changed: the terrain comes from the same mirror as the map, which learns which blocks you fetch and never where you walk.

The maths above is the same in all three places, and none of it is new: Horn's slope, the cosine of the light, sixteen cases of marching squares and Douglas and Peucker's simplification. What it takes to make a hiking map from open data is less a clever algorithm than choosing where the work runs. Here it runs on your phone, for the part of the map you are looking at, and the hill the path climbs is on the map.

walker Plan your hikes and record every walk, hike and ride on offline maps that come with the app. Buy once, no account, and your walks never leave your phone. Coming soon to Google Play.