Höhenlinien und Schummerung auf Android berechnen

Warum eine Wanderkarte das Gelände braucht

Eine Karte, die nur aus OpenStreetMap gezeichnet ist, zeigt jeden Weg, aber nicht den Berg, den der Weg hinaufführt. Beim Wandern fehlt damit die Hälfte: Du willst das Tal sehen, durch das du aufsteigst, und wie steil das nächste Stück wird.

walker, die App für Spaziergänge, Wanderungen und Radtouren, die ich für Android entwickle, ist in Rust geschrieben, und ihre Karte entsteht aus OpenStreetMap. Das Gelände hatte sie schon, bevor sie ein Relief zeigen konnte: Damit ein geglätteter Track seine Höhen vom Boden bekommt und nicht von dem, was das GPS geraten hat, lädt sie zu jeder Kartenregion das Gelände neben der Karte herunter (warum das für die Höhenmeter wichtig ist). In diesem Beitrag geht es um die zweite Verwendung, die ich für diese Höhen gefunden habe: eine Ebene Topo mit Schummerung und Höhenlinien, berechnet auf dem Handy selbst. Wie die Ebene unterwegs aussieht, steht in Offline-Karten zum Wandern.

Warum auf dem Handy

Naheliegend wäre es, fertige Kacheln mit Schummerung und Höhenlinien herunterzuladen. Doch die Kachelserver hinter den Kartenstilen von OpenStreetMap, also Carto, CyclOSM, OpenTopoMap und Tracestrack, verbieten alle, Kacheln in großer Zahl oder für die Offline-Nutzung herunterzuladen. Und bei walker gilt: Unterwegs wird nichts gestreamt. Jede Ebene ist ein Paket, das du auf Wunsch herunterlädst, und jeder Download wird protokolliert.

Das Gelände lag schon auf dem Handy. Ein Relief daraus braucht also weder einen weiteren Download noch einen weiteren Server. Offen war nur, wann gerechnet wird. walkers, das Karten-Widget, das walker verwendet, nimmt eine Kachel nur als kodierte Bytes an. Kacheln erst beim Anzeigen zu berechnen hieße, für jede Kachel auf dem Bildschirm ein PNG zu kodieren und es sofort wieder zu dekodieren. Stattdessen berechnet walker die ganze Ebene einmal und schreibt sie in zwei Kachelarchive neben dem Gelände. Danach kostet sie nur Speicherplatz.

Woher die Höhen kommen

Das Gelände stammt von Mapterhorn, einem offenen Projekt, das nationale und regionale Höhenmodelle zu einem Kachelsatz zusammenführt. Seine Kacheln sind Terrarium-kodierte WebP-Bilder, 512 px breit, gebündelt in PMTiles-Archiven: eine Datei planet.pmtiles für die Zoomstufen 0 bis 12 und regionale Dateien für die Zoomstufen 13 bis 17.

Terrarium verteilt eine Höhe auf die drei Farbkanäle eines Pixels. Nach der Dokumentation von Tilezen ist die Höhe in Metern

wobei red, green und blue der rote, grüne und blaue Kanal des Pixels sind, jeweils eine ganze Zahl von 0 bis 255. Rot und Grün tragen also ganze Meter, Blau Schritte von 1/256 m, und die Skala beginnt bei −32.768 m. Eine 32-Bit-Gleitkommazahl fasst das exakt, deshalb dekodiert walker in eine solche.

Für das Gelände einer Kartenregion nimmt walker Zoomstufe 12 aus der Planet-Datei (etwa 12 m pro Pixel bei 51° nördlicher Breite) und Zoomstufe 14 (etwa 3 m), wo ein feineres Modell den Boden abdeckt. PMTiles ist ein Archiv in einer einzigen Datei, das sich stückweise über HTTP-Range-Requests lesen lässt. walker holt nur die Kacheln der Region und nie den ganzen Planeten. In Deutschland stammen die Höhen jedes Bundeslands aus dessen Lidar-Geländemodell DGM1, das den nackten Boden misst. Wo es kein offenes nationales Modell gibt, nimmt Mapterhorn Copernicus GLO-30, ein Oberflächenmodell, das Baumkronen und Dächern folgt. Dort laufen die Höhenlinien im Wald über die Baumkronen, und der Hinweis unter Map packs (Kartenpakete) nennt Copernicus als Quelle. In Deutschland stellt sich die Frage nicht: Für alle sechzehn Länder gibt es Lidar-Daten.

