GPS-Tracks glätten mit einem Faktorgraphen

Eine Radtour von 1 h 16 min kam auf 6,98 km, nachdem ihr Track mit den Rohdaten der Satelliten bereinigt war. Ohne sie bereinigt waren es 6,19 km. Der rohe Track, direkt aus dem Chip, hatte 6,39 km. Die Bereinigung, die Rauschen herausnehmen sollte, hatte den Track länger gemacht als den rohen.

Bereinigt hat diese Tour walker, die App für Spaziergänge, Wanderungen und Radtouren, die ich für Android entwickle. Sie behält alles, was sie weiß, auf dem Handy, also muss sie dort auch jede Zahl ausrechnen, die sie zeigt. Und sie zählt alles aus dem bereinigten Track: History (den Verlauf), Stats (die Statistik), Ziele und Abzeichen. Hübsch reicht deshalb nicht, die Bereinigung muss stimmen. Sie begann als Kalman-Glätter (ein Glätter, englisch smoother, schätzt jeden Punkt aus den Messungen davor und danach) und wuchs zu einem kleinen Faktorgraphen mit einem Solver, den ich selbst geschrieben habe. Die Radtour war der erste echte Test des Graphen. Die Mathematik, die ihn geformt hat, steht in diesem Beitrag. Die Abstimmung behält walker für sich.

Warum ein roher Track lügt

Ein GPS-Punkt vom Handy rauscht, und das Rauschen summiert sich. Zittern macht aus einer geraden Linie einen längeren Zickzack. Ausreißer werfen einzelne GPS-Punkte Dutzende Meter daneben. Die GPS-Höhe liegt 5–15 m daneben, und die Höhenmeter summieren jedes Stück bergauf, also zählt auch Rauschen als Anstieg. GPS-Strecke zu lang? Warum der Track mehr misst zeigt, was das mit den Zahlen macht, die du siehst, und diese Radtour kommt darin vor.

Der schlimmste Fall, der mir begegnet ist, ist der Static Hold. Manche Chips frieren die Position ein und melden 0 m/s, während du weitergehst. Mein Testhandy, ein OnePlus 7 Pro, hat das auf einem Spaziergang getan. Der GPS-Punkt stand still und sprang dann, um aufzuholen. Eine naive Bereinigung liest das als Stopp mit anschließendem Teleport.

Erster Versuch: ein Kalman-Glätter mit Doppler

Vor dem Graphen bereinigte walker mit einem Kalman-Filter für konstante Geschwindigkeit, der vorwärts lief, und einem Rauch-Tung-Striebel-Durchlauf rückwärts, mit Ost und Nord als zwei getrennten Achsen. Außer der Position ging die Doppler-Geschwindigkeit des Chips als Messung ein, aus Tempo und Richtung jedes GPS-Punkts, und die Höhe hatte einen eigenen Glätter.

Um ihn herum standen Regeln für Ausreißer, unmögliche Sprünge und Stopps. Der Static Hold brachte ihn doppelt zu Fall. Aus dem eingefrorenen GPS-Punkt wurde ein selbstsicheres „Geschwindigkeit ist null“, und die Stopp-Regel hielt ihn fest. Der bereinigte Track zeigte einen Stopp und einen Sprung, wo ich gleichmäßig gegangen war. Der Schrittzähler wusste es besser, und der Filter konnte ihn nicht hören.

Warum ein Graph

