En teknisk opfølgning: Hvordan vi byggede verdens smukkeste auto-genererede transitkort

af Anton Dubrau

For seks uger siden lancerede vi Transit Maps og skrev dette blogindlæg om, hvorfor vi påtager os den enorme opgave at skabe automatisk genererede, men æstetisk tiltalende kort. Vi blev sprængt af den offentlige reaktion på vores indsats, skønt de ikke var helt overraskede i betragtning af den mængde tid, tanke og inspiration, det tog at skabe dem. I dag opfylder vi vores løfte om at offentliggøre en teknisk opfølgning fra Anton, vores bosiddende kortlægningsguide, der forklarer meget mere detaljeret, hvad der gik til opbygningen af ​​disse kort.

Når du tænker på Transit, kan du tænke slank, farverig grænseflade. I betragtning af at vi er ekstremt særlige med at gøre appen så smuk og anvendelig som muligt, er det ingen stor overraskelse. Men UI er ikke det eneste, vi handler om: vores team strækker sig langt ud over ekspertdesignere, og vores app er meget mere end bare smuk. Under overfladen er der en masse 'hård' teknologi, der roligt driver den.

For det første kontrollerer vores magtfulde backend-kvalitet hundreder af transitdatafeeds, løser automatisk ødelagte data og markerer problemer, der skal undersøges. Dette system giver os mulighed for at styre 350 transitfeeds i 125 byer med et lille team.

Så er der vores komprimeringsalgoritme. Det krymper transitplaner, der er op til 100 gange mindre, end hvilke zip-filer transitbureauer leverer. Dette gør det muligt for Transit at downloade tidsplanerne for brugerens hele region, gemme dataene på brugerens enhed og returnere søgeresultater ... alt sammen i den tid det tager andre apps at anmode om og indlæse en enkelt tidsplan. Og mens vores brugere nu måske er vant til vores apps hastighed, da funktionen først blev introduceret, reducerede den effektivt responstiden fra flere sekunder til 0,1 sekunder. Det er hurtigt.

Men der er en bestemt teknologi, som vi har arbejdet med i årevis. Til vores store glæde (og lettelse) lancerede vi det endelig i sommer: automatisk genererede transitkort.

Transitkort: Transit-app (til venstre), Apple Maps (midt) og Google Maps (til højre)

Ideen i sig selv er næppe ny: Google lancerede deres transitkort for næsten seks år siden. Men det viser sig, at det er ganske problemet at løse, og Google (selv efter alle disse år) kan stadig ikke generere meget smukke eller endda meget nyttige transitkort.

Så hvordan klarede vi det? Med sved, tårer og kreativ tænkning.

1. Former på et kort

Ideen om at oprette automatisk genererede kort er noget, der har betaget mig siden jeg kom til Transit App for tre år siden. På det tidspunkt var Google den eneste spiller i branchen, og for at være ærlig, var deres transitkort en slags crappy. Vi var lige færdig med vores førnævnte superkomprimeringsalgoritme og følte os klar til at tackle et nyt problem. Vi regnede med, temmelig naivt, at det ville tage omkring tre måneder. Lidt vidste vi…

Det første trin var at vise kildedataene på et kort. Mange af ture i de underliggende transitdata indeholdt allerede former, der repræsenterer de ruter, som transitvogne traf. Hvis vi blot tegner alle de former, der er defineret af alle ture, ville vi få en forenklet slags transitkort:

Vores Transit Maps-teknologi, omkring november 2014

Dette var relativt enkelt: vi oprettede en behandlingsrørledning til at udtrække figurerne fra kildedataene; lagrede figurerne i et dataudvekslingsformat; sikrede, at dataene var tilgængelige for enheden; og brugte enhedens kortlægningsbiblioteker til at tegne et nyt lag med dataene.

Let. Vi havde dette igang inden for et par uger.

Men mens det er tæt, er det ikke et rigtigt transitkort. Alle linjer blev tegnet oven på hinanden. Du kan ikke se, hvilke linjer der går hen - og den eneste synlige linje var den, der blev trukket sidst. For ordentlige diagrammatiske kort, hvor du kan følge linjerne med fingeren, skal du have dem tegnet parallelt og skære så lidt som muligt.

2. Matching med OpenStreetMap

