Τεχνική παρακολούθηση: Πώς κατασκευάσαμε τους πιο όμορφους χάρτες διαμετακόμισης αυτοκινήτου παγκοσμίως

από τον Anton Dubrau

Πριν από έξι εβδομάδες ξεκινήσαμε τους Χάρτες Διαμετακόμισης και γράψαμε αυτήν την ανάρτηση ιστολογίου για το γιατί πήραμε το μαζικό καθήκον να δημιουργούμε αυτοματοποιημένους αλλά και αισθητικά ευχάριστους χάρτες. Μας έσκαψαν οι δημόσιες αντιδράσεις στις προσπάθειές μας, αν και δεν εκπλήσσονταν εντελώς δεδομένου του χρόνου, της σκέψης και της έμπνευσης που χρειάστηκε για να τις δημιουργήσουν. Σήμερα, εκπληρώνουμε την υπόσχεσή μας να δημοσιεύσουμε μια τεχνική παρακολούθηση από τον Anton, τον κάτοχό μας χαρτογράφησης κατοίκων, ο οποίος εξηγεί με πολύ μεγαλύτερη λεπτομέρεια τι πήγε στην κατασκευή αυτών των χαρτών.

Όταν σκέφτεστε τη διέλευση, ίσως να σκεφτείτε κομψή, πολύχρωμη διεπαφή. Δεδομένου ότι είμαστε εξαιρετικά ιδιαίτεροι για να κάνουμε την εφαρμογή τόσο όμορφη και χρησιμοποιήσιμη όσο το δυνατόν, αυτό δεν είναι μεγάλη έκπληξη. Όμως, το UI δεν είναι το μόνο πράγμα που είμαστε: η ομάδα μας εκτείνεται πέρα ​​από τους σχεδιαστές εμπειρογνωμόνων, και η εφαρμογή μας είναι κάτι περισσότερο από όμορφο. Κάτω από την επιφάνεια, υπάρχει μια πολύ «σκληρή» τεχνολογία που την οδηγεί ήσυχα.

Πρώτον, η ισχυρή ποιότητα backend μας ελέγχει εκατοντάδες τροφοδοσίες δεδομένων διέλευσης, διορθώνει αυτόματα σπασμένα δεδομένα και ζητήματα σημαίας που χρειάζονται έρευνα. Αυτό το σύστημα μας επιτρέπει να διαχειριζόμαστε 350 τροφοδοσίες διαμετακόμισης σε 125 πόλεις με μικρή ομάδα.

Τότε υπάρχει ο αλγόριθμος συμπίεσης μας. Συρρικνώνει τα δρομολόγια διαμετακόμισης μέχρι και 100 φορές μικρότερα από τα γραφεία διαμετακόμισης φακέλων με φερμουάρ. Αυτό επιτρέπει στο Transit να κατεβάζει τα χρονοδιαγράμματα ολόκληρης της περιοχής του χρήστη, να αποθηκεύει τα δεδομένα στη συσκευή του χρήστη και να επιστρέφει τα αποτελέσματα αναζήτησης ... όλοι με το χρόνο που χρειάζονται άλλες εφαρμογές για να ζητήσουν και να φορτώσουν ένα μόνο πρόγραμμα. Και ενώ οι χρήστες μας μπορούν τώρα να εξοικειωθούν με την ταχύτητα της εφαρμογής μας, όταν η λειτουργία παρουσιάστηκε για πρώτη φορά, μειώνει αποτελεσματικά το χρόνο απόκρισης από μερικά δευτερόλεπτα σε 0,1 δευτερόλεπτα. Αυτό είναι γρήγορο.

Αλλά υπάρχει μια συγκεκριμένη τεχνολογία στην οποία εργαζόμαστε εδώ και χρόνια. Για τη μεγάλη μας χαρά (και ανακούφιση), την ξεκινήσαμε τελικά αυτό το καλοκαίρι: χάρτες διαμετακόμισης που δημιουργήθηκαν αυτόματα.

Χάρτες διαμετακόμισης: Εφαρμογή διαμετακόμισης (αριστερά), Χάρτες Apple (μεσαία) και Χάρτες Google (δεξιά)

Η ίδια η ιδέα είναι μόλις καινούργια: η Google ξεκίνησε τους χάρτες διαμετακόμισης σχεδόν πριν από έξι χρόνια. Αλλά αποδεικνύεται ότι είναι αρκετά το πρόβλημα να λυθεί, και το Google (ακόμα και μετά από όλα αυτά τα χρόνια) εξακολουθεί να μην μπορεί να δημιουργήσει πολύ όμορφοι ή και πολύ χρήσιμοι χάρτες διαμετακόμισης.

Τόσο πώς το καταφέραμε; Με ιδρώτα, δάκρυα και δημιουργική σκέψη.

1. Σχήματα σε χάρτη