Wie groß ein Pixel ist

Alles Weitere misst Steigungen und Längen und braucht dafür die Breite eines Pixels auf dem Boden. Auf einer Web-Mercator-Kachel hängt sie vom Breitengrad ab. Den Breitengrad $\varphi$ der Kachelzeile $y$ bei Zoomstufe $z$ gibt das OpenStreetMap-Wiki so an (die Welt ist dabei $2^z$ Kacheln breit, und die Zeilen zählen von Norden her):

Die Mercator-Projektion streckt die Karte dort um den Faktor $1/\cos\varphi$, also ist ein Pixel

Meter breit auf dem Boden, wobei $R$ der Äquatorradius der Erde ist und $w = 512$ die Breite der Kachel in Pixeln. Bei Zoomstufe 12 und 51° nördlicher Breite sind das 12,03 m, bei Zoomstufe 14 sind es 3,01 m. Innerhalb einer Kachel ändert sich der Breitengrad zu wenig, um ins Gewicht zu fallen, deshalb rechnet walker ihn einmal pro Kachel aus.

Für Topo rechnet walker das Gelände nicht auf ein anderes Raster um: Jedes Pixel des WebP ist eine Höhe, ein Pixel Schummerung und ein Gitterpunkt für die Höhenlinien.

Schummerung nach dem Horn-Verfahren

Eine Schummerung beleuchtet das Gelände, als stünde die Sonne tief im Nordwesten. Hänge, die dem Licht zugewandt sind, werden hell, abgewandte dunkel. walker nimmt die übliche Beleuchtung für Schummerungen: Licht aus der Richtung 315°, 45° über dem Horizont. Das ist auch die Voreinstellung von ArcGIS.

Die Steigung an jedem Pixel ergibt sich aus seinen acht Nachbarn, mit dem 3×3-Kern, der als Horn-Verfahren bekannt ist, nach Berthold Horns Hill shading and the reflectance map (Proceedings of the IEEE, 1981). Der Kern nimmt die Höhen der drei Pixel im Osten minus die der drei im Westen, die mittlere Zeile doppelt gewichtet, und teilt durch $8\Delta$: Die Gewichte ergeben zusammen vier, und Ost und West liegen zwei Pixelbreiten auseinander. Dann dasselbe von Norden nach Süden. Das ergibt zwei Steigungen, $p$ nach Osten und $q$ nach Norden, beide in Metern pro Meter. Warum Horns Kern? Zevenbergen und Thorne (1987) nehmen für die Steigung nur die vier direkten Nachbarn. Horns Kern zählt die Diagonalen mit und glättet so einzelne verrauschte Pixel, und ArcGIS verwendet ihn für seine Schummerung. Am Rand einer Kachel, wo die Nachbarn einer Seite fehlen, weicht walker auf eine einseitige Differenz aus.

Maßstabsgetreu ist ein Hügel auf einer 512-px-Kachel im Flachland kaum zu sehen. walker zeichnet deshalb jede Steigung doppelt so steil, wie sie ist, mit einer Überhöhung von $k = 2$: Eine Steigung von 10 % wird wie 20 % schattiert.

Aus den beiden Steigungen folgt die Normale der Fläche, der Pfeil, der senkrecht aus dem Boden ragt. Das Licht ist ebenfalls ein Einheitsvektor: Er zeigt zu gleichen Teilen nach Westen und nach Norden, dazu nach oben. Wie hell das Pixel ist, hängt vom Kosinus des Winkels zwischen beiden ab:

Dabei ist $\mathbf{n}$ die Normale, $\mathbf{l}$ der Vektor zum Licht, und $p$ und $q$ sind die beiden Steigungen, mit der Überhöhung darin. $L$ reicht von 0, abgewandt oder im eigenen Schatten, bis 1, dem Licht genau zugewandt. Flaches Gelände bekommt den Sinus der Lichthöhe, etwa 0,707.

Eine Schummerung liegt über der Karte, und die Karte muss darunter lesbar bleiben. Jedes Pixel wird zu einem Ton aus einer kleinen Palette: Schwarztöne für Schatten, ein paar Weißtöne für Licht und durchsichtig für fast flaches Gelände, damit die Karte dort unverändert durchscheint. Die hellen Töne zählen nur im dunklen Design. Die Kacheln sind PNGs mit Palette, also mit einer kleinen, festen Menge an Farben, und die Zahl der Töne bestimmt ihre Größe. Mit halb so vielen Schattentönen wurden die Kacheln halb so groß, zeigten aber Stufen, deshalb habe ich den vollen Satz behalten.

