So hat Mapsake seinen Offline-Reise-Geographischen-Daten-Pool erstellt.

Ein Koordinatenpaar ist noch kein Ort.

Ein Reisefoto kann eine Längengrad- und Breitengradangabe mit beeindruckender Genauigkeit enthalten. Diese beiden Zahlen geben jedoch nicht an, ob sich die Kamera in Japan, Präfektur Kyoto, Kyoto oder am Kansai International Airport auf dem Heimweg befand. Mapsake benötigt diese Hierarchie, bevor ein Punkt zu einem nützlichen Reiseeintrag werden kann.

Die Komponente, die diese Fragen beantwortet, ist ein Geodatenverzeichnis: ein strukturierter Verzeichnisdienst für benannte geografische Orte. Mapsake bündelt sein Geodatenverzeichnis in der App, zusammen mit den Begrenzungslinien, die zum Zeichnen und Testen von Ländern und Regionen erster Ordnung verwendet werden. Suche, manuelle Markierung, Fotoimport, Ortsgeschichten, Passport-Statistiken, Erfolge und sogar einige Ansichten von Freunden hängen davon ab.

Es wäre einfacher gewesen, jede Koordinate an einen Web-Geocoder zu senden. Dies hätte auch einen großen Fotoimport verlangsamt, ihn netzwerkabhängiger gemacht, die Reproduzierbarkeit erschwert und die Privatsphäre beeinträchtigt. Der Offline-Ansatz erforderte mehr anfängliche Entwicklungsarbeit, gab Mapsake aber ein stabiles geografisches Vokabular, das auf einem Flugzeug, zu Hause und Jahre nach einer Änderung des Quelldatensatzes gleich funktioniert.

Dies ist die Geschichte davon, wie diese Ebene aufgebaut wurde, wo Punkte und Linien voneinander abweichen und warum „nächste Stadt“ nur der Anfang einer korrekten Antwort ist.

Vier offene Datensätze, vier verschiedene Jobs

Keine einzelne Quelle enthält alles, was Mapsake benötigt, daher kombiniert der Build-Prozess vier Arten von offenen Daten:

• GeoNames bietet Länder, administrative Regionen erster Ordnung, bewohnte Orte, stabile Identifikatoren, alternative Namen, Koordinaten und Bevölkerungszahlen.
• Unsere Flughäfen bietet Flughäfen, IATA- und ICAO-Codes, Namen, Gemeinden und Koordinaten.
• Natural Earth bietet die Geometrie der Landesgrenzen (admin-1) sowie nützliche Kartenelemente.
• Eine kleine, Mapsake-eigene Ebene speichert Produktentscheidungen wie unterstützte Länder, Aliase und Korrekturen, die nicht sicher aus einer generischen Quelle abgeleitet werden können.

Jede Quelle ist gut in etwas anderem. GeoNames weiß, dass eine Stadt zu einer Region und einem Land gehört, aber eine Stadtkoordinate ist ein Punkt, keine Grenze. Natural Earth weiß, wo ein Polygon gezeichnet ist, aber seine Feature-IDs stimmen nicht immer sauber mit GeoNames überein. OurAirports weiß, dass KLAX und LAX sich auf denselben Flughafen beziehen, aber es ist keine Hierarchie aller Orte rund um den Flughafen.

Das Build-Skript lädt die Quelldateien herunter und speichert sie zwischen, normalisiert sie, validiert Beziehungen und erzeugt zwei kompilierte Artefakte: eine schreibgeschützte SQLite-Datenbank und vereinfachte GeoJSON-Geometrien. Die App liefert diese Ergebnisse. Sie lädt keine weltweite Datenbank beim ersten Start herunter und ist nicht auf die Verfügbarkeit der Quellseiten während einer Reise angewiesen.