At opbygge vores kort med former udgør andre problemer: hvad skal vi gøre, når et agentur ikke leverer nogen formdata, eller hvis et agentur leverer meget dårlige former? De eneste geografiske data, vi ville have i disse tilfælde, ville være stopstederne. Selvfølgelig, vi kunne tegne lige linjer mellem stoppestederne, men det er grimt, rodet og forvirrende.

Det er også problemet med Googles transitkort. I Berlin foretager Google lige forbindelser mellem stop; i London bruger de en slags spline-interpolation, der ikke følger de faktiske spor; og i LA bruger de de former, agenturet leverer, selvom kvaliteten af ​​figurerne virkelig er ret dårlig.

Google Maps i Berlin (venstre) og London (højre)

Det, der er sjovt, er, at når du zoomer ind på kortene, vil du se, at Google ofte har data til de underliggende jernbanespor, hvilket giver anledning til spørgsmålet: hvorfor kombinerer de ikke sporene med formdataene? Besluttet de, at det ikke er vigtigt?

Selvom Google måske ikke synes det er vigtigt, gør vi det bestemt. Sikker på, vi har ikke adgang til Googles rige underliggende kortdata, men vi kan bruge den næste bedste ting: OpenStreetMap (OSM). Og takket være deres samfund af frivillige kortgeeks har OSM stort set alle spor til de offentlige transportlinjer, som vi bruger i vores app.

Jernbanedataene fra OpenStreetMap

Ved at oprette en form langs OSM-gadenettet, der forbinder alle punkter langs en given rute, kunne vi generere vores transitformer! Så vi oprettede en dynamisk programmeringsalgoritme, der følger veje eller spor, der sandsynligvis vil blive brugt af transitlinjer. Den formfremstillende algoritme overvejer hvilken type køretøj, der kører på linjen, og minimerer matchende fejl (dvs. afstandene mellem den genererede form og de faktiske placeringer af kildepunkterne).

Her er et eksempel. I nedenstående diagram har vi en tur med tre stop og ingen forminformation overhovedet. Vi udtrækker det sæt spor, turen bruger fra OSM (grå linjer). Vores matchende algoritme finder derefter en bane (sort linje), der følger OSM, mens den minimerer længden og fejlene til stop (e1, e2, e3).

Form-OSM-matchende proces

Det er svært at få denne algoritme til at fungere i alle tilfælde, så nogle gange er vi nødt til at levere parametre for at få specifikke linjer til at fungere. Samlet set giver det former af høj kvalitet til alle de offentlige transportlinjer, vi har brug for i dag, og de fleste af dem, vi har brug for i fremtiden - også i udviklingslande, hvor OSM ofte er de bedste tilgængelige data.

Et eksempel, der motiverer OSM-matching, selv når figurer er tilgængelige og af anstændig kvalitet: I Montreal-West følger de medfølgende figurer ikke sporet (billede til venstre), så på gadeniveau ser det forfærdeligt ud. Efter OSM-matching (højre) er linjerne meget glattere.

3. Behandling i Pixel Space: Skeletonization

OSM gav os figurerne, men linjerne blev stadig trukket oven på hinanden. Reelle transitkort har linjer trukket parallelt. Hvad vi var nødt til at gøre var at identificere fælles segmenter, hvor de rejser på den samme gade og derefter 'klikke' disse linjer sammen.

Så hvordan gør Google det? De ser ud til at beregne delte segmenter ved at se på stop. Så længe to linjer deler de samme stop, bliver de 'snappet' sammen. Men når det næste stop ikke deles, linjerne 'afbryd':

Googles linjer glemmer, at de kender hinanden straks på det sidste stop, hvor de stopper sammen.

Men det er ikke sådan, hvordan tog og busser virkelig rejser! Linjer forbliver sammen i nogen afstand, inden de divergerer. Hvad vi havde brug for var en algoritme, der ville finde, hvor linjerne begynder at forgrene sig i det virkelige liv.

Vi forsøgte at beregne ruteudskillelserne i vektorrummet, hvilket tilsyneladende var enkelt til at begynde med: tage to linjer, der rejser tæt sammen og derefter finde centrumlinjen i det delte segment. Dette viste sig imidlertid at være overraskende kompliceret, da vi fortsat løb ind i enkle eksempler, der ville bryde vores algoritme. En lille løkke i ruten ville smide midtlinjen ud til uendelig, og vi var også nødt til at håndtere flere linjer, flere grene, forskellige stopmønstre ...