Das Gelände liegt in Zoomstufe 12 vor, die Schummerung reicht aber bis Zoomstufe 8 hinunter. Jede niedrigere Zoomstufe wird aus Höhen schattiert, die aus der Stufe darüber je 2×2 gemittelt sind. Ihre Pixel sind doppelt so breit, und so bleiben die Steigungen in Metern pro Meter.

Dafür muss walker nicht die Höhen einer ganzen Region im Speicher halten. PMTiles ordnet ein Archiv entlang einer Hilbert-Kurve, die einen Quadranten füllt, bevor sie zum nächsten geht, und das in jedem Maßstab. Die vier Kinder einer Kachel kommen so direkt nacheinander, ebenso ihre sechzehn Enkel. walker liest die Kacheln der Zoomstufe 12 in dieser Reihenfolge, schließt eine Elternkachel ab, sobald eine Kachel einer anderen kommt, und hält nie mehr als eine Elternkachel pro Zoomstufe: zusammen etwa 5 MB.

Höhenlinien mit Marching Squares

Die Höhenlinien entstehen mit Marching Squares, dem zweidimensionalen Verwandten von Marching Cubes (Lorensen und Cline, 1987). Das Höhengitter wird in Zellen aus vier Ecken zerlegt, die ein Pixel auseinanderliegen. Jede Höhenstufe zwischen der niedrigsten und der höchsten Ecke einer Zelle schneidet sie. Für eine Höhenstufe $\ell$ liegt jede Ecke darüber oder darunter. Die Ecken, im Uhrzeigersinn ab Nordwesten als Bits gelesen, ergeben den Fall

wobei jedes $s$ gleich 1 ist, wenn diese Ecke auf oder über $\ell$ liegt, und sonst 0. Das sind 16 Fälle. In den Fällen 0 und 15 gibt es keine Linie. Jeder andere Fall sagt, welche Kanten der Zelle die Linie schneidet, und lineare Interpolation setzt den Schnittpunkt auf der Kante. Zwischen den beiden Ecken $u$ und $v$ einer Kante, mit den Höhen $h_u$ und $h_v$, liegt er bei

wobei $t$ der Anteil des Wegs von $u$ nach $v$ ist und $P_u$, $P_v$ und $P$ Punkte in Pixeln sind. Eine Kante wird nur geschnitten, wenn ein Ende darüber und das andere darunter liegt. Dann ist $h_v \ne h_u$, und die Division ist sicher.

Zwei Fälle sind mehrdeutig: 5 und 10, bei denen zwei gegenüberliegende Ecken darüber liegen und die anderen beiden darunter. Das ist ein Sattel, und die Linie könnte auf zwei Arten durch die Zelle laufen (Abbildung 3). walker entscheidet nach der Mitte der Zelle und nimmt dafür den Mittelwert ihrer Ecken:

Liegt $\bar h$ auf derselben Seite von $\ell$ wie die Nordwestecke, verbinden sich die Nordwest- und die Südostecke durch die Mitte. Sonst schneiden die Linien diese beiden Ecken ab.

Danach müssen die Stücke zu Linien verbunden werden. walker benennt jeden Schnittpunkt nach der Kante, auf der er liegt. Zwei benachbarte Zellen geben einer gemeinsamen Kante so denselben Namen, berechnen ihren Schnittpunkt aus denselben zwei Höhen und treffen sich in genau einem Punkt. Bis auf das Sortieren der Enden ist das Aneinanderhängen dann ein einziger Durchlauf, erst die offenen Linien, danach die geschlossenen Ringe.

walker zeichnet alle 10 m eine Linie und alle 50 m eine Zähllinie, die ihre Höhe als Beschriftung trägt. Im Ebenen-Menü, das der Ebenen-Knopf der Karte öffnet, hat Topo zwei Schalter, Hillshading (Schummerung) und Contour lines (Höhenlinien), und unter dem zweiten steht genau das: every 10 m, labelled every 50 m (alle 10 m, alle 50 m beschriftet).