Η ιδέα της δημιουργίας αυτόματα δημιουργημένων χαρτών είναι κάτι που με αιχμαλώτισε πριν από την είσοδό της στην Transit App πριν από τρία χρόνια. Εκείνη την εποχή, η Google ήταν ο μόνος παίκτης στον κλάδο και, για να είμαι ειλικρινής, οι χάρτες διαμετακόμισης ήταν κάπως μπερδεμένοι. Είχαμε τελειώσει τον προαναφερθέντα αλγόριθμό σούπερ συμπίεσης και είμαστε έτοιμοι να αντιμετωπίσουμε ένα νέο πρόβλημα. Σκεφτήκαμε, μάλλον άγρια, ότι θα χρειαζόταν περίπου τρεις μήνες. Λίγα ξέρουμε ...

Το πρώτο βήμα ήταν να δείξουμε τα δεδομένα πηγής σε ένα χάρτη. Πολλά από τα ταξίδια στα υποκείμενα δεδομένα διαμετακόμισης περιείχαν ήδη σχήματα που αντιπροσωπεύουν τις διαδρομές που διέθεταν τα οχήματα. Εάν απλά τραβήξαμε όλα τα σχήματα που ορίστηκαν από όλα τα ταξίδια, θα παίρναμε ένα απλουστευμένο είδος χάρτη διέλευσης:

Η τεχνολογία των Χαρτών Διαμετακόμισης, περίπου τον Νοέμβριο του 2014

Κάνοντας αυτό ήταν σχετικά απλό: δημιουργήσαμε έναν αγωγό επεξεργασίας για να εξαγάγουμε τα σχήματα από τα δεδομένα προέλευσης. αποθηκεύει τα σχήματα σε μορφή ανταλλαγής δεδομένων. εξασφάλισε ότι τα δεδομένα ήταν διαθέσιμα στη συσκευή. και χρησιμοποίησε τις βιβλιοθήκες χαρτογράφησης της συσκευής για να σχεδιάσει ένα νέο στρώμα με τα δεδομένα.

Ανετα. Το είχαμε λειτουργήσει εντός δύο εβδομάδων.

Αλλά ενώ είναι κοντά, δεν είναι ένας πραγματικός χάρτης διαμετακόμισης. Όλες οι γραμμές είχαν σχεδιαστεί πάνω από το άλλο. Δεν μπορείτε να πείτε ποια γραμμή πηγαίνουν εκεί - και η μόνη ορατή γραμμή ήταν αυτή που τραβήχτηκε τελευταία. Για τους σωστούς διαγραμματικούς χάρτες, όπου μπορείτε να ακολουθήσετε τις γραμμές με το δάχτυλό σας, θα χρειαστείτε να σχεδιαστούν παράλληλα και να διασταυρωθούν όσο το δυνατόν λιγότερο.

2. Αντιστοίχιση με το OpenStreetMap

Η κατασκευή των χαρτών μας με σχήματα δημιουργούσε άλλα προβλήματα: τι πρέπει να κάνουμε όταν ένας οργανισμός δεν παρέχει δεδομένα σχήματος ή εάν μια αντιπροσωπεία παρέχει πολύ κακές μορφές; Τα μόνα γεωγραφικά δεδομένα που θα έχουμε στις περιπτώσεις αυτές θα είναι οι θέσεις στάσης. Σίγουρα θα μπορούσαμε να σχεδιάσουμε ευθείες γραμμές μεταξύ των στάσεων, αλλά αυτό είναι άσχημο, ακατάστατο και συγχέοντας.

Είναι επίσης το πρόβλημα με τους Χάρτες Διαμετακόμισης της Google. Στο Βερολίνο, η Google πραγματοποιεί ευθείες συνδέσεις μεταξύ στάσεων. στο Λονδίνο, χρησιμοποιούν κάποιο είδος παρεμβολής spline που δεν ακολουθεί τα πραγματικά κομμάτια. και στο Λος Άντζελες, χρησιμοποιούν τα σχήματα που παρέχει ο οργανισμός, παρόλο που η ποιότητα των σχημάτων είναι πραγματικά πολύ κακή.

Οι χάρτες Google στο Βερολίνο (αριστερά) και στο Λονδίνο (δεξιά)

Αυτό που είναι αστείο είναι ότι όταν κάνετε μεγέθυνση στους χάρτες, θα δείτε ότι η Google συχνά διαθέτει δεδομένα για τα υποκείμενα σιδηροδρομικά κομμάτια, γεγονός που προκαλεί την ερώτηση: γιατί δεν συνδυάζουν τα κομμάτια με τα δεδομένα σχήματος; Αποφάσισαν ότι δεν είναι σημαντικό;