Für ein lineares Modell mit gaußschem Rauschen liefern ein Faktorgraph und ein Kalman-Filter mit RTS-Durchlauf dieselbe Antwort. Beide lösen ein Problem der kleinsten Quadrate über den ganzen Abschnitt. Der Gewinn liegt in dem, was ein Kalman-Filter schwer ausdrücken kann. Ein robuster Verlust lässt den Schätzer selbst einen Ausreißer heruntergewichten, ohne dass vorher ein Schwellwert festgelegt werden muss. Ein nichtlinearer Faktor kann den Betrag der Geschwindigkeit einschränken, und genau den misst das Tempo aus Schritten. Ein linearer Faktor kann das nicht. Eine Unbekannte, die ein ganzer Abschnitt teilt, etwa die Schrittlänge oder Offset und Drift des Barometers, lässt sich zusammen mit dem Track lösen. Und eine Messung lässt sich abschalten, wo sie falsch ist. Ein gehaltener GPS-Punkt hat dann einfach keine.

Dellaert und Kaess' Factor Graphs for Robot Perception ist eine gute Einführung. Den Solver habe ich selbst geschrieben, und das war nur sinnvoll, weil dieser Graph eine ganz bestimmte Form hat.

Was im Graphen steckt

walker baut den Graphen für jeden Abschnitt zwischen zwei Pausen, damit nichts über eine Pause hinweg geglättet wird.

Die Zustände und die Kosten

Jeder behaltene GPS-Punkt bekommt einen horizontalen Zustand in lokalen Metern, $x_i = (e_i, n_i, v^e_i, v^n_i)$: Ost und Nord ab dem ersten GPS-Punkt des Abschnitts und die Geschwindigkeit entlang beider Richtungen. Eine eigene vertikale Kette hält Höhe und Steigrate jedes GPS-Punkts. Die beiden teilen keinen Faktor, also werden sie getrennt gelöst. Neben den Zuständen stehen die globalen Unbekannten, ein Satz pro Abschnitt: in der Ebene die Schrittlänge, für die Höhe Offset und Drift des Barometers.

Jede Messung wird zu einem Faktor, einem Term, der sagt, wie weit die Zustände von dem entfernt sind, was gemessen wurde. Der Solver sucht die Zustände und globalen Unbekannten, bei denen die Summe aller Faktoren am kleinsten ist:

$x$ steht für alle Zustände der Kette und $g$ für die globalen Unbekannten. Jeder Faktor $j$ hat ein Residuum $r_j$, die Differenz zwischen dem, was er gemessen hat, und dem, was die Zustände sagen, und eine Kovarianz $\Sigma_j$, die sagt, wie weit er danebenliegen darf. $e_j$ ist die Länge des Residuums in Einheiten seines Rauschens, also ist $e_j = 1$ eine Standardabweichung, egal was der Faktor misst. $\rho_j$ ist der Verlust des Faktors. Die meisten Faktoren nutzen einfache kleinste Quadrate, $\rho(e) = e^2$. Die Faktoren, die Ausreißer sehen, nutzen einen robusten Verlust, zu dem ich weiter unten komme. Für den Track heißt das: Kein GPS-Punkt wird beim Wort genommen. Jeder zieht an der Lösung, so stark, wie er sich sicher war, gegen alle anderen Messungen.

Bewegung zwischen Nachbarn

Zusammengehalten wird die Kette vom Bewegungsfaktor zwischen benachbarten Zuständen. Er sagt, dass du dich von einem GPS-Punkt zum nächsten mit konstanter Geschwindigkeit bewegt hast, und lässt sich jede Änderung etwas kosten:

$F_i$ trägt Zustand $i$ mit konstanter Geschwindigkeit um $\Delta t_i$ weiter, die Zeit von GPS-Punkt $i$ zu GPS-Punkt $i+1$. $I_2$ ist die 2×2-Einheitsmatrix, und $\otimes I_2$ wiederholt den Block für Ost und Nord, die unabhängig sind und ein Modell teilen. $Q_i$ ist die Kovarianz des Faktors, das $\Sigma_j$ von oben. Es ist das Lehrbuchmodell der Beschleunigung als kontinuierliches weißes Rauschen. $q$ ist die spektrale Leistungsdichte der Beschleunigung: Während $\Delta t_i$ wächst die Varianz der Geschwindigkeit um $q\,\Delta t_i$; das ist der Diagonaleintrag der Geschwindigkeit in $Q_i$. walker setzt $q$ danach, wie schnell sich das Tempo zu Fuß oder auf dem Rad ändern kann. Je größer $q$, desto freier darf sich der Track zwischen zwei GPS-Punkten biegen.