Efter to måneder med bassing af vores hjerner mod vores tastaturer, kastede vi omsider håndklædet. Vi kunne bare ikke finde en stabil, generel løsning, der ville fungere pålideligt, indtil ...

Pixel plads til redning!

I stedet for at behandle linjerne i vektorrum, besluttede vi at prøve noget skør. Vi brugte pixelplads.

Normalt udføres pixelbaseret behandling til billedbaserede data. Det er meget usædvanligt for GIS-behandling, for med en opløsning på 1x / meter ville vores billede være 64 terabyte. Hukommelsen er billig i disse dage ... men ikke så billig!

Så hvordan gjorde vi det? Vi implementerede et specielt sparsomt billedbibliotek, der kunne håndtere disse meget store monokromatiske billeder med relativt få hvide områder.

Derefter oprettede vi en algoritme til at tegne transitformer på et kæmpe sort-hvidt lærred, der repræsenterer hele verden, hvor hver pixel svarer til en kvadratmeter. Hver linje blev tegnet tykt på lærredet, så hvor linjerne var tæt, blev deres pixels samlet.

Når alle linjerne var trukket, brugte vi en "skeletonisering" -proces til successivt at tynde linjerne, indtil hver kun var en pixel tyk. Så mens linierne ikke længere blev slået sammen, forblev de forbundet og opretholdt den samme topologi. Disse tynde linier repræsenterer hvor transitlinjerne kører sammen og afslører strukturen i netværket.

Den hvide repræsenterer de trukket transitlinjer. 'Skelettet' er overlagt med rødt.

Selvom vi nu havde netværkets midtlinjer, havde vi ødelagt mere information, end vi havde fået. Det, vi havde nu, var en masse pixels, der betegner skelettet, hvilket betød, at vi vidste, at hver linje skulle rejse langs dette skelet, men vi var stadig nødt til at finde ud af, hvilke linjer der kørte hvor.

Ved hjælp af skelettet genopbyggede vi nu linjerne i modsætning til de former, vi tidligere havde. Vi behandlede derefter det resulterende netværk for at slippe af med de fejl, der blev introduceret af skeletoniseringen.

Dette trin var langt og kedeligt. Alt i alt tog tegning, skeletonisering, netværksopbygning og fejlfinding et sted omkring seks måneder at udvikle sig. (Så meget for at få det hele gjort i tre!)

Men de endelige resultater var tilfredsstillende. Vi havde en intern repræsentation af linjer, der rejser sammen og divergerede. Det så sådan ud:

Da vi gengiver linjerne parallelt, fik vi dette:

Succes!

Temmelig godt til en version 1. Meget bedre end Google, da du mere eller mindre kan drille, hvor hver linje går. Vi var klar til at rulle Transit Maps ud! Og så ... Apple Maps skete.

I sommeren 2015, efter at have arbejdet med vores kort i en bedre del af et år, var vi endelig klar til at frigive vores første version af Transit Maps. Så rullede Apple deres transitkort ud, og de var virkelig smukke.

Apples smukke transitkort

De hævede øjeblikkeligt linjen for, hvordan transitkort skal se ud. I vores tegninger og design var slutmålet noget, der ligner (eller bedre end), hvad Apple efterfølgende frigav, men vi planlagde at komme dertil efter frigivelse af vores version 1.

Sammenlignet med Apple var vores foreslåede version 1 slags middelmådige. Vores designer-CEO besluttede, at det at slå Google ikke var godt nok - vi måtte også i det mindste spille i den samme liga som Apple.

Efter nærmere gennemgang antog vi, at Apple tegner deres kort manuelt. Der var enorme forsinkelser mellem frigivelsen af ​​nye byer, og der var noget underligt ved kortets udseende - som om de var tegnet af mennesker, ikke computere. Dette betød, at selv om vores kort ikke var lige så smukke, var vores algoritme stadig foran deres.

På dette tidspunkt vidste vi også, at den hårde del var bag os. Vi havde fundet ud af et netværk, der ville give os mulighed for at tegne linjer parallelt. Nu var alt hvad vi skulle gøre, at få det til at se godt ud.

4. Transit Line Ordering ved hjælp af heltal lineær programmering

Inden vi offentliggjorde vores kort, var vi nødt til at slippe af med den grimme, unødvendige krydsning af linjer, der gjorde dem til et forfærdeligt spaghetti-rod.