Παρόλο που η Google ίσως να μην το θεωρεί σημαντικό, σίγουρα το κάνουμε. Σίγουρα, δεν έχουμε πρόσβαση στα πλούσια υποκείμενα δεδομένα χάρτη του Google, αλλά μπορούμε να χρησιμοποιήσουμε το επόμενο καλύτερο πράγμα: OpenStreetMap (OSM). Και χάρη στην κοινότητα εθελοντών map-geeks, ο OSM έχει σχεδόν όλες τις διαδρομές για τις γραμμές δημόσιας συγκοινωνίας που χρησιμοποιούμε στην εφαρμογή μας.

Τα δεδομένα της σιδηροδρομικής γραμμής του OpenStreetMap

Δημιουργώντας ένα σχήμα κατά μήκος του δικτύου οδού OSM που συνδέει όλα τα σημεία κατά μήκος μιας δεδομένης διαδρομής, θα μπορούσαμε να δημιουργήσουμε τα σχήματα διαμετακόμισης! Έτσι δημιουργήσαμε έναν δυναμικό αλγόριθμο προγραμματισμού ο οποίος ακολουθεί δρόμους ή διαδρομές που πιθανόν να χρησιμοποιηθούν από γραμμές διέλευσης. Ο αλγόριθμος δημιουργίας σχήματος θεωρεί τον τύπο του οχήματος που τρέχει στη γραμμή και ελαχιστοποιεί τα αντίστοιχα σφάλματα (δηλ. Τις αποστάσεις μεταξύ του παραγόμενου σχήματος και των πραγματικών θέσεων των σημείων πηγής).

Ακολουθεί ένα παράδειγμα. Στο παρακάτω διάγραμμα, έχουμε ένα ταξίδι με τρεις στάσεις, και καμία πληροφορία σχετικά με το σχήμα. Εκχυλίζουμε το σύνολο των κομματιών που χρησιμοποιεί το ταξίδι από OSM (γκρίζες γραμμές). Ο αλγόριθμος αντιστοίχισης βρίσκει έπειτα μια τροχιά (μαύρη γραμμή) που ακολουθεί το OSM, ελαχιστοποιώντας παράλληλα το μήκος και τα σφάλματα στις στάσεις (e1, e2, e3).

Η διαδικασία προσαρμογής σχήμα-OSM

Είναι δύσκολο να βρούμε αυτόν τον αλγόριθμο για όλες τις περιπτώσεις, έτσι ώστε μερικές φορές πρέπει να παρέχουμε παραμέτρους για να δουλέψουμε συγκεκριμένες γραμμές. Συνολικά, μας δίνει υψηλής ποιότητας σχήματα για όλες τις γραμμές δημόσιας συγκοινωνίας που χρειαζόμαστε σήμερα και οι περισσότερες από αυτές που θα χρειαστούμε στο μέλλον - ακόμη και στις αναπτυσσόμενες χώρες όπου ο OSM είναι συχνά τα καλύτερα διαθέσιμα δεδομένα.

Ένα παράδειγμα που παρακινεί την αντιστοίχιση OSM ακόμα και όταν υπάρχουν διαθέσιμα σχήματα και αξιοπρεπούς ποιότητας: Στο Montreal-West, τα παρεχόμενα σχήματα δεν ακολουθούν το κομμάτι (εικόνα αριστερά), έτσι στο επίπεδο του δρόμου φαίνεται τρομερό. Μετά την προσαρμογή OSM (δεξιά), οι γραμμές είναι πολύ πιο ομαλές.

3. Επεξεργασία σε Pixel Space: Σκελετοποίηση

Ο OSM μας έδωσε τα σχήματα, αλλά οι γραμμές εξακολουθούσαν να τρέχουν το ένα πάνω στο άλλο. Οι πραγματικοί χάρτες διέλευσης έχουν παράλληλες γραμμές. Αυτό που έπρεπε να κάνουμε ήταν να εντοπίσουμε τα κοινά τμήματα, όπου ταξιδεύουν στον ίδιο δρόμο και στη συνέχεια να "κουμπώσουν" αυτές τις γραμμές μαζί.

Πώς το κάνει η Google; Φαίνονται να υπολογίζουν τα κοινά τμήματα εξετάζοντας τις στάσεις. Εφόσον δύο γραμμές μοιράζονται τις ίδιες στάσεις, αυτές «κουμπώνουν» μαζί. Αλλά όταν η επόμενη στάση δεν είναι κοινή, οι γραμμές 'unsnap':

Οι γραμμές της Google ξεχνούν ότι ξέρουν ο ένας τον άλλο αμέσως στην τελευταία στάση όπου σταματούν μαζί.

Αλλά αυτό δεν είναι το πώς τα τρένα και τα λεωφορεία πραγματικά ταξιδεύουν! Οι γραμμές παραμένουν μαζί για κάποια απόσταση προτού αποκλίνουν. Αυτό που χρειαζόμασταν ήταν ένας αλγόριθμος που θα βρήκε πού θα αρχίσουν να ξεχωρίζουν οι γραμμές στην πραγματική ζωή.