Der alte Filter modellierte dieses Rauschen als eine konstante Beschleunigung pro Intervall, mit der Varianz $\sigma_a^2$: $\sigma_a^2 \begin{bmatrix} \Delta t^4/4 & \Delta t^3/2 \\ \Delta t^3/2 & \Delta t^2 \end{bmatrix}$. Diese Matrix ist das äußere Produkt eines einzigen Vektors, sie hat also Rang 1. Ein Kalman-Filter addiert sie nur und stört sich nicht daran. Ein Graph braucht ihre Inverse. Der Block des weißen Rauschens hat die Determinante $q^2 \Delta t^4 / 12$, nie null, also lässt er sich invertieren.

Die Messungen

Fünf Arten von Messungen ziehen an den Zuständen.

Die GPS-Position ist ein robuster Faktor, gewichtet mit der Genauigkeit, die der GPS-Punkt meldet, und die liest walker vorsichtig.

Die Doppler-Geschwindigkeit ist ebenfalls ein robuster Faktor. Ihr Fehler ist aufgeteilt in einen Anteil längs und einen quer zur Bewegungsrichtung. Längs zählt die Geschwindigkeitsgenauigkeit, die der Chip meldet, quer die Genauigkeit der Richtung, und der Fehler quer wächst mit dem Tempo. Das ergibt eine volle 2×2-Kovarianz. Der alte Glätter mit seinen zwei getrennten Achsen konnte nur die Diagonale nehmen. Der Graph nimmt die ganze Matrix.

Das Tempo aus Schritten gilt für GPS-Punkte beim Gehen. Es ist Schrittlänge mal Schrittfrequenz, innerhalb einer Toleranz. Der Faktor ist nichtlinear, weil er den Betrag der Geschwindigkeit einschränkt. Die Schrittlänge ist eine globale Unbekannte mit einem lockeren Prior, also lernt der Graph sie dort, wo Doppler gut ist.

Die Nullgeschwindigkeit gilt nur für einen echten Stopp: einige langsame GPS-Punkte in Folge, während die Schritte sagen, dass du nicht gehst. Und sie gilt nur ohne Satelliten, weil die Satelliten die Geschwindigkeit selbst messen.

Die Höhe kommt vom GPS als robuster Faktor und vom Barometer, wo das Handy eines hat. Aus dem Luftdruck wird über die internationale Standardatmosphäre eine Höhe, aber ein Wetterwechsel verschiebt sie um Meter, also traut walker nur ihren Änderungen. Offset und Drift des Barometers sind globale Unbekannte, und die GPS-Höhe verankert sie.

Eine Unbekannte pro Abschnitt, die keine Messung erfasst, ändert nichts. Deshalb passt eine Form des Graphen auf jeden Track, mit oder ohne Schritte und Luftdruck.

Der gehaltene GPS-Punkt

Mit diesen Faktoren wird der Static Hold einfach. Ein GPS-Punkt, der Stillstand meldet, während der Schrittzähler Gehen meldet, gilt als gehalten. Er bekommt weder einen Positions- noch einen Doppler-Faktor, wie der vierte Zustand in Abbildung 1. Die Bewegungsfaktoren tragen den Track hindurch und verteilen den Aufholsprung über die Zeit, in der der Punkt gehalten war.

Huber statt Ausreißerregeln

Die Ausreißerregeln sind weg. An ihrer Stelle nutzen Position, Doppler und GPS-Höhe einen Huber-Verlust, der ein Residuum voll zählt, solange es klein ist, und nur noch linear, sobald es eine Schwelle überschreitet. In walkers Skalierung lautet er für eine Schwelle $k$