Knifflig ist der Kachelrand. Einzeln verfolgt, würde jede Kachel eine Zelle vor ihrer Nachbarkachel aufhören, und die Linien hätten Lücken. walker verfolgt jede Kachel mit einer zusätzlichen Spalte und Zeile aus den Höhen der Nachbarkacheln. Zwei Kacheln teilen sich so diese Höhen, und ihre Linien treffen sich genau.

Weniger Punkte mit Douglas-Peucker

Marching Squares liefert einen Punkt in jeder Zelle, durch die eine Linie läuft, weit mehr, als eine Zeichnung braucht. walker vereinfacht jede Linie mit dem Algorithmus von Douglas und Peucker (Cartographica, 1973). Er behält die beiden Enden, sucht den Punkt, der am weitesten von der geraden Verbindung zwischen ihnen entfernt ist, und behält ihn, wenn er weiter weg liegt als eine Toleranz. Dann wiederholt er das für jede Hälfte.

Eine Änderung habe ich bewusst gemacht. Der Algorithmus, wie er meist aufgeschrieben wird, misst den Abstand eines Punkts zur unendlichen Geraden durch die beiden Enden. walker misst ihn zur Strecke zwischen ihnen. Jenseits eines Endes ist dieser Abstand der größere, also behält walker womöglich einen Punkt, den die übliche Fassung verwerfen würde, aber nie umgekehrt. Das regelt auch die geschlossenen Ringe, deren Enden zusammenfallen: Dort wird der Abstand zum einfachen Abstand vom Anfangspunkt, ohne Sonderfall im Code. Winzige geschlossene Ringe gelten danach als Rauschen im Gelände, nicht als Kuppen, und fallen weg.

Vektorkacheln schreiben

walker schreibt die Höhenlinien als Mapbox Vector Tiles, dem Format seiner OpenStreetMap-Karten. So zeichnet derselbe Renderer beides, mit einem eigenen Stil für die Höhenlinien. Einen MVT-Encoder hatte walker bis dahin nur in seinen Tests; für die Höhenlinien habe ich einen richtigen daraus gemacht. Jede Linie trägt ihre Höhe und die Angabe, ob sie eine Zähllinie ist, weil der Kartenstil keinen Divisionsrest berechnen kann.

Was es kostet

Die Arbeit beginnt von selbst, sobald ein Gelände-Download fertig ist. Sie läuft auf einem blockierenden Thread, getrennt von dem Thread, der die Downloads verwaltet. Der würde sonst nichts mehr beantworten, solange sie läuft. Map packs zeigt Making topo… (Topo wird erstellt) mit einem Prozentwert, danach Hillshading and contours (Schummerung und Höhenlinien). Löschst du die Kartenregion, hört die Arbeit zwischen zwei Kacheln auf. Beide Archive werden unter einem anderen Namen geschrieben und erst umbenannt, wenn sie vollständig sind, damit ein abgebrochener Lauf nichts hinterlässt.

Ich habe Sachsen-Anhalt auf meinem Desktop-Rechner gemessen, mit einem Release-Build. Sein Gelände in Zoomstufe 12 umfasst 1.240 Kacheln und 66 MB. Die Topo-Ebene zu berechnen dauerte 43 s und schrieb 63 MB Schummerung und 6 MB Höhenlinien.

Die Rechenzeit ist auch der Grund, warum Topo nur aus Zoomstufe 12 entsteht. Lidar deckt ganz Sachsen-Anhalt ab, also gibt es dort auch Zoomstufe 14, aber sie ist 1,1 GB groß. Jede Kachel der Zoomstufe 12 enthält 16 Kacheln der Zoomstufe 14, die Region hat also höchstens 19.840 davon; aus Stichproben habe ich etwa 17.000 geschätzt. Jede Kachel kostet ungefähr so viel Arbeit wie die nächste, und so wächst die Zeit mit der Anzahl:

Dabei ist $N$ die Zahl der Kacheln, $\tau = 43\ \text{s} / 1.240 \approx 35$ ms die Zeit des Desktop-Rechners pro Kachel und $f$ der Faktor, um den das Handy langsamer ist. Mit $N = 17.000$ und geschätzt $f = 3$ sind das etwa 1.770 s, eine halbe Stunde. Die Schummerung käme in meinen Stichproben mit 65–85 % der Geländegröße noch dazu: grob weitere 0,7 bis 0,9 GB.

Die anderen beiden Ebenen: TopPlusOpen und Luftbilder