Hvis vi kunne sortere linjerne for at minimere det visuelle rod tæt ved kryds, ville vi have et offentliggøreligt kort. For at gøre dette var vi nødt til at beslutte, hvilke linjer der skulle gå til venstre, og hvilke der skulle gå til højre for at minimere deres krydsninger.

Google havde (og har stadig) et lignende problem - undtagen deres linjer krydser hinanden, selv hvor der kun er stop og ingen kryds.

Åh, kom på Google! Linjerne skal forblive organiserede.

For os skete krydsning kun, hvor linjer faktisk sluttede sig og divergerede, så vi gjorde allerede bedre end Googles algoritme. Det skyldes, at vi lagrede delte sektioner baseret på geografi.

Så hvordan blev vi af med spaghettien? Først prøvede vi en heuristisk løsning - sorteringslinjer baseret på hvor de afsluttes - men dette mislykkedes ofte, og det fungerede nogle steder, men ikke andre.

For at forbedre den heuristiske løsning oprettede vi en matematisk model, der ville 'score' en given rækkefølge af linjer, straffe krydsning af linjer samt andet visuelt rod.

Flere mulige krydsingsscenarier, der markerer kilder til sanktioner ved hjælp af røde cirkler

Som du kunne forvente, kan det at skabe et andet sted et andet sted undgå et overkrydsning på et sted på kortet. Alt er forbundet! Så hvad gjorde vi? Vi fandt bestilling af linjer, der havde den laveste globale straffescore.

Integer-lineær programmering var det, der gjorde det muligt for os at udforske alle mulighederne og finde en løsning, der globalt minimerede straffunktionen. Men behandlingstiden til heltal-lineær programmering er eksponentiel i problemstørrelsen: at løse et problem kan tage et sekund; et andet vanskeligere problem kan tage et år! Det gjorde det risikabelt at bruge, selv i 'offline' forbehandling inden i backend.

Vi var bekymrede. Behandling af Chicagos data tog os timer. Et større område som den nordøstlige korridor (Boston til Washington) kan tage uger! Heldigvis fandt vi en anden angrebsplan: en, der gjorde det muligt for den heltal-lineære programmeringsløsere at udforske problemområdet mere effektivt og finde optimale løsninger hurtigere. Det, der tidligere tog en time, tog nu 0,2 sekunder.

At se optimering som denne i handling er uhyggeligt: ​​når du ser algoritmen tage beslutninger, er det som at være vidne til en strålende matematiker, der ubesværet løser problemer med de klareste, mest kortfattede løsninger.

Før / Efter linjesortering

Med de andre behandlingstrin, der allerede var afsluttet i forbehandlingen på serveren, blev dataene nu gemt i binære filer og sendt til enheden for den faktiske gengivelse af kort på ethvert ønsket zoomniveau.

5. Circle-Arc afrunding af linjer

Vi var dog stadig ikke helt færdige. Håndtegnede diagrammatiske transitkort ligner stadig ikke rigtig kortene vist ovenfor. Deres linjer er smukt afrundet med glatte overgange i kryds. Vi ønskede, at vores kort skulle have et lignende afrundet udseende.

Når linjer spores rundt om hjørnerne, ville vi have dem til at forblive perfekt parallelle, selv i potentielt degenerative tilfælde, som i Chicago. Der rejser et stort antal linjer sammen omkring skarpe kurver, så at tegning af dem parallelt kan resultere i linjer, der bundter sig på indersiden af ​​svingen.

Normalt foretages afrunding ved hjælp af bezier-kurver, som ser ud som om de letter på kurverne. Men for at forblive tro mod udseendet på diagrammatiske transitkort, var bezier-kurver ikke helt rigtige. Transitkort har lige linjer, der falder skarpt i cirkulære buesegmenter. Så vi brugte lysbuesegmenter til afrunding.

I modsætning til bezier-kurver er enhver linje parallelt med en cirkelbue i sig selv en cirkelbue. Så længe radius er stor nok, var vi garanteret ikke at have degenerative tilfælde.

Vi kom med en brugerdefineret algoritme, der med en form ville fjerne og tilføje punkter for at afrunde den ved hjælp af cirkulære lysbuesegmenter. Det garanterer en given minimumsradius ved at forenkle geometrien efter behov. Minimumsradius afhænger af den samlede bredde på alle parallelle linjer.