Προσπαθήσαμε να υπολογίσουμε τους διαχωρισμούς διαδρομής στον διανυσματικό χώρο, ο οποίος φαινόταν απλός αρχικά: πάρτε δύο γραμμές που ταξιδεύουν από κοντά και στη συνέχεια βρείτε την κεντρική γραμμή του κοινού τμήματος. Αυτό αποδείχθηκε εκπληκτικά περίπλοκο, ωστόσο, καθώς συνεχίσαμε να τρέχουμε σε απλά παραδείγματα που θα έσπασαν τον αλγόριθμό μας. Ένας μικρός βρόχος στη διαδρομή θα ρίξει από την κεντρική γραμμή στο άπειρο, και θα χρειαζόταν επίσης να ασχοληθούμε με πολλαπλές γραμμές, πολλαπλούς κλάδους, διαφορετικά στάδια ...

Μετά από δύο μήνες από το να βάλουμε το μυαλό μας στα πληκτρολόγια μας, πέταξα τελικά στην πετσέτα. Δεν μπορούσαμε να βρούμε μια σταθερή, γενική λύση που θα μπορούσε να λειτουργήσει αξιόπιστα, έως ότου ...

Pixel χώρο για τη διάσωση!

Αντί να επεξεργαστούμε τις γραμμές σε διανυσματικό χώρο, αποφασίσαμε να δοκιμάσουμε κάτι τρελό. Χρησιμοποιήσαμε χώρο pixel.

Συνήθως η επεξεργασία με βάση τα pixel γίνεται για δεδομένα με βάση την εικόνα. Είναι πολύ ασυνήθιστο για την επεξεργασία GIS, επειδή με ανάλυση 1px / meter, η εικόνα μας θα ήταν 64 terabytes. Η μνήμη είναι φτηνή αυτές τις μέρες ... αλλά όχι τόσο φθηνή!

Τόσο πώς το κάναμε; Εφαρμόσαμε μια ειδική αραιή βιβλιοθήκη εικόνων που θα μπορούσε να ασχοληθεί με αυτές τις πολύ μεγάλες μονοχρωματικές εικόνες με σχετικά λίγες λευκές περιοχές.

Στη συνέχεια δημιουργήσαμε έναν αλγόριθμο για να σχεδιάσουμε σχήματα διαμετακόμισης σε ένα γιγαντιαίο ασπρόμαυρο καμβά που αντιπροσωπεύει ολόκληρο τον κόσμο, όπου κάθε εικονοστοιχείο είναι ισοδύναμο με ένα τετραγωνικό μέτρο. Κάθε γραμμή τραβούσε παχιά πάνω στον καμβά, οπότε οπουδήποτε οι γραμμές ήταν κοντά, τα εικονοστοιχεία τους συγχωνεύονταν.

Μόλις τραβήχτηκαν όλες οι γραμμές, χρησιμοποιήσαμε μια διαδικασία "σκελετοποίησης" για να διαστρεβλώνουμε διαδοχικά τις γραμμές έως ότου ο καθένας είχε πάχος μόνο ενός εικονοστοιχείου. Έτσι, ενώ οι γραμμές δεν συγχωνεύονταν πλέον, έμειναν συνδεδεμένες, διατηρώντας την ίδια τοπολογία. Αυτές οι λεπτές γραμμές αντιπροσωπεύουν όπου οι γραμμές διέλευσης ταξιδεύουν μαζί, και αποκαλύπτουν τη δομή του δικτύου.

Το άσπρο αντιπροσωπεύει τις γραμμές διέλευσης. Ο «σκελετός» επικαλύπτεται με κόκκινο χρώμα.

Παρόλο που είχαμε τώρα τις κεντρικές γραμμές του δικτύου, είχαμε καταστρέψει περισσότερες πληροφορίες από ό, τι κερδίσαμε. Αυτό που είχαμε τώρα ήταν μια δέσμη εικονοστοιχείων που δηλώνει τον σκελετό, πράγμα που σημαίνει ότι γνωρίζαμε ότι κάθε γραμμή πρέπει να ταξιδεύει κατά μήκος αυτού του σκελετού, αλλά έπρεπε ακόμα να καταλάβουμε ποιες γραμμές ταξιδεύουν εκεί.

Χρησιμοποιώντας τον σκελετό, ξαναχτίσαμε τις γραμμές, σε αντίθεση με τα σχήματα που είχαμε προηγουμένως. Στη συνέχεια επεξεργαζόμαστε το δίκτυο που προκύπτει για να απαλλαγούμε από τις δυσλειτουργίες που εισάγονται από τον σκελετό.