Das Ebenen-Menü hat zwei weitere Ebenen, die heruntergeladen statt berechnet werden: TopPlusOpen, die amtliche topografische Karte des Bundesamts für Kartographie und Geodäsie (BKG), und Aerial, die Luftbilder der Bundesländer. Beide sind für eine ganze Kartenregion viel zu groß (der Download von TopPlusOpen beim BKG ist ein Cache von 1,6 TB), also arbeiten beide mit Gebieten. Du rahmst ein Gebiet auf der Karte ein, tippst auf Download this area (dieses Gebiet herunterladen) und wählst die Detailstufe: 3 m, 1,5 m oder 0,75 m pro Pixel, jeweils mit der Größe des Downloads. Die Bilder kommen über WMS, einen Standard für Server, die Kartenbilder ausliefern, und keiner der Dienste nennt Bedingungen dafür, viele Kacheln abzurufen. walker holt deshalb nur, was du angefordert hast, eine Anfrage nach der anderen und mit Pausen dazwischen. Einen Download über 2 GB lehnt die App ab, und ein unterbrochener Download macht dort weiter, wo er aufgehört hat. Fünfzehn Länder sind dabei. Mecklenburg-Vorpommern stempelt sein Copyright in jedes Bild und bleibt darum außen vor.

Quellenangaben

Die Ebenen beruhen auf offenen Daten anderer, und walker nennt jede Quelle auf der Karte, solange ihre Daten zu sehen sind. Tippst du darauf, siehst du die Links.

• Die Karte: © OpenStreetMap-Mitwirkende, unter der Open Database License.
• Das Gelände: Mapterhorn, aufgebaut aus offenen Höhenmodellen, jedes unter seiner Lizenz. In Deutschland sind das die DGM1 der Länder, unter dl-de/by-2-0, dl-de/zero-2-0 oder CC BY 4.0; anderswo, wo es kein offenes nationales Modell gibt, Copernicus GLO-30. Der Bildschirm Licences (Lizenzen) in walker listet jede Quelle von Mapterhorn auf, aus dessen Attributionsliste.
• TopPlusOpen: © BKG, unter der „Datenlizenz Deutschland – Namensnennung – Version 2.0“. Für offline gespeicherte Kacheln verlangen die Nutzungsbedingungen des BKG das Jahr des letzten Datenbezugs und eine Liste der Datenquellen mit dem Datum der Speicherung. walker zeigt das als „© BKG (2026) dl-de/by-2-0, Datenquellen“, jeder Teil verlinkt.
• Luftbilder: unter der Lizenz des jeweiligen Landes, dl-de/by-2-0, dl-de/zero-2-0, CC BY 4.0 oder, für Hessen, den Open-Data-Bedingungen des Landes. walker nennt jedes Land mit seinen Links, solange seine Luftbilder zu sehen sind.

Was es gebracht hat

Das Relief auf dem Handy zu berechnen, hat dreierlei gebracht. Die Topo-Ebene entsteht einmal, aus Höhen, die walker ohnehin heruntergeladen hatte, und funktioniert danach offline wie jede andere Ebene, ohne weiteren Download und ohne Server, den die App fragen müsste. Die Arbeit läuft Stück für Stück durch: In der Hilbert-Reihenfolge schattiert walker eine Region aus 1.240 Kacheln und hält dabei jeweils nur etwa 5 MB Höhen. Und die ganze Karte besteht aus offenen Daten, OpenStreetMap für die Wege und Mapterhorn für den Boden, und jede Quelle steht dort auf der Karte, wo ihre Daten zu sehen sind.

Zwei Fragen bleiben offen. Auf einem Handy habe ich es noch nicht gemessen, und die Schätzung oben beruht auf einer Vermutung, wie viel langsamer ein Handy als mein Desktop-Rechner ist. Und Topo bleibt bei Zoomstufe 12, weil das feinere Modell für ein Bundesland etwa eine halbe Stunde und den größten Teil eines Gigabytes kosten würde.

Die Höhen lagen auf dem Handy, bevor all das begann: heruntergeladen, damit ein Track seine Höhen vom Boden bekommt. Die Topo-Ebene arbeitet nur mit diesen Höhen, läuft einmal, wenn der Download fertig ist, und legt ihr Ergebnis neben das Gelände. Eine Kartenregion bringt jetzt ihr Relief mit, vom Handy aus offenen Daten gezeichnet, und der Berg, den der Weg hinaufführt, steht auf der Karte.