$e$ ist das normierte Residuum des Faktors von oben. Bis zu $k$ Standardabweichungen zählt ein Faktor voll. Darüber bleibt seine Zugkraft die eines Residuums von $k$, egal wie weit er danebenliegt. Das ist das Doppelte von Hubers üblichem Verlust, was am Ort des Minimums nichts ändert. $w(e)$ ist das Gewicht, mit dem der Solver rechnet, denn er wertet $\rho$ selbst nie aus. Für den Track heißt das: Ein Ausreißer braucht keine Regel mehr, die ihn fängt. Er zieht wie jedes Residuum an der Schwelle, und die anderen Messungen entscheiden, wo der Track verläuft.

Positionen bekommen eine Regel mehr. Eine Position weit jenseits jedes ehrlichen Fehlers bleibt ganz draußen. Diese Grenze ist der Grund, warum walkers GPS-Diagnose einen GPS-Punkt weiterhin als ausgelassen benennen kann und die alten Tests für Ausreißer und zu hohes Tempo unverändert bestehen. Ich hatte erwartet, Cauchy zu brauchen; die Tests haben nie danach verlangt.

Der Solver: Levenberg-Marquardt über einem Pfeil

Jeder Zustand ist nur mit seinen Nachbarn verbunden, dazu mit ein paar globalen Unbekannten. Diese dünne Besetzung macht den Solver billig. Für einen Abschnitt aus $n$ Zuständen hat das System für einen Schritt $\delta$ diese Form:

$A_i$ ist der Block von Zustand $i$ mit sich selbst, $N \times N$ für einen Zustand aus $N$ Zahlen. $L_i$ verbindet Zustand $i$ mit Zustand $i+1$; nur Faktoren zwischen Nachbarn schreiben hinein. $E_i$ verbindet Zustand $i$ mit den $G$ globalen Unbekannten, und $C$ ist deren $G \times G$-Block. $\delta_i$ ist der Schritt für Zustand $i$, $\delta_g$ der Schritt für die globalen Unbekannten, und die $b$ sind die rechte Seite. Alles andere ist null, und darin liegt der ganze Trick. Die Matrix ist blocktridiagonal mit einem Rand: ein Pfeil.

Der Solver eliminiert die Zustände einen nach dem anderen. Übrig bleibt ein kleines System nur in den globalen Unbekannten, ihr Schur-Komplement. Das löst er, bevor er die Zustände rückwärts zurückgewinnt. Jeder Zustand kostet ein paar kleine Cholesky-Lösungen. Nirgends entsteht eine dichte Matrix, und es gibt kein Crate für lineare Algebra. Der Solver ist von Hand geschriebenes Rust, wie fast alles in walker. Ein Abschnitt kostet $O(n\,(N + G)^3)$, linear in $n$. Eine dichte Lösung für eine Stunde mit einem GPS-Punkt pro Sekunde wäre $O\big((nN)^3\big)$: für 14.400 Unbekannte etwa 10¹² Operationen.

Um das herum arbeitet Levenberg-Marquardt, weil nicht alle Faktoren linear sind. Jede Iteration linearisiert jeden Faktor dort, wo die Zustände gerade stehen, und macht einen gedämpften Schritt. Ein Schritt, der die Kosten nicht erhöht, bleibt, und die Dämpfung lässt nach. Ein Schritt, der sie erhöht, wird verworfen und mit mehr Dämpfung wiederholt. Nocedal und Wrights Numerical Optimization beschreibt die Trust-Region-Variante, die den Rückgang der Kosten mit dem Rückgang vergleicht, den das lineare Modell vorhergesagt hat. walker fragt nur, ob die Kosten gesunken sind: die einfachste Regel, die funktioniert.