Das Generieren von Artefakten ermöglicht auch eine reproduzierbare Version. Eine ausgelieferte Version hat eine bekannte geografische Welt. Das Aktualisieren des Quellcodes ist eine absichtliche Codeänderung, die getestet und überprüft werden kann, und keine unsichtbare serverseitige Änderung, die die Karte eines Benutzers über Nacht verändert.

Eine absichtlich einfache SQLite-Datenbank.

Der erste Gazetteer enthielt 252 Länder, 3,861 Regionen, 33,744 Städte und 4,564 Flughäfen in etwa 14 MB. Er verwendete die von der Betriebssystembibliothek bereitgestellte SQLite-Bibliothek und eine kleine lokale Wrapper-Schicht anstelle eines größeren Datenbank-Frameworks.

Das Schema ist absichtlich direkt. Kontinente enthalten Länder. Länder enthalten Regionen. Regionen enthalten Städte. Flughäfen enthalten Ländercodes und Koordinaten. Stabile Quellidentifikatoren werden als die Identifikatoren gespeichert, die mit einem Mapsake-Eintrag verknüpft sind: ISO alpha-2 für ein Land, ein GeoNames-Admin-Code für eine Region, eine GeoNames-ID für eine Stadt und ein IATA-Code für einen Flughafen.

Mapsake: Normalisiert auch den für Menschen lesbaren Namen und die Herkunft in jeden gespeicherten Eintrag. Diese Duplizierung ist nützlich. Ein persönlicher Reisebericht sollte lesbar bleiben, wenn ein späteres Verzeichnis einen Ort umbenennt, einen Eintrag entfernt oder während eines Exports nicht verfügbar ist. Der Identifikator dient dem Abgleich; der Schnappschuss speichert die Benutzerdaten selbstständig.

SQLite eignet sich gut für diesen Anwendungsfall, da die Datenbank einmal erstellt und viele Male abgefragt wird. Sie unterstützt Indizes, Transaktionen während des Builds und die Volltextsuche ohne einen separaten Dienstprozess. Die App öffnet die eingebundene Datei nur zum Lesen, sodass es kein Migrationsrisiko für die Referenzdaten gibt und die Gefahr, dass ein unterbrochener Schreibvorgang sie beschädigt, ausgeschlossen ist.

Die Suche ist mehr als nur 'enthält(Text)'

Die manuelle Markierung beginnt mit einem einzigen Suchfeld, das Kontinente, Länder, Regionen, Städte und Flughäfen abdeckt. Eine Suche nach "san" sollte sinnvolle Städte vor obskuren Einträgen finden; "LAX" sollte den Flughafen finden; und ein Name, der ohne seine diakritischen Zeichen eingegeben wird, sollte dennoch funktionieren.

Das Build-Skript erstellt eine Tabelle namens FTS5 mit Anzeigenamen, ausgewählten alternativen Namen, Codes, Abstammung, Koordinaten, Art und einem Wichtigkeitswert. Der Unicode-Tokenizer entfernt diakritische Zeichen für den Abgleich. Während der Abfrage normalisiert Mapsake Groß- und Kleinschreibung und Diakritika, entfernt Zeichen, die zu einer vollständigen Textsyntax werden könnten, fügt jedem Token eine Präfixsuche hinzu und ordnet exakte Namen vor Präfixen und allgemeinen Übereinstimmungen ein.

Die Wichtigkeit löst die verbleibenden Gleichstände auf. Kontinente und Länder sollten nicht unter ähnlich benannten Dörfern verschwinden. Die Bevölkerungszahl einer Stadt gibt wichtigen Orten eine sinnvolle Gewichtung. Große Flughäfen werden gegenüber kleinen Flughäfen gewichtet, wenn der Textabgleich ansonsten vergleichbar ist.

Alternative Namen sind absichtlich begrenzt. GeoNames kann eine sehr lange mehrsprachige Liste für einen beliebten Ort bereitstellen. Das Kopieren jeder Schreibweise in den Geräteindex würde Rauschen und Größe hinzufügen. Der Builder verwendet eine begrenzte, de-duplizierte Menge nützlicher Varianten und speichert den ursprünglichen Anzeigenamen separat von seiner Suchformularversion.

