Техническо проследяване: Как изградихме най-хубавите автоматично генерирани карти за транзит в света

от Антон Дубрау

Преди шест седмици стартирахме Transit Maps и написахме тази публикация в блога за това защо се заехме с мамутната задача да създадем автоматично генерирани, но естетически приятни карти. Бяхме взривени от реакцията на обществото към нашите усилия, макар и не съвсем изненадани, като се има предвид времето, мисълта и вдъхновението, необходими за създаването им. Днес изпълняваме обещанието си да публикуваме техническо проследяване от Антон, наш съветник за картографиране, който обяснява много по-подробно какво е създало тези карти.

Когато мислите за Transit, може да помислите за елегантен, цветен интерфейс. Като се има предвид, че ние сме изключително особени в това да направим приложението възможно най-красиво и използваемо, това не е голяма изненада. Но потребителският интерфейс не е единственото, за което става дума: нашият екип се разпростира над експертните дизайнери, а нашето приложение е много повече от просто красиво. Под повърхността има много „твърда“ технология, която тихо я кара.

Първо, нашето мощно резервно качество проверява стотици транзитни емисии от данни, автоматично коригира счупени данни и проблеми с флаговете, които се нуждаят от проучване. Тази система ни позволява да управляваме 350 транзитни емисии в 125 града с малък екип.

Тогава има нашия алгоритъм за компресия. Той свива графиците за транзит до 100 пъти по-малки от предоставените от транзитните агенции zip-файлове. Това позволява на Transit да изтегля графиците на целия регион на потребителя, да съхранява данните на устройството на потребителя и да връща резултати от търсенето ... всичко това за времето, необходимо на други приложения да заявят и заредят един график. И макар че потребителите ни сега може да са свикнали със скоростта на приложението ни, при първото въвеждане на функцията, тя ефективно намалява времето за реакция от няколко секунди на 0,1 секунди. Това е бързо.

Но има една конкретна технология, над която работим от години. За наша голяма радост (и облекчение), най-накрая го пуснахме това лято: автоматично генерирани транзитни карти.

Карти за транзит: Приложение за транзит (отляво), Apple Maps (в средата) и Google Maps (вдясно)

Самата идея едва ли е нова: Google пуснаха транзитните им карти преди почти шест години. Но се оказва, че е доста проблем да се реши и Google (дори и след всички тези години) все още не може да генерира много красиви или дори много полезни транзитни карти.

И така, как се справихме? С пот, сълзи и креативно мислене.

1. Форми на карта

Идеята за създаване на автоматично генерирани карти е нещо, което ме плени от преди да се присъединя към Transit App преди три години. По онова време Google беше единственият играч в бранша и, честно казано, техните транзитни карти бяха някак глупави. Току-що завършихме гореспоменатия алгоритъм за супер компресия и се почувствахме готови да се справим с нов проблем. Решихме, по-скоро наивно, че ще отнеме около три месеца. Малко знаехме ...

Първата стъпка беше да се покажат изходните данни на карта. Много от пътуванията в основните данни за транзита вече съдържат форми, представящи маршрутите, по които са преминали транзитните превозни средства. Ако просто нарисувахме всички форми, определени от всички пътувания, ще получим опростен вид транзитна карта:

Нашата технология за транзитни карти, около ноември 2014 г.

Правенето на това беше сравнително просто: ние създадохме тръбопровод за обработка, за да извлечем фигурите от изходните данни; съхранява фигурите във формат за обмен на данни; гарантира, че данните са достъпни за устройството; и използва библиографските карти на устройството, за да нарисува нов слой с данните.

Лесно. Имахме това и работихме в рамките на няколко седмици.

Но докато е близо, това не е истинска карта за транзит. Всички линии бяха нарисувани една върху друга. Не можете да кажете кои линии отиват - и единствената видима линия беше тази, която беше начертана последна. За правилни схематични карти, на които можете да следвате линиите с пръст, е необходимо те да бъдат начертани паралелно и да се пресичат възможно най-малко.

2. Съвпадение с OpenStreetMap