Robuste Gewichte machen die Summe von sich selbst abhängig, deshalb steckt das Ganze in iterativ neu gewichteten kleinsten Quadraten. Jede Runde setzt jedes robuste Gewicht aus seinem Residuum und löst dann mit festgehaltenen Gewichten. Die Runden wiederholen sich, bis die Gewichte sich nicht mehr ändern. Ein ausgelassener Faktor wird in der nächsten Runde trotzdem wieder angesehen. So kann ein früh verworfener GPS-Punkt zurückkommen, sobald der Track sich auf ihn zubewegt hat.

Robuste Verluste machen das Problem nichtkonvex, also kommt es auf den Startpunkt an. Der alte Kalman-Glätter liefert seitdem den Startpunkt. Seine Antwort ist eine Lösung kleinster Quadrate, und die erste Runde muss nur noch die Ausreißer herausnehmen.

Was die Tests sagten

Zuerst die Kontrolle. Mit einfachen gaußschen Verlusten reproduziert der Graph die Positionen und Höhen des alten Glätters auf einen Millimeter genau. Dann synthetische Tests:

• Durch einen Static Hold im Gehtempo läuft der Track auf 5 m genau hindurch, und die Distanz stimmt auf 5 %; ohne Schritte bleibt er ein Stopp.
• Bei einem Anstieg von 100 m mit verrauschter, systematisch verschobener GPS-Höhe liegen die gezählten Höhenmeter höchstens 10 % neben dem Wert aus den wahren Höhen, und mindestens doppelt so nah daran wie ohne Barometer.

Abbildung 3 zeigt die Idee des ersten Tests in einer Dimension.

Das sind Tests auf erfundenen Tracks, keine Ergebnisse aus dem Gelände. Mein Handy hat kein Barometer, deshalb ist dieser Teil nur mit synthetischen Hügeln und einem simulierten Barometer geprüft.

Die Radtour, die länger wurde

Später kamen die rohen GNSS-Messungen des Handys in den Graphen; ein eigener Beitrag behandelt sie. Der Zustand wuchs um Uhrenfehler und Uhrendrift des Empfängers, der Bias jedes Signals gegen GPS L1 wurde eine globale Unbekannte, und der Pfeil behielt seine Form. Auf meinem OnePlus liegt BeiDou bei −459 m, GLONASS bei +1.141 m und GPS L5 bei −2.350 m. Die exakte Methode rechnet jede Position bei jeder Auswertung von lokalen Metern in erdzentrierte Koordinaten um. Exakt gerechnet dauerte die Bereinigung einer Stunde mit Satelliten 13-mal so lange, deshalb linearisiert walker diese Umrechnung einmal pro Epoche. Das ist unbedenklich. Ein Knoten bewegt sich beim Lösen um Meter, und die Erdkrümmung macht auf 100 m weniger als einen Millimeter aus.

Dann kam die Radtour vom Anfang dieses Beitrags, der erste echte Test: 1 h 16 min aufgezeichnete GPS-Punkte, auf einer Fahrt, die länger dauerte, mit einem Stopp von über zwei Stunden. Mit Satelliten bereinigt 6,98 km. Ohne sie 6,19 km. Roh 6,39 km.

Ein Diagnosewerkzeug zerlegte die zusätzlichen 793 m. Nur 62 m davon fielen dort an, wo der Empfänger stand, also lag es nicht an den Stopps. Es lag an den Gewichten. Jede Pseudoentfernung kam mit dem eigenen σ des Chips, ein paar Meter, und galt jede Sekunde als unabhängig. Mehrwegefehler halten Sekunden bis Minuten an, also zog ein Dutzend Pseudoentfernungen pro Epoche jeden Knoten hin und her. Zwei Änderungen folgten:

• eine Untergrenze für das σ jeder Pseudoentfernung, die steigt, wenn das Signal schwächer wird;
• eine Aufweitung, sodass eine Folge von Epochen als eine unabhängige Pseudoentfernung pro Korrelationszeit von einigen zehn Sekunden zählt.