Die Suchergebnisse zeigen das gleiche GazetteerPlace-Modell an, das auch für die hierarchische Navigation verwendet wird. Ein Benutzer kann direkt suchen oder Kontinent, Land, Region und Stadt durchsuchen, ohne zwei geografische Systeme zu erstellen, die möglicherweise nicht übereinstimmen.

Linien beantworten eine andere Frage als Punkte.

Der früheste Foto-Resolver wählte die nächstgelegene Stadt und übernahm das Land und die Region dieser Stadt. In dicht besiedelten Gebieten sieht dies oft perfekt aus. In der Nähe einer Grenze kann es falsch sein, was schwer zu bemerken ist.

Stellen Sie sich ein Foto vor, das direkt in Montana aufgenommen wurde, während der nächstgelegene bewohnte Ort in North Dakota liegt. Die Berechnung des nächstgelegenen Ortes funktioniert korrekt, aber das Ergebnis ist nicht der Verwaltungsort, an dem das Foto aufgenommen wurde. Das gleiche Problem tritt an internationalen Grenzen, in der Nähe von Enklaven und über Wasser auf, wo eine spärliche Küstenlinie keine nahegelegenen bewohnten Orte hat.

Geometriedaten geben die Enthaltenheit und nicht die Nähe an. Mapsake decodiert die Natural Earth-Länder- und Admin-1-Polygone, prüft, welche Ringe die Koordinate enthalten, und verwendet dieses Ergebnis, um die Zuweisung von Land und Region zu schützen. Es kann dann die nächstgelegene Stadt innerhalb des Landes oder der Region des Polygons suchen.

Dies schafft eine nützliche Arbeitsteilung:

1. Die Polygon-Eigenschaft legt den Verwaltungsbereich fest.
2. Die Hierarchie des Gazetters liefert stabile IDs und Namen.
3. Eine eingeschränkte Suche nach der nächstgelegenen Stadt liefert eine nützliche Ortsangabe, ohne die Grenze zu überschreiten, die gerade festgelegt wurde.
4. Eine Überprüfung auf nahegelegene Flughäfen fügt einen Flughafen nur innerhalb einer bewusst festgelegten, geringen Entfernung hinzu.

Weder die Linien-Daten noch das Ortsverzeichnis sind für sich genommen ausreichend. Gemeinsam verwandeln sie eine Koordinate in eine nachvollziehbare Kette.

Die admin-1-Überprüfung hat systemische Diskrepanzen aufgedeckt.

Länderpolygone und Regionspolygone stammen aus verschiedenen Natural Earth-Layern, und die Identifikatoren der Regionslayer stimmen nicht immer mit GeoNames überein. Einige Fehler waren offensichtlich, während andere plausible, aber falsche Ergebnisse lieferten.

Bei einer frühen Konvertierungstabelle wurde Quebec die Geometrie für New Brunswick zugewiesen. Andere Funktionen fehlten einen Code, enthielten einen Code aus einem benachbarten System oder repräsentierten eine Verwaltungseinheit anders als im Verzeichnis. Ein visueller Blick auf die Weltkarte konnte nicht zuverlässig alle diese Fehler finden.

Der Ersatzmechanismus behandelt Städte wie eine Orakelquelle. Für jedes Kandidatenpolygon fragt er, welche Regionen aus dem Gazetteer tatsächlich Städte enthalten, die innerhalb des Polygons liegen. Bestehende Natural Earth-Daten werden validiert, anstatt blind vertraut zu werden. Features, die die Validierung nicht bestehen, können räumlich neu zugeordnet, aufgeteilt oder ausgeschlossen werden. Die generierte Ausgabe verwendet dann die exakten Regions-IDs, die bereits in SQLite vorhanden sind.