Изграждането на нашите карти с форми създава други проблеми: какво да правим, когато агенцията не предоставя данни за формата или ако агенцията предоставя много лоши форми? Единствените географски данни, които бихме имали в тези случаи, са местата за спиране. Разбира се, можем да начертаем прави линии между спирките, но това е грозно, объркано и объркващо.

Проблемът е и с транзитните карти на Google. В Берлин Google прави линейни връзки между спирките; в Лондон използват някаква сплайнова интерполация, която не следва действителните песни; и в Ел Ей те използват формите, предоставени от агенцията, въпреки че качеството на формите наистина е доста лошо.

Google Maps в Берлин (вляво) и Лондон (вдясно)

Забавното е, че когато увеличавате картите, ще видите, че Google често има данни за основните железопътни коловози, което поставя въпроса: защо не комбинират коловозите с данните за формата? Решиха ли, че не е важно?

Въпреки че Google може да не смята, че е важно, ние със сигурност го правим. Разбира се, нямаме достъп до богатите основни данни на Google, но можем да използваме следващото най-добро нещо: OpenStreetMap (OSM). И благодарение на тяхната общност от доброволци-геодези, OSM има практически всички коловози за железопътните линии за обществен транспорт, които използваме в нашето приложение.

Данните за железопътния транспорт на OpenStreetMap

Създавайки форма по OSM уличната мрежа, която свързва всички точки по даден маршрут, бихме могли да генерираме нашите транзитни форми! Така създадохме алгоритъм за динамично програмиране, който следва пътища или трасета, които вероятно ще бъдат използвани от транзитни линии. Алгоритъмът за създаване на форма отчита какъв тип превозно средство работи по линията и свежда до минимум грешките при съвпадение (т.е. разстоянията между генерираната форма и действителните местоположения на изходните точки).

Ето пример. На диаграмата по-долу имаме пътуване с три спирки и никаква информация за формата. Ние извличаме набора от песни, които пътуването използва от OSM (сиви линии). Нашият алгоритъм за съвпадение след това намира траектория (черна линия), която следва OSM, като в същото време минимизира неговата дължина и грешките до стоповете (e1, e2, e3).

Процесът на съвпадение на формата OSM

Трудно е този алгоритъм да работи за всички случаи, така че понякога се налага да предоставяме параметри, за да работим конкретни линии. Като цяло тя ни дава висококачествени форми за всички обществени линии за транзит, от които се нуждаем днес, и повечето от тези, от които ще се нуждаем в бъдеще - дори в развиващите се страни, където OSM често е най-добрите налични данни.

Един пример, който мотивира съвпадението с OSM, дори когато формите са налични и с прилично качество: В Монреал-Запад предоставените форми не следват пистата (изображение вляво), така че на нивото на улицата изглежда ужасно. След съвпадение с OSM (вдясно) линиите са много по-гладки.

3. Обработка в пикселно пространство: скелетонизация

OSM ни даде форми, но линиите все още се очертаваха една върху друга. Реалните транзитни карти имат линии, очертани успоредно. Това, което трябваше да направим, беше да идентифицираме общи сегменти, където те пътуват по една и съща улица, и след това „щракнете“ тези линии заедно.

И така, как Google го прави? Изглежда, че изчисляват споделени сегменти, като гледат спирките. Докато две линии споделят едни и същи спирки, те са „щракнати“ заедно. Но когато следващата спирка не бъде споделена, редовете „отмяна“:

Редовете на Google забравят, че се познават веднага на последната спирка, където спират заедно.

Но не така пътуват влаковете и автобусите! Линиите остават заедно за известно разстояние, преди да се разминават. Това, от което се нуждаех, беше алгоритъм, който ще открие къде линиите започват да се разклоняват в реалния живот.

Опитахме се да изчислим разделенията на маршрута във векторно пространство, което в началото изглеждаше просто: вземете две линии, които се движат плътно заедно и след това открийте средната линия на споделения сегмент. Това обаче се оказа учудващо сложно, тъй като продължихме да бягаме в прости примери, които биха нарушили алгоритъма ни. Малък цикъл в маршрута би изхвърлил от безкрайност централната линия и ние също трябваше да се справим с множество линии, множество разклонения, различни модели на спиране ...

След два месеца, като удряхме мозъка си по клавиатурите, най-накрая хвърлихме кърпата. Просто не можахме да намерим стабилно общо решение, което да работи надеждно, докато ...