Die letzte Zeile hält außerdem einen Stopp fest, den der Chip gemeldet hat, sofern auch die gelöste Geschwindigkeit dort einen Stopp zeigt. Ohne Satelliten: 6.185 m und 78 verschobene GPS-Punkte. Aus 6,98 km wurden so 6,22 km.

Als ich jedes Satellitensystem und jedes Frequenzband dazunahm, das das Handy misst, etwa 25–30 Signale pro Epoche, kam die Falle in neuer Form zurück. Die Umgebung beugt alle Signale einer Epoche zugleich, also liegt die Position, die sie ergeben, um Meter daneben, egal wie viele Satelliten übereinstimmen. Jetzt zählen die Pseudoentfernungen einer Epoche und ihre Änderungsraten zusammen wie einige wenige unabhängige.

Beide Aufweitungen beruhen auf einer Tatsache. Information, eins durch die Varianz, addiert sich. Weite jede Pseudoentfernung einer Epoche um deren Anzahl auf, und ihre gemeinsame Information bleibt die von wenigen unabhängigen Pseudoentfernungen, egal wie viele Satelliten am Himmel stehen. Die Aufweitung über die Zeit beruht ebenfalls darauf. Die Pseudoentfernungen eines Satelliten innerhalb einer Korrelationszeit zählen zusammen als eine. Ein vollständigerer Schätzer würde die Korrelation modellieren, mit einem Gauß-Markov-Zustand pro Satellit oder einer vollen Kovarianz pro Epoche. walker weitet nur jeden Faktor auf. So bleibt jeder Faktor skalar, und der Pfeil behält seine Form.

Bewerten ohne Referenzweg

Ich habe auch aufgehört, auf die Länge hin abzustimmen. Zwei Maße kommen ohne Referenz aus. Das erste ist, wie weit die bereinigten GPS-Punkte von den kartierten Wegen in den Kartenregionen auf dem Handy liegen, als Median und als 90. Perzentil. Das zweite bereinigt den Track mehrmals und lässt dabei jedes Mal eine Gruppe von Satelliten weg. Dann bewertet es deren Pseudoentfernungen gegen die Orte, an die der Track jeden GPS-Punkt gelegt hat, und nimmt ein robustes σ des Rests. Die Karte sieht Fehler quer zum Weg. Die zurückgehaltenen Satelliten sehen Fehler entlang des Wegs.

Auf der Radtour lagen die GPS-Punkte ohne Satelliten 2,37 m (Median) und 5,98 m (p90) von den Wegen entfernt, mit allen Signalen 2,24 m und 5,34 m. Das robuste σ der zurückgehaltenen Pseudoentfernungen ging von 7,61 m auf 7,51 m zurück. Heute bereinigt walker die Tour auf 6,25 km; das über die Zeit aufsummierte Tempo des Chips ergibt 6,13 km.

Das ist ein bescheidener Gewinn. Die Satelliten kürzen vor allem die schlechten Ausläufer der Verteilung. Wo der Chip gut ist, liegt sein GPS-Punkt schon etwa so nah am Weg. Auf einer von drei kürzeren Aufzeichnungen wurde der Median etwas schlechter (von 2,63 m auf 2,87 m), während sich das p90 verbesserte. Die siegreiche Lösung der Google Smartphone Decimeter Challenge 2021 nutzte ebenfalls einen Faktorgraphen und kam auf 1,62 m, aber mit Trägerphase und mit Pseudoentfernungen, die über Referenzstationen korrigiert waren. Mein Handy liefert keine gültige Trägerphase, und walker nutzt keinen Korrekturdienst.

Ein UKF für die zugeordneten Wege