Dies ist eine praktische Form des Cross-Dataset-Testens. Ein Polygon, das als Region beansprucht wird, sollte eine überzeugende Stichprobe von Städten enthalten, die dieselbe Region beanspruchen. Wenn die beiden Quellen nicht übereinstimmen, erzeugt das System einen Beweis anstelle von stillschweigendem Auswählen des Wertes, der zuerst geladen wurde.

Derselbe Audit ergab Sonderfälle, wie z. B. bewohnte Abhängigkeiten, die in die Geometrie eines übergeordneten Landes integriert sind. Mapsake behebt eine kleine Anzahl dieser Fälle, sodass ein Foto dem Land zugeordnet werden kann, das auch der Gazetteer und die Länderzähleinstellungen verstehen.

Schärfere Linien, ohne die Welt in Originalgröße zu übertragen.

Die erste Version verwendete Natural Earths 1:110 Millionen Länderkarte. Sie war kompakt und schnell, aber die Küstenlinien wurden sichtbar ungenau, als Mapsake detailliertere Karten, Ortsgeschichten und regionale Ansichten hinzufügte.

Die Karte wurde später in die 1:10-Millionen-Ebene verschoben. Diese Quelle ist viel detaillierter, sodass die Bündelung und das unveränderte Rendern zu einer Erhöhung des Speicherplatzes, der Dekodierzeit, der Overlay-Konstruktion und der Farbänderungsarbeiten geführt hätten. Die Build-Pipeline vereinfacht jeden Ring mit Douglas-Peucker mit einer Toleranz von etwa 0.004 Grad und rundet dann die Koordinaten auf eine stabile Präzision.

Die resultierende Länderdatei hat eine Größe von etwa 6.5 MB. Sie behält nützliche Küstendetails bei den Zoomstufen bei, die Mapsake anzeigt, während sie Eckpunkte entfernt, die effektiv auf denselben Pixeln landen würden. Die Admin-1-Geometrie durchläuft einen ähnlichen Validierungs- und Vereinfachungsprozess.

Vereinfachung hat eine Korrekteinschränkung: Ein kleineres Polygon muss weiterhin die gleichen Entscheidungen für tatsächliche Fotokoordinaten treffen. Spätere Benchmark-Tests platzieren absichtlich Punkte um die Ränder und vergleichen optimiertes Hit-Testing mit einer unveränderten Referenz. Schnellere Linien sind nur dann nützlich, wenn sie weiterhin die gleiche Frage der Enthaltenheit beantworten.

Erweiterung von 34,000 zu 234,000 Städten.

Die erste Datenbank verwendete GeoNames-Städte mit einer Bevölkerung von mehr als 15,000. Das hielt das Paket klein, ließ aber Reisen in ländliche Gebiete, kleine Inseln, Wanderstädte und viele Wohnorte mit einer unnötig weit entfernten Bezeichnung.

Mapsake hat später GeoNames übernommen. Städte500, und umfasst bewohnte Orte mit einer Einwohnerzahl von etwa 500 oder mehr sowie Verwaltungssitze. Die Tabelle mit Städten wurde um das Siebenfache auf etwa 234,000 Einträge erweitert, und die Datenbank wuchs von etwa 14 MB auf etwa 69 MB.

Dieser Tausch wurde nach dem Entfernen des App Clips durchgeführt. Die Download-Obergrenze des Clips war der stärkste Grund, um die Datenbank zu beschränken. Nachdem die Haupt-App der einzige Konsument war, war eine bessere Abdeckung wertvoller als die Aufrechterhaltung einer künstlichen Begrenzung für kleine Städte.

Der Volltextindex ist weiterhin selektiv bei alternativen Namen für kleinere Orte, und die Regionssuche begrenzt, was angezeigt wird. Die Daten können umfassend sein, ohne dass jede Ansicht die gesamte Tabelle darstellen muss.