Пиксел пространство за спасяване!

Вместо да обработим линиите във векторно пространство, решихме да опитаме нещо лудо. Използвахме пикселно пространство.

Обикновено обработката на базата на пиксели се извършва за данни, базирани на изображения. Това е много необичайно за GIS обработка, тъй като при резолюция 1px / метър изображението ни ще бъде 64 терабайта. Паметта е евтина в наши дни ... но не е толкова евтина!

И така, как го направихме? Внесохме специална библиотека с разредени изображения, която може да се справи с тези много големи монохроматични изображения със сравнително малко бели области.

След това създадохме алгоритъм за рисуване на транзитни фигури върху гигантско черно-бяло платно, представящо целия свят, където всеки пиксел е еквивалентен на един квадратен метър. Всяка линия беше нарисувана гъсто върху платното, така че където и линиите да бяха близки, техните пиксели се сливаха заедно.

След като всички линии бяха нарисувани, използвахме процес на "скелетонизиране", за да разреждаме последователно линиите, докато всяка от тях не беше с дебелина само един пиксел. И така, докато линиите вече не бяха слети, те останаха свързани, поддържайки същата топология. Тези тънки линии представляват мястото, където транзитните линии пътуват заедно, и разкриват структурата на мрежата.

Бялото представлява начертаните транзитни линии. „Скелетът“ е наслоен в червено.

Въпреки че сега разполагахме с централните линии на мрежата, бяхме унищожили повече информация, отколкото сме спечелили. Това, което имахме сега, бяха куп пиксели, обозначаващи скелета, което означаваше, че знаем, че всяка линия трябва да се движи по този скелет, но все пак трябваше да разберем кои линии пътуват къде.

Използвайки скелета, ние възстановихме линиите, за разлика от формите, които преди сме имали. След това обработихме получената мрежа, за да се освободим от проблемите, въведени от скелетонизацията.

Тази стъпка беше дълга и досадна. Като цяло, разработването, скелетонизирането, изграждането на мрежа и отстраняването на грешки отне някъде около шест месеца. (Толкова за това, че цялата работа е направена в три!)

Но крайните резултати бяха задоволителни. Имахме вътрешно представяне на линии, които пътуват заедно и се разминават. Изглеждаше така:

Когато паралелно рендирахме линиите, получихме това:

Успех!

Доста добър за Версия 1. Много по-добър от Google, тъй като можете повече или по-малко да дразнете къде отива всеки ред. Бяхме готови да разгърнем транзитни карти! И тогава ... Apple Maps се случи.

През лятото на 2015 г., след като работихме върху нашите карти през по-голямата част от година, най-накрая бяхме готови да пуснем първата си версия на Transit Maps. Тогава Apple разгърна транзитните си карти и те наистина бяха много.

Apple доста транзитни карти

Веднага вдигнаха лентата за това как трябва да изглеждат транзитните карти. В нашите чертежи и дизайни крайната цел беше нещо подобно на (или по-добро от) това, което Apple впоследствие пусна, но ние планирахме да стигнем до там, след като пуснахме нашата Версия 1.

В сравнение с Apple, предлаганата от нас версия 1 беше някак посредствена. Нашият дизайнер-изпълнителен директор постанови, че побеждаването с Google не е достатъчно добро - ние също трябваше поне да играем в същата лига като Apple.

След по-внимателен контрол, ние предположихме, че Apple рисува картите си ръчно. Между освобождаването на нови градове имаше огромни изоставания и имаше нещо странно в начина, по който изглеждат картите - сякаш те бяха нарисувани от хора, а не от компютри. Това означаваше, че въпреки че нашите карти не бяха толкова красиви, алгоритъмът ни все още изпревари техния.

В този момент също разбрахме, че тежката част е зад нас. Бяхме измислили мрежа, която ще ни позволи да начертаваме паралелно линии. Сега всичко, което трябваше да направим, беше да изглежда добре.

4. Подреждане на транзитни линии с помощта на цялостно линейно програмиране

Преди да публикуваме нашите карти, трябваше да се освободим от грозното, ненужно пресичане на линии, което ги превръщаше в ужасяваща спагети.