walker ordnet Tracks auf dem Handy auch Wegen aus OpenStreetMap zu, mit einem Hidden-Markov-Modell und dem Viterbi-Algorithmus, der die wahrscheinlichste Folge von Wegen wählt. Die Projektion jedes Messpunkts auf die gewählten Wege zittert, und an einer Ecke kann sie rückwärts springen. Deshalb bekommt jedes zugeordnete Teilstück einen Unscented-Kalman-Filter (UKF) entlang der zugeordneten Linie. Sein Zustand ist die Strecke entlang der Linie, das Tempo entlang der Linie und ein Versatz quer dazu. Der Versatz fängt einen Track auf, der sich auf einer Seite eines breiten Wegs hält, oder einen GPS-Bias, und geht mit der Zeit wieder auf null zurück.

Unscented ist der Filter, weil die Messung, also wo der Zustand einen Messpunkt auf die Linie setzt, an jeder Ecke abknickt. Der Filter schickt eine Handvoll Stichproben-Zustände hindurch, seine Sigma-Punkte. Punkte auf beiden Seiten einer Ecke landen auf beiden Schenkeln und sehen den Knick, wo eine Linearisierung nur einen Schenkel sähe. Aus demselben Grund läuft die Linie über ihre Enden hinaus gerade weiter. Als ich sie stattdessen begrenzt habe, landete jeder Sigma-Punkt, der über ein Ende hinausfiel, genau auf diesem Ende, und ein gerades, rauschfreies Teilstück lag 6 m daneben. Abbildung 4 zeigt beides. Danach wird das Teilstück rückwärts geglättet, und ein letzter Schritt stellt sicher, dass die Strecke nur vorwärts geht. Um eine synthetische Ecke ergibt das 1,5 m RMS gegen 3,3 m der bloßen Projektion. Die zugeordnete Linie fließt nie in den bereinigten Track zurück, sonst würde das Herunterladen einer Kartenregion deine History ändern.

Was es auf dem Handy kostet

Auf meinem Desktop, in einem Release-Build, waren 300 synthetische Spaziergänge von je einer Stunde durch den Graphen in 4,4 s bereinigt, gegen 318 ms durch den alten Glätter. Eine Stunde mit Rohdaten der Satelliten dauerte etwa 200 ms, ohne sie 20 ms.

Erst auf dem Handy zeigte es sich. Auf dem OnePlus dauerte die Bereinigung zweier Spaziergänge von 1,8 und 6,2 km mit rohen GNSS-Daten 37 s, und das bei jedem Start, weil walker jede Aktivität von Grund auf neu bereinigte. Das war ein Debug-Build, und die kleinen Matrixfunktionen des Solvers, die ihre Argumente als Wert übernehmen, brauchen Inlining. Der Debug-Build überzeichnet also die Kosten, aber einen Release-Build habe ich auf dem Handy noch nicht gemessen.

Der nächste Meilenstein ließ die Konstante in Ruhe und änderte das Muster. walker bereinigt jetzt jede Aktivität einmal und behält das Ergebnis. Was fehlt, bereinigt die App auf bis zu vier Threads neben dem Speicher-Thread, damit der Rest der App nicht darauf wartet. Weil ich zuerst gemessen habe, fand ich zwei Beschleunigungen, die das Ergebnis Bit für Bit gleich lassen, und die Radtour ging auf meinem Desktop, im Release-Build, von 2,6 s auf 1,2 s. Das ist gebaut, aber noch nicht veröffentlicht, und auf dem Handy habe ich es noch immer nicht gemessen.

Eine GPU kommt darin nicht vor. Pseudoentfernungen von etwa 2·10⁷ m brauchen Millimeter, also f64, und der Vulkan-Treiber des Handys hat keine f64-Shader.

Finge ich neu an, würde ich zwei Dinge früher tun. Ich würde gegen etwas bewerten, das die Bereinigung nie sieht, statt gegen die Distanz, die sie anzeigt. Und ich würde früh auf dem Handy messen: Der Desktop sagte ein paar hundert Millisekunden pro Stunde, das Handy 37 Sekunden.