Die Abdeckung ist am wichtigsten, wo ein Netzwerk-Geocoder am wenigsten zuverlässig wäre. Eine kleine Stadt auf einer abgelegenen Reise sollte nicht als Stadt fälschlicherweise als eine Stadt in Stunden Entfernung gekennzeichnet werden, nur weil das kompakte Dataset sie ausgelassen hat.

Die Suche nach der nächstgelegenen Stadt wurde zu einem gemeinsamen Leistungsproblem.

Die ursprüngliche Abfrage nach der nächstgelegenen Stadt erweiterte eine Längen- und Breitengradbox, forderte von SQLite eine gewichtete Distanzberechnung für jeden Kandidaten, erstellte eine temporäre Sortierung und gab die nächstgelegene Zeile zurück. Dies war leicht verständlich und ausreichend genau, aber eine 82,000-Foto-Bibliothek verwandelte einen geringen Kostenfaktor pro Abfrage in Sekunden wiederholter Arbeit während des Imports, der Erinnerungen, der Kartenerstellung und von Constellations.

Die erste Verbesserung fügte eine enge 0.4-Grad-Suche hinzu, bevor breitere Optionen verwendet wurden. Orte mit hoher Dichte fanden normalerweise eine Stadt aus einem viel kleineren Kandidatensatz. Memoization und ein persistierter geografischer Zellen-Cache verhinderten, dass nahegelegene Fotos die gleiche Arbeit wiederholten.

Die größere Verbesserung lädt die numerischen Koordinaten der 234,000-Städte in einen latituden-sortierten In-Memory-Index. Eine binäre Suche findet den Abschnitt innerhalb des aktuellen Breitengrads, eine begrenzte Schleife prüft die Längengrade und die gewichtete Entfernung, und nur die gewinnende Zeile wird aus SQLite abgerufen. Ein kleiner Cache für Datensätze hält wiederholte Gewinner kostengünstig.

Das Verhalten der automatischen Anpassung hat sich nicht geändert. Die optimierte Funktion wählt weiterhin die nächstgelegene Stadt innerhalb des ersten nicht-leeren Suchbereichs aus, einschließlich einer deterministischen Tie-Break-Regel. Eine Benchmark-Version des alten SQL-Pfads überprüft Hunderte von koordinatenbasierten Grenzwerten auf exakte ID-Übereinstimmung.

Im Simulator reduzierte sich die mittlere Zeit für die Bestimmung der nächstgelegenen Stadt von 2.11 Sekunden auf 5.2 Millisekunden. Bei einem physischen iPhone-Gerät sank die Zeit von 3.06 Sekunden auf 6.35 Millisekunden. Diese Verbesserungen ermöglichten mehrere Funktionen, da das Geodatenregister eine gemeinsame Infrastruktur und keine private Implementierungsdetail der Importoberfläche ist.

Überlappende Polygone haben einen Fehler in der Korrektheit aufgedeckt.

Der Mechanismus zur Leistungsüberprüfung hat einen Fehler aufgedeckt, der vor der Optimierung bestand. Einige admin-1 Polygone überlappen sich absichtlich, insbesondere Regionen von Hauptstädten innerhalb einer umliegenden Region. Berlin und Brandenburg, Seoul und Gyeonggi sowie Kiew und seine Oblast sind Beispiele.

Der ursprüngliche Treffer-Test akzeptierte das zuerst in einem Swift-Dictionary gefundene übereinstimmende Polygon. Die Iterationsreihenfolge eines Dictionaries kann sich zwischen Prozessen ändern, sodass dieselbe Koordinate nach dem Neustart der App zu einer anderen Region gehören kann.

Mapsake sortiert überlappende Kandidaten nach Polygonfläche und lässt das kleinste, spezifischste Merkmal gewinnen. Die Referenzimplementierung folgt derselben Regel. Eine 82,000-Foto-Referenz muss keine Unterschiede zwischen den Kalt- und Warm-Derivationspfaden aufweisen, bevor eine Geometrieeoptimierung akzeptiert wird.