Ако можехме да сортираме линиите, за да сведем до минимум визуалното претрупване в близост до кръстовищата, ще имаме публикувана карта. За да направим това, трябваше да решим кои линии ще отидат вляво и коя ще отидат надясно, за да сведат до минимум техните пресичания.

Google имаше (и все още има) подобен проблем - с изключение на това, че линиите им се пресичат помежду си, дори когато има само спирки и няма пресечки.

О, хайде в Google! Линиите трябва да останат организирани.

За нас пресичането се случи само там, където линиите действително се присъединиха и се разминаха, така че вече се справяхме по-добре от алгоритъма на Google. Това е така, защото съхранявахме споделени секции въз основа на география.

И така, как се отървахме от спагетите? Първо опитахме евристично решение - сортиране на линии въз основа на мястото, където те приключват - но това често се проваля, като се работи на някои места, но не и на други.

За да подобрим евристичното решение, ние създадохме математически модел, който ще "оцени" зададен ред на линиите, санкционирайки пресичането на линиите, както и други визуални смущения.

Няколко възможни сценария за пресичане, маркиране на източници на санкции с помощта на червени кръгове

Както може би очаквате, избягването на кръстосване на едно място на картата може да създаде друго някъде другаде. Всичко е свързано! И така, какво направихме? Открихме подреждането на линии с най-ниската глобална оценка на наказанията.

Линейно-линейното програмиране беше това, което ни позволи да проучим всички възможности и да намерим решение, което глобално свежда до минимум наказателната функция. Но времето за обработка на цяло-линейно програмиране е експоненциално в размера на проблема: решаването на един проблем може да отнеме една секунда; друг по-труден проблем може да отнеме година! Това го направи рисковано да се използва, дори и при „офлайн“ предварителна обработка вътре в бекенда.

Тревожехме се. Обработката на данните в Чикаго ни отне часове. По-голяма площ като Североизточния коридор (Бостън до Вашингтон) може да отнеме седмици! За щастие открихме различен план за атака: този, който позволи на решаването на цяло число-линейно програмиране да изследва проблемното пространство по-ефективно и да намери по-бързо оптимални решения. Това, което преди отне час, сега отне 0.2 секунди.

Да виждате подобна оптимизация в действие е странно: когато видите алгоритъма да взима решения, това е като да станете свидетели на някакъв брилянтен математик, който без усилия решава проблемите с най-ясните, най-сбити решения.

Преди / След сортиране на линии

С останалите стъпки на обработка, които вече са завършени при предварителната обработка на сървъра, данните вече се съхраняват в двоични файлове и се изпращат на устройството за действителното изобразяване на карти при всяко желано ниво на увеличение.

5. Кръгово-дъгово закръгляване на линиите

Все още обаче не бяхме съвсем готови. Рисуваните на ръка схематични транзитни карти все още не изглеждат като картите, показани по-горе. Техните линии са добре заоблени с плавни преходи в пресечки. Искахме нашите карти да имат подобен заоблен вид.

Когато линиите се очертаваха по ъглите, ние искахме те да останат напълно успоредни, дори в потенциално дегенеративни случаи, като в Чикаго. Там голям брой линии се движат заедно около остри криви, така че изчертаването им успоредно може да доведе до изкълчване на линии от вътрешната страна на завоя.

Обикновено закръгляването се извършва с помощта на безиеви криви, които изглеждат така, сякаш се облекчават в кривите. Но за да останем верни на външния вид на схематичните транзитни карти, безиевите криви не бяха съвсем правилни. Транзитните карти имат прави линии, които рязко попадат в сегменти на кръговата дъга. Затова използвахме дъгови сегменти за закръгляне.

Също така, за разлика от кривите на Безие, всяка линия, успоредна на дъга на кръг, сама по себе си е дъга на окръжност. Докато радиусът е достатъчно голям, гарантирано ни нямаше дегенеративни случаи.

Ние създадохме персонализиран алгоритъм, който, като даде форма, ще премахне и добави точки, за да го закръгли, като използва сегменти от кръгова дъга. Той гарантира зададен минимален радиус чрез опростяване на геометрията при необходимост. Минималният радиус зависи от общата ширина на всички успоредни линии.

