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
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 of tile row at zoom , where the world is tiles across and the rows count down from the north, as
Mercator stretches the map by , so a pixel there is
metres wide on the ground, where is the Earth's equatorial radius and 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.
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 : 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, towards the east and 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 , 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:
where is the normal, the vector towards the light, and and the two slopes, with the exaggeration in them. 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.
A hillshade lies over the map, so it has to leave the map readable. walker stores each pixel's 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 , each corner is above or below. Reading the corners clockwise from the north-west as bits gives the case
where each is 1 if that corner is at or above 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 and , of heights and , the line crosses at
where is the fraction of the way from to , and , and are points in pixels. An edge is crossed only when one end is above and the other below, so 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:
If is on the same side of as the north-west corner, the north-west and south-east corners join through the middle; otherwise the lines cut those two corners off.
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.
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 |
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.
- The map: © OpenStreetMap contributors, under the Open Database Licence.
- The terrain: Mapterhorn, built from open elevation models, each under its licence. In Germany these are the states' DGM1, under dl-de/by-2-0, dl-de/zero-2-0 or CC BY 4.0; elsewhere, where there is no open national model, Copernicus GLO-30. walker's Licences screen lists every one of Mapterhorn's sources, from its attribution list.
- TopPlusOpen: © BKG, under the Data Licence Germany – Attribution – 2.0. For tiles stored offline, BKG's terms ask for the year and a list of sources dated to the day of download. walker shows it as "© BKG (2026) dl-de/by-2-0, Datenquellen", with each part linked.
- Aerial photos: under each state's licence, dl-de/by-2-0, dl-de/zero-2-0, CC BY 4.0 or, for Hesse, the state's open-data terms, credited with its links while its photos are on screen.
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.