Den resulterende form er glat. Det er helt sammensat af lige linjer og lysbuesegmenter, hvilket betyder, at vi altid kan tegne linjer parallelt uden nogen artefakter eller degenerative tilfælde.

Denne tilgang gav os sådan noget:

Afrundingen sker kun langs delte segmenter. Du bemærker muligvis også, at vi fjernede alle kryds. Håndtering af krydsene var et stort problem, fordi vi var nødt til at sikre, at hver linje fortsatte fra et segment til det næste og koblet ordentligt sammen. Vi brugte også den lysbue-genererende algoritme til at have det samme afrundede look. Her er det endelige resultat:

Temmelig godt, ikke? Men mens de var smukke ... så de stadig underligt nøgne ud. Det skyldes, at de manglede stop.

Så vi besluttede at fortsætte med frigivelsen endnu en gang - og tilføje et sidste trin.

6. Tilføjelse af stop

Tilføjelse af stop kan virke ligefrem, men det kræver faktisk en vis behandling at sprede stopinformationen gennem den lange rørledning, vi havde oprettet.

Vi stødte også på mange tilfælde, hvor flere stop i dataene faktisk svarede til en enkelt fysisk station, så vi var nødt til at kollapse dem i ét stop.

Her er hvad vi gjorde. Ved stop med flere linjer trak vi en hvid bjælke med en sort kontur (til kontrast) på tværs af alle linjerne. Ved stop på en enkelt linje tegnet vi en simpel cirkel ved hjælp af farven på den pågældende transitlinie. Vi tilføjede også et hvidt overlay for at reducere kontrasten for kortlaget nedenfor. Dette er det endelige resultat:

For at give brugere mulighed for at tænde og slukke linjer selektivt fra vores apps indstillingsside, besluttede vi, at afrundingen såvel som noget stop-behandling og gengivelse skulle udføres på enheden. Så i New York City kan du deaktivere alle New Jersey-baserede transitlinjer (eller alle NYC-linjer, hvis du bor i New Jersey). Med så mange transitlinjer i bestemte områder giver dette brugere mulighed for at oprette fuldt tilpassede kort.

Bemærk, hvordan linjerne vises igen baseret på hvilken linje, der er aktive, og hvordan stop skifter farve.

Konklusion

Så sådan gjorde vi det. Sikker på at implementere automatisk genererede transitkort krævede en masse arbejde, men det var det værd. Vores kort er et pænt stykke meget mere kraftfuldt end de PDF-filer, du er vant til at få fra bureauer, ligesom det papir, du folder sammen og fastklemmer i din tegnebog. Hvad er de største forskelle?

Vores transitkort er skalerbare, så vi nemt kan tilføje nye byer i samme visuelle stil, uanset hvor i verden vi udvider til næste. De kan tilpasses, så brugere kan tænde / slukke netværk og tilstande for at oprette deres helt egne personaliserede transitkort. Og de er også kontekstuelle: I modsætning til en PDF-fil på et agenturekort, indeholder vores kort din placering, hvilket giver dig en fornemmelse af, hvor du er i forhold til linier i nærheden og justerer udseendet afhængigt af dit zoomniveau.

Og i sidste ende giver vores diagrammatiske transitkort mere end blot de grundlæggende oplysninger om transportsystemer. De er symbolsk for byerne selv: vigtige stykker funktionel kunst, der forbinder mennesker til deres miljøer. Vi ønsker at hjælpe med at opbygge denne forbindelse, og vi tror, ​​at vores nye transitkort gør netop det.

Vi er glade for at fortsætte med at forbedre os, men er tilfredse med det, vi har opnået indtil videre. Vi lancerede med 55 byer. Responsen på vores blogindlæg, der sammenligner vores kort med Googles og Apples, har været utroligt positivt. For backend-teamet er det dejligt at få folk til at se og værdsætte det arbejde og den indsats, vi lægger på, hvad der driver appens oplevelse. Det motiverer os til at fortsætte med at skubbe vores teknologi videre.

Derudover har vi stadig mange flere 'hårde' problemer at løse. Vi vil fortsætte med at arbejde under hætten, ikke kun mod at have den smukkeste app med den bedste brugergrænseflade, men den mest funktionelle, kraftfulde og præcise transitapp derude.

Vil du lege med vores kort?
Du kan få Transit gratis i App Store og Google Play. Eller lære mere om virksomheden på vores hjemmeside.

Har du lyst til at tackle udfordringer som denne til leve? Vi ansætter!