Получената форма е гладка. Той е изцяло съставен от прави линии и дъгови сегменти, което означава, че винаги можем да рисуваме линии паралелно без артефакти или дегенеративни случаи.

Този подход ни даде нещо подобно:

Закръгляването става само по споделени сегменти. Може също да забележите, че премахнахме всички кръстовища. Работата с кръстовищата беше основен проблем, защото трябваше да гарантираме, че всеки ред продължава от един сегмент до следващ и се свързва правилно. Използвахме и алгоритъма за генериране на дъга, за да имаме същия заоблен вид. Ето и крайния резултат:

Доста страхотно, нали? Но докато бяха доста ... те все още изглеждаха странно голи. Това е така, защото липсваха спирки.

Затова решихме да спрем отново на изданието - и добавихме една последна стъпка.

6. Добавяне на спирки

Добавянето на спирки може да изглежда просто, но всъщност изисква доста голямо количество обработка, за да се разпространи информацията за стоп през дългия тръбопровод, който създадохме.

Също така се сблъскахме с много случаи, при които множество спирания в данните всъщност съответстваха на една единствена физическа станция, така че трябваше да ги сгънем в едно спиране.

Ето какво направихме. За спирки с множество линии нарисувахме бяла лента с черен контур (за контраст) по всички линии. За спирки на една линия нарисувахме обикновен кръг, използвайки цвета на тази конкретна транзитна линия. Добавихме и бяло наслагване, за да намалим контраста на слоя карта отдолу. Това е крайният резултат:

За да позволим на потребителите да превръщат и изключват линии избирателно от страницата с настройки на нашите приложения, решихме, че закръгляването, както и някои спиране на обработката и изобразяването трябва да се извършат на устройството. Така че в Ню Йорк можете да деактивирате всички базирани в Ню Джърси транзитни линии (или всички NYC линии, ако живеете в Ню Джърси). С толкова много транзитни линии в определени области това позволява на потребителите да създават напълно персонализирани карти.

Обърнете внимание как ретирите на линиите се основават на коя линия са активни и как стопът променя цвета си.

заключение

Така го направихме. Разбира се, внедряването на автоматично генерирани транзитни карти отне много работа, но си заслужаваше. Нашите карти са много по-мощни от PDF файловете, които сте свикнали да получавате от агенции, без значение хартиените, които сгъвате и засядате в портфейла си. Кои са основните разлики?

Нашите Транзитни карти са мащабируеми, така че лесно можем да добавим нови градове в същия визуален стил, където и да се разширяваме до следващия. Те са персонализируеми, така че потребителите могат да включват / изключват мрежи и режими, за да създават свои собствени персонализирани транзитни карти. И те също са контекстуални: за разлика от PDF на карта на агенцията, нашите карти съдържат вашето местоположение, което ви дава усещане за това къде сте по отношение на близките линии и коригира външния вид в зависимост от вашето ниво на увеличение.

И в крайна сметка нашите схематични транзитни карти предоставят повече от само основната информация за транзитните системи. Те са емблематични за самите градове: важни части от функционалното изкуство, които свързват хората с тяхната среда. Искаме да помогнем за изграждането на тази връзка и вярваме, че нашите нови транзитни карти правят точно това.

Радваме се да продължаваме да се подобряваме, но сме доволни от постигнатото досега. Стартирахме с 55 града. Отговорът на нашата публикация в блога, сравнявайки нашите карти с Google и Apple, беше невероятно положителен. За бекенд екипа е чудесно хората да виждат и оценяват работата и усилията, които влагаме в това, което движи опита на приложението. Това ни мотивира да продължаваме да натискаме технологията си още повече.

Отвъд това, ние все още имаме много повече „трудни“ проблеми за решаване. Ще продължим да работим под капака, не само за да имаме най-красивото приложение с най-добрия потребителски интерфейс, но и най-функционалното, мощно и точно приложение за транзит там.

Искате да играете с нашите карти?
Можете да получите Транзит безплатно в App Store и Google Play. Или научете повече за компанията на нашия уебсайт.

Чувствате ли се като да се справите с предизвикателства като това за живот? Търсим служители!