Αυτό το βήμα ήταν μακρύ και κουραστικό. Συνολικά, η σχεδίαση, ο σκελετοποίηση, η οικοδόμηση δικτύου και η αφαίρεση σφαλμάτων χρειάστηκαν περίπου έξι μήνες για να αναπτυχθούν. (Τόσο για το ότι το όλο πράγμα έγινε σε τρία!)

Αλλά τα τελικά αποτελέσματα ήταν ικανοποιητικά. Είχαμε μια εσωτερική αναπαράσταση γραμμών που ταξιδεύουν μαζί και αποκλίνουν. Φαινόταν έτσι:

Όταν κάναμε τις γραμμές παράλληλα, το πήραμε:

Επιτυχία!

Πολύ καλό για μια έκδοση 1. Πολύ καλύτερα από το Google, βλέποντας όπως μπορείτε περισσότερο ή λιγότερο να διδάξετε έξω από όπου κάθε γραμμή πηγαίνει. Ήμασταν έτοιμοι να εγκαταστήσουμε τους Transit Maps! Και στη συνέχεια ... έγιναν οι Χάρτες της Apple.

Το καλοκαίρι του 2015, αφού εργαστήκαμε στους χάρτες μας για το μεγαλύτερο μέρος του έτους, ήμασταν τελικά έτοιμοι να κυκλοφορήσουμε την πρώτη μας έκδοση των Χαρτών Διαμετακόμισης. Στη συνέχεια η Apple έβαλε τους χάρτες διαμετακόμισης και ήταν πολύ όμορφοι.

Οι όμορφοι χάρτες διέλευσης της Apple

Ανυψώσανε αμέσως τη μπάρα για το τι πρέπει να μοιάζουν οι χάρτες διαμετακόμισης. Στα σχέδια και τα σχέδιά μας, ο τελικός στόχος ήταν κάτι παρόμοιο με (ή καλύτερα από) αυτό που ακολούθησε η Apple, αλλά σχεδίαζαμε να φτάσουμε εκεί μετά την απελευθέρωση της έκδοσης 1.

Σε σύγκριση με την Apple, η προτεινόμενη έκδοση 1 ήταν κάπως μέτρια. Ο σχεδιαστής-διευθύνων σύμβουλός μας δήλωσε ότι η νίκη της Google δεν ήταν αρκετά καλή - έπρεπε επίσης τουλάχιστον να παίξουμε στο ίδιο πρωτάθλημα με την Apple.

Μετά από προσεκτικότερη εξέταση, υποθέσαμε ότι η Apple σχεδίαζε τους χάρτες τους χειροκίνητα. Υπήρχαν τεράστιες καθυστερήσεις μεταξύ της απελευθέρωσης νέων πόλεων και υπήρχε κάτι παράξενο για τον τρόπο που φαίνονταν οι χάρτες - σαν να είχαν τραβηχτεί από ανθρώπους, όχι υπολογιστές. Αυτό σήμαινε ότι παρόλο που οι χάρτες μας δεν ήταν αρκετά ωραίοι, ο αλγόριθμός μας ήταν ακόμα μπροστά από τον δικό τους.

Σε αυτό το σημείο, γνωρίζαμε επίσης ότι το σκληρό μέρος ήταν πίσω μας. Είχαμε βρει ένα δίκτυο που θα μας επέτρεπε να σχεδιάζουμε γραμμές παράλληλα. Τώρα, το μόνο που έπρεπε να κάνουμε ήταν να φανεί καλό.

4. Παραγγελία Γραμμής Διαμεταγωγής χρησιμοποιώντας Αλληλουργικό Γραμμικό Προγραμματισμό

Πριν δημοσιεύσουμε τους χάρτες μας, χρειαζόμασταν να απαλλαγούμε από την άσχημη, περιττή διασταύρωση των γραμμών, η οποία τους μετατρέπει σε τρομακτικό σπαγγέτι.

Εάν μπορούσαμε να ταξινομήσουμε τις γραμμές για να ελαχιστοποιήσουμε την οπτική ακαταστασία κοντά στις διασταυρώσεις, θα είχαμε έναν χάρτη με δυνατότητα δημοσίευσης. Για να γίνει αυτό, έπρεπε να αποφασίσουμε ποιες γραμμές θα πήγαιναν αριστερά και ποιες θα πήγαιναν σωστά, προκειμένου να ελαχιστοποιηθούν οι διασταυρώσεις τους.

Η Google είχε (και εξακολουθεί να έχει) ένα παρόμοιο πρόβλημα - εκτός από τις γραμμές που διασχίζουν μεταξύ τους ακόμη και όταν υπάρχουν μόνο στάσεις και δεν υπάρχουν διασταυρώσεις.

Ω, έλα στο Google! Οι γραμμές πρέπει να παραμείνουν οργανωμένες.