Dieser Fehler ist eine gute Erinnerung daran, dass "innerhalb eines Polygons" nicht immer eine Ja-oder-Nein-Frage ist. Geografische Daten enthalten Enklaven, verschachtelte Hauptstädte, Antimeridian-Übergänge, Multipolygone, Löcher, umstrittene Grenzen und Quellkonventionen. Eine deterministische Richtlinie ist genauso wichtig wie der Point-in-Polygon-Algorithmus.

Offline ist eine Datenschutzfunktion und eine Produktfunktion.

Der Foto-Import von Mapsake kann eine große Bibliothek verarbeiten, ohne die Koordinaten an einen Drittanbieter-Geocoding-Dienst zu senden. Dies schützt sensible Reise- und Heimlstandorte, vermeidet eine Preisgestaltung pro Anfrage, verhindert Drosselung und macht den Fortschritt vorhersehbar.

Es sorgt auch für eine kohärente Bearbeitung. Manuelle Suche, Fotoimport, Passport-Karten, Erfolge, Freunde-Schnappschüsse, Stempel-Matching und Ortsgeschichten sprechen die gleiche Sprache, da sie die gleichen stabilen Orts-IDs verwenden. Ein Flughafen, der aus einem Flugprotokoll importiert wurde, kann mit demselben Flughafen abgeglichen, der in der Nähe eines Fotos erkannt wurde. Eine Stadt, die durch eine Suche gefunden wurde, kann mit der Stadt abgeglichen werden, die von Then & Now verwendet wird.

Dieses Paket wird nicht als perfekt oder endgültig betrachtet. Quellenangaben sind in der App sichtbar. Die Build-Skripte werden zusammen mit dem Code gespeichert. Bekannte Korrekturen sind explizit angegeben. Benchmark-Tests schützen das Verhalten bei schwierigen Koordinaten. Ein Update der geografischen Welt ist ein Release-Ereignis mit überprüfbaren Auswirkungen.

Was ich beim Wiederaufbau beibehalten würde

Die haltbarsten Entscheidungen waren keine einzelnen Algorithmen. Sie waren die Grenzen der Verantwortlichkeiten:

• Verwenden Sie Punkte für Namen, stabile Identitäten, Suche und Hierarchie.
• Verwenden Sie Linien und Polygone zur Abgrenzung.
• Erstellen Sie ein schreibgeschütztes Produkt-Artefakt anstelle des Parsens von vier Upstream-Formaten auf einem Telefon.
• Speichern Sie einen lesbaren Schnappschuss mit Benutzerdaten und behalten Sie gleichzeitig die Quell-ID zur Zuordnung bei.
• Machen Sie den üblichen Offline-Pfad deterministisch, bevor Sie ihn beschleunigen.
• Behalten Sie eine langsame Referenzimplementierung lange genug, um zu beweisen, dass die optimierte Ausgabe äquivalent ist.

Der Gazetteer begann als frühes Suchfeature. Er wurde zu einem der wichtigsten Systeme von Mapsake, da fast jedes erweiterte Feature die gleiche einfache Frage beantworten muss: welcher Ort ist das?

Die richtige Antwort zu finden bedeutet, zu akzeptieren, dass Geografie keine einzige Datenbank oder eine clevere Abfrage ist. Es ist eine sorgfältige Vereinbarung zwischen Namen, Punkten, Linien, Produktregeln und dem Reiseverlauf, den eine Person erwartet, zu erkennen.

• Sehen Sie, wie Mapsake aus Fotos eine Reiskarte erstellt.
• Erkunden Sie die unterstützten Importe von Reisehistorien.
• Lesen Sie mehr über das datenschutzorientierte Modell von Mapsake, das auf lokalen Daten basiert.