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

Making contour lines and hillshading on the phone

How walker turns open lidar terrain into hillshading and contour lines on an Android phone: Horn's method, marching squares, Douglas–Peucker and MVT.

27 September 2026 · Malik · 15 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, made on the phone itself. How the layer looks from the walker's side is in offline maps for hiking.

Why make it on the phone

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 pack you download on request, and each download is logged.

The terrain was on the phone, so drawing the relief from it needs no extra download and no extra server. The only question was when to do the work. The map widget walker uses, walkers, takes a tile only as encoded bytes. Making a tile on the fly would mean encoding a PNG for every tile on screen and decoding it straight away. walker makes the whole layer once instead, into two tile archives beside the terrain, and after that it costs only disk space.

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\,\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.

walker's terrain for a map region takes zoom 12 (about 12 m per pixel at 51° N) from the planet file, 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 walker fetches only the region's tiles and never the whole planet. Over Germany, every state's source is its lidar terrain model, DGM1, which measures the bare ground. 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 the note in Map packs names 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 $y$ at zoom $z$ , where the world is $2^z$ tiles across and the rows count down from the north, as

\varphi = \arctan\!\left(\sinh\!\left(\pi\left(1 - \frac{2y}{2^z}\right)\right)\right)

(2)

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

\Delta = \frac{2\pi R \cos\varphi}{w \cdot 2^z}

(3)

metres wide on the ground, where $R$ is the Earth's equatorial radius and $w = 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.

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\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\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, $p$ towards the east and $q$ 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 = 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,\ \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 $\mathbf{n}$ is the normal, $\mathbf{l}$ the vector towards the light, and $p$ and $q$ the two slopes, with the exaggeration in them. $L$ 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.

Figure 2. Left: Horn's weights for

p

and

q

, before the division by

8\Delta

. Right: a made-up eight-sided pyramid seen from above, its faces rising 20 %, drawn as 40 % (

k = 2

), shaded by

L

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. Each pixel becomes one of a small palette of tones: shades of black for shadow, a few of white for light, and clear for ground close to flat, so the map shows through unchanged. The light tones matter only on the dark theme. The tiles are paletted PNG, a PNG with a small fixed set of colours, so the number of tones sets their size. Halving the shades of shadow halved the tiles, but showed bands, so I kept the full set.

The terrain is zoom 12, but hillshading goes down to zoom 8. Each lower zoom is shaded from heights averaged 2×2 from the zoom above; its pixels are twice as wide, so the slopes stay in metres per metre.

That needn't mean holding a region's heights in memory. PMTiles orders an archive along a Hilbert curve, which fills one quadrant before it moves to the next, at every scale, so a tile's four children arrive one after another, and so do its sixteen grandchildren. walker reads the zoom-12 tiles in that order, finishes a parent as soon as a tile of another parent arrives, and never holds more than one parent per zoom: about 5 MB in all.

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

\kappa = 8\,s_{\text{NW}} + 4\,s_{\text{NE}} + 2\,s_{\text{SE}} + s_{\text{SW}}

(5)

where each $s$ 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 $u$ and $v$ , of heights $h_u$ and $h_v$ , the line crosses at

t = \frac{\ell - h_u}{h_v - h_u}, \qquad P = P_u + t\,(P_v - P_u)

(6)

where $t$ is the fraction of the way from $u$ to $v$ , and $P_u$ , $P_v$ and $P$ are points in pixels. An edge is crossed only when one end is above and the other below, so $h_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:

\bar h = \tfrac14\,(h_{\text{NW}} + h_{\text{NE}} + h_{\text{SE}} + h_{\text{SW}})

(7)

If $\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.

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

P

placed by

t

. 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. 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 neighbours' heights added, so the two tiles share those heights and their lines meet exactly.

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.

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

P

beyond the end

B

, the distance to the segment is

|PB|

, larger than the distance to the endless line through

A

and

B

. When

A

and

B

coincide, as on a closed ring, it is the plain distance from

A

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 work starts by itself after a terrain download finishes. It runs on a blocking thread, off the thread that handles the downloads, which would otherwise answer nothing while it ran. Map packs shows Making topo… with a percentage, then Hillshading and contours. Deleting the map region stops it between tiles. Both archives are written aside and renamed when whole, so a stopped run leaves nothing behind.

I measured Sachsen-Anhalt on my desktop, in a release build. Its zoom-12 terrain is 1,240 tiles and 66 MB. Making the Topo layer took 43 s and wrote 63 MB of hillshading and 6 MB of contours.

The time is also why Topo is made from zoom 12 alone. Lidar covers all of Sachsen-Anhalt, so zoom 14 is there too, but it is 1.1 GB. Each zoom-12 tile holds 16 of zoom 14, so the region has at most 19,840 of them; from sample tiles I estimated about 17,000. Every tile takes about as much work as the next, so the time grows with the count:

T \approx N \cdot f \cdot \tau

(8)

where $N$ is the number of tiles, $\tau = 43\ \text{s} / 1{,}240 \approx 35$ ms is the desktop's time per tile, and $f$ is how many times slower the phone is. With $N = 17{,}000$ and a guess of $f = 3$ , that is about 1,770 s: half an hour. And the hillshading would add 65–85 % of the terrain's size again in my samples: roughly another 0.7 to 0.9 GB.

The other two layers: TopPlusOpen and aerial photos

The layer sheet offers two more layers, which are downloaded instead of made: TopPlusOpen, the official topographic map of Germany's Federal Agency for Cartography and Geodesy (BKG), and Aerial, the German states' aerial photos. Both are far too large for a whole map region (BKG's download of TopPlusOpen is a 1.6 TB cache), so both work by area. You frame an area on the map, tap Download this area, and pick the detail: 3, 1.5 or 0.75 m per pixel, each with its size. They come over WMS, a standard for map-image servers, and none of the services states terms for fetching many tiles, so walker fetches only what you asked for, one request at a time and spaced apart. A download over 2 GB is refused, and it resumes where it stopped. Fifteen states are in. Mecklenburg-Western Pomerania stamps its copyright into every 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 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 on the phone bought three things. The Topo layer is made once, from heights walker had downloaded anyway, and from then on it works offline like every other layer, with no extra download and no server to ask. The work streams: in the Hilbert order walker shades a region of 1,240 tiles while holding about 5 MB of heights at a time. And the whole map is open data, OpenStreetMap for the paths and Mapterhorn for the ground, and each is credited on the map where it shows.

Two questions remain. I haven't timed it on a phone yet, and the estimate above rests on a guess at how much slower a phone is than my desktop. And Topo stays at zoom 12, because the finer model would take about half an hour and most of a gigabyte for one state.

walker had the heights before any of this started, downloaded to put a track's heights on the ground. The Topo layer works on those heights alone, runs once when the download finishes, and keeps its result beside the terrain. A map region now carries its relief, drawn by the phone from open data, and the hill the path climbs is on the map.