Για εμάς, η διασταύρωση έγινε μόνο όταν οι γραμμές εντάχθηκαν και αποκλίνονταν, γι 'αυτό κάναμε ήδη καλύτερα από τον αλγόριθμο της Google. Αυτό συμβαίνει επειδή αποθηκεύσαμε κοινά τμήματα με βάση τη γεωγραφία.

Πώς λοιπόν ξεφορτώσαμε τα μακαρόνια; Πρώτον, δοκιμάσαμε μια ευρετική λύση - γραμμές διαλογής με βάση το πού τελειώνουν - αλλά αυτό συχνά απέτυχε, δουλεύοντας σε ορισμένα μέρη, αλλά όχι σε άλλους.

Για να βελτιώσουμε την ευρετική λύση, δημιουργήσαμε ένα μαθηματικό μοντέλο που θα «βαθμολογούσε» μια συγκεκριμένη παραγγελία γραμμών, επιβάλλοντας κυρώσεις στη διέλευση γραμμών, καθώς και άλλες οπτικές ακαταστασίες.

Αρκετά πιθανά σενάρια διασταύρωσης, σηματοδοτώντας πηγές κυρώσεων χρησιμοποιώντας κόκκινους κύκλους

Όπως θα περίμενε κανείς, αποφεύγοντας μια διασταύρωση σε ένα μέρος του χάρτη θα μπορούσε να δημιουργήσει ένα άλλο κάπου αλλού. Όλα είναι συνδεδεμένα! Τι κάναμε λοιπόν; Βρήκαμε την παραγγελία γραμμών που είχαν το χαμηλότερο σκορ σε παγκόσμιο επίπεδο.

Ο ακέραιος-γραμμικός προγραμματισμός μας επέτρεψε να διερευνήσουμε όλες τις δυνατότητες και να βρούμε μια λύση που ελαχιστοποίησε σε παγκόσμιο επίπεδο τη λειτουργία ποινής. Αλλά ο χρόνος επεξεργασίας για τον ακέραιο-γραμμικό προγραμματισμό είναι εκθετικός στο μέγεθος του προβλήματος: η επίλυση ενός προβλήματος μπορεί να διαρκέσει ένα δευτερόλεπτο. ένα άλλο πιο δύσκολο πρόβλημα μπορεί να διαρκέσει ένα χρόνο! Αυτό το καθιστούσε επικίνδυνο για χρήση, ακόμα και στην προετοιμασία 'offline' στο εσωτερικό του backend.

Ανησυχθήκαμε. Η επεξεργασία των δεδομένων του Σικάγο μας πήρε ώρες. Μια ευρύτερη περιοχή όπως ο Βορειοανατολικός Διάδρομος (Βοστώνη στην Ουάσιγκτον) μπορεί να πάρει εβδομάδες! Ευτυχώς, βρήκαμε ένα διαφορετικό σχέδιο επίθεσης: αυτό που επέτρεψε στον ολοκληρωτικό-γραμμικό προγραμματιστή λύσης να διερευνήσει πιο αποτελεσματικά τον χώρο προβλημάτων και να βρει ταχύτερα τις βέλτιστες λύσεις. Αυτό που πήρε προηγουμένως μια ώρα, πήρε τώρα 0,2 δευτερόλεπτα.

Βλέποντας τη βελτιστοποίηση όπως αυτή στη δράση είναι εκπληκτική: όταν βλέπετε τον αλγόριθμο να παίρνετε αποφάσεις, είναι σαν να βλέπετε έναν λαμπρό μαθηματικό να επιλύει αβίαστα προβλήματα με τις σαφέστερες, πιο συνοπτικές λύσεις.

Πριν / Μετά τη Ταξινόμηση Γραμμών

Με τα άλλα βήματα επεξεργασίας που έχουν ήδη ολοκληρωθεί στην προεπεξεργασία στο διακομιστή, τα δεδομένα αποθηκεύτηκαν τώρα σε δυαδικά αρχεία και αποστέλλονται στη συσκευή για την πραγματική απόδοση χαρτών σε οποιοδήποτε επιθυμητό επίπεδο ζουμ.

5. Στρογγυλοποίηση των Γραμμών με Circle-Arc

Εντούτοις, δεν ήμασταν τελείως τελειωμένοι. Οι διαγραμμένοι χάρτες διάγραμμα διαμετακόμισης εξακολουθούν να μην μοιάζουν με τους χάρτες που παρουσιάζονται παραπάνω. Οι γραμμές τους είναι ωραία στρογγυλεμένες με ομαλές μεταβάσεις σε διασταυρώσεις. Θέλαμε τους χάρτες μας να έχουν μια παρόμοια στρογγυλή εμφάνιση.

Όταν γραμμές που εντοπίστηκαν γύρω από τις γωνίες, θέλαμε να παραμείνουν τέλεια παράλληλες, ακόμη και σε πιθανώς εκφυλιστικές περιπτώσεις, όπως στο Σικάγο. Εκεί, ένας μεγάλος αριθμός γραμμών ταξιδεύει μαζί γύρω από αιχμηρές καμπύλες, οπότε η σύλληψή τους παράλληλα θα μπορούσε να οδηγήσει σε γραμμές που συσσωρεύονται στο εσωτερικό της κάμψης.

Συνήθως, η στρογγυλοποίηση γίνεται με καμπύλες Bezier, οι οποίες μοιάζουν σαν να χαλαρώνουν στις καμπύλες. Αλλά για να παραμείνουν πιστές στην εμφάνιση διαγραμμάτων χαρτών διαμετακόμισης, οι καμπύλες Bezier δεν ήταν σωστές. Οι χάρτες διέλευσης έχουν ευθείες γραμμές που πέφτουν απότομα σε τμήματα κυκλικού τόξου. Έτσι χρησιμοποιήσαμε τμήματα τόξου για στρογγυλοποίηση.

Επίσης, σε αντίθεση με τις καμπύλες Bezier, οποιαδήποτε γραμμή παράλληλη με ένα τόξο κύκλου είναι η ίδια ένα τόξο κύκλου. Εφόσον η ακτίνα είναι αρκετά μεγάλη, μας εγγυόταν ότι δεν έχουμε εκφυλιστικές περιπτώσεις.

Καταλήξαμε με έναν προσαρμοσμένο αλγόριθμο ο οποίος, δεδομένου ενός σχήματος, θα αφαιρέσει και θα προσθέσει σημεία για να το στρογγυλοποιήσει χρησιμοποιώντας τμήματα κυκλικού τόξου. Εξασφαλίζει μια δεδομένη ελάχιστη ακτίνα απλοποιώντας τη γεωμετρία όπως είναι απαραίτητο. Η ελάχιστη ακτίνα εξαρτάται από το συνολικό πλάτος όλων των παράλληλων γραμμών.

Το προκύπτον σχήμα είναι ομαλό. Αποτελείται εξ ολοκλήρου από ευθείες γραμμές και τμήματα τόξου, πράγμα που σημαίνει ότι μπορούμε πάντα να τραβήξουμε παράλληλα γραμμές παράλληλα χωρίς αντικείμενα ή εκφυλιστικά περιστατικά.

Αυτή η προσέγγιση μας έδωσε κάτι τέτοιο:

Η στρογγυλοποίηση γίνεται μόνο σε κοινόχρηστα τμήματα. Ενδέχεται επίσης να παρατηρήσετε ότι καταργήσαμε όλες τις διασταυρώσεις. Η ενασχόληση με τις διασταυρώσεις ήταν ένα σημαντικό πρόβλημα, επειδή έπρεπε να διασφαλίσουμε ότι κάθε γραμμή θα συνέχιζε από το ένα τμήμα στο επόμενο και θα συνδεόταν σωστά. Χρησιμοποιήσαμε επίσης τον αλγόριθμο δημιουργίας τόξου για να έχουμε την ίδια στρογγυλή εμφάνιση. Εδώ είναι το τελικό αποτέλεσμα:

Πολύ ωραία, σωστά; Αλλά ενώ ήταν αρκετά ... εξακολουθούσαν να φαίνονται περίεργα γυμνοί. Αυτό συμβαίνει επειδή έλειπαν στάσεις.

Έτσι, αποφασίσαμε να κρατήσουμε την απελευθέρωση ξανά - και να προσθέσουμε ένα τελευταίο βήμα.

6. Προσθήκη Σταματά

Η προσθήκη αναστολέων μπορεί να φαίνεται απλή, αλλά στην πραγματικότητα απαιτεί μια δίκαιη ποσότητα επεξεργασίας για τη διάδοση των πληροφοριών στάσης μέσω του μακρού αγωγού που δημιουργήσαμε.

Συναντήσαμε επίσης πολλές περιπτώσεις όπου οι πολλαπλές στάσεις στα δεδομένα αντιστοιχούσαν στην πραγματικότητα σε ένα μόνο φυσικό σταθμό, οπότε χρειαζόμασταν να τα καταργήσουμε σε μία στάση.

Εδώ τι κάναμε. Για στάσεις με πολλαπλές γραμμές, τραβήξαμε μια λευκή ράβδο με μαύρο περίγραμμα (για αντίθεση) σε όλες τις γραμμές. Για στάσεις σε μια γραμμή, σχεδιάσαμε έναν απλό κύκλο χρησιμοποιώντας το χρώμα της συγκεκριμένης γραμμής διέλευσης. Προσθέσαμε επίσης μια λευκή επικάλυψη για να μειώσουμε την αντίθεση του στρώματος χάρτη παρακάτω. Αυτό είναι το τελικό αποτέλεσμα:

Για να επιτρέπεται στους χρήστες να ενεργοποιούν επιλεκτικά τις γραμμές από τη σελίδα ρυθμίσεων των εφαρμογών μας, αποφασίσαμε ότι η στρογγυλοποίηση, καθώς και κάποια επεξεργασία και τερματισμός θα πρέπει να γίνονται στη συσκευή. Έτσι, στη Νέα Υόρκη, μπορείτε να απενεργοποιήσετε όλες τις γραμμές διαμετακόμισης με βάση το Νιου Τζέρσεϋ (ή όλες τις γραμμές της Νέας Υόρκης εάν ζείτε στο New Jersey). Με τόσες γραμμές διέλευσης σε ορισμένες περιοχές, αυτό επιτρέπει στους χρήστες να δημιουργούν πλήρως προσαρμοσμένους χάρτες.

Σημειώστε πώς οι γραμμές επανεμφανίζονται βάσει της γραμμής που είναι ενεργή και πως η στάση αλλάζει χρώμα.

συμπέρασμα

Έτσι έτσι το κάναμε. Σίγουρα, η εφαρμογή αυτοματοποιημένων χαρτών διαμετακόμισης χρειάστηκε πολλή δουλειά, αλλά αξίζει τον κόπο. Οι χάρτες μας είναι πολύ πιο ισχυροί από τα αρχεία PDF που συνηθίζατε να παίρνετε από τους οργανισμούς, δεν έχει σημασία το χαρτί που αναδιπλώνετε και το μαρμελάρετε στο πορτοφόλι σας. Ποιες είναι οι κύριες διαφορές;

Οι Χάρτες Διαμετακόμισης μας είναι κλιμακωτές, ώστε να μπορούμε εύκολα να προσθέτουμε νέες πόλεις με το ίδιο οπτικό στυλ, οπουδήποτε στον κόσμο θα επεκταθούμε στην επόμενη. Είναι προσαρμόσιμα, ώστε οι χρήστες να μπορούν να ενεργοποιούν / απενεργοποιούν δίκτυα και λειτουργίες για να δημιουργούν τους δικούς τους εξατομικευμένους χάρτες διαμετακόμισης. Και είναι επίσης συμφραζόμενα: αντίθετα από ένα PDF ενός χάρτη αντιπροσωπείας, οι χάρτες μας ενσωματώνουν την τοποθεσία σας δίνοντάς σας μια αίσθηση του πού βρίσκεστε σε σχέση με τις κοντινές γραμμές και προσαρμόζοντας το βλέμμα ανάλογα με το επίπεδο ζουμ σας.

Και τελικά, οι διαγραμμικοί χάρτες διαμετακόμισης δεν παρέχουν μόνο τις βασικές πληροφορίες για τα συστήματα διαμετακόμισης. Είναι έμβλημα των ίδιων των πόλεων: σημαντικά κομμάτια λειτουργικής τέχνης που συνδέουν τους ανθρώπους με το περιβάλλον τους. Θέλουμε να βοηθήσουμε στη δημιουργία αυτής της σύνδεσης και πιστεύουμε ότι οι νέοι μας Χάρτες Διαμετακόμισης κάνουν ακριβώς αυτό.

Είμαστε ενθουσιασμένοι που συνεχίζουμε να βελτιώνουμε, αλλά είμαστε ευχαριστημένοι με αυτό που έχουμε επιτύχει μέχρι στιγμής. Ξεκινήσαμε με 55 πόλεις. Η απάντηση στην ανάρτησή μας στο blog που συγκρίνει τους χάρτες μας με τα Google και την Apple ήταν απίστευτα θετική. Για την ομάδα backend, είναι υπέροχο να βλέπουμε και να εκτιμούμε το έργο και την προσπάθεια που βάζουμε σε αυτό που οδηγεί την εμπειρία της εφαρμογής. Μας ενθαρρύνει να συνεχίσουμε να προωθούμε περαιτέρω την τεχνολογία μας.

Πέρα από αυτό, εξακολουθούμε να έχουμε πολλά ακόμα «σκληρά» προβλήματα για να λύσουμε. Θα συνεχίσουμε να δουλεύουμε κάτω από την κουκούλα, όχι μόνο για να έχουμε την ωραιότερη εφαρμογή με το καλύτερο UI, αλλά την πιο λειτουργική, ισχυρή και ακριβή εφαρμογή διέλευσης εκεί έξω.

Θέλετε να παίξετε με τους χάρτες μας;
Μπορείτε να λάβετε δωρεάν το Transit στο App Store και στο Google Play. Ή μάθετε περισσότερα για την εταιρεία στην ιστοσελίδα μας.

Νιώστε σαν να αντιμετωπίζετε προκλήσεις όπως αυτό για να ζήσετε; Προσλαμβάνουμε!