Un seguimiento técnico: cómo construimos los mapas de tránsito autogenerados más bonitos del mundo

por Anton Dubrau

Hace seis semanas, lanzamos Transit Maps y escribimos esta publicación de blog sobre por qué asumimos la gigantesca tarea de crear mapas generados automáticamente pero estéticamente agradables. Nos sorprendió la reacción pública a nuestros esfuerzos, aunque no nos sorprendió del todo el tiempo, el pensamiento y la inspiración que llevó crearlos. Hoy, estamos cumpliendo nuestra promesa de publicar un seguimiento técnico de Anton, nuestro asistente de mapeo residente, quien explica con mucho más detalle lo que fue necesario para construir estos mapas.

Cuando piensa en Transit, puede pensar en una interfaz elegante y colorida. Dado que somos extremadamente particulares acerca de hacer que la aplicación sea lo más bella y utilizable posible, no es una gran sorpresa. Pero la IU no es lo único de lo que se trata: nuestro equipo se extiende mucho más allá de los diseñadores expertos, y nuestra aplicación es mucho más que simplemente bonita. Debajo de la superficie, hay una gran cantidad de tecnología "dura" que lo conduce silenciosamente.

Primero, nuestra potente calidad de backend verifica cientos de fuentes de datos de tránsito, corrige automáticamente los datos rotos y marca los problemas que necesitan investigación. Este sistema nos permite administrar 350 transmisiones de tránsito en 125 ciudades con un equipo pequeño.

Luego está nuestro algoritmo de compresión. Reduce los horarios de tránsito hasta 100 veces más pequeños que los archivos zip que proporcionan las agencias de tránsito. Esto permite que Transit descargue los horarios de toda la región del usuario, almacene los datos en el dispositivo del usuario y devuelva los resultados de búsqueda ... todo en el tiempo que le toma a otras aplicaciones solicitar y cargar un solo horario. Y aunque nuestros usuarios ahora pueden estar acostumbrados a la velocidad de nuestra aplicación, cuando se introdujo la función por primera vez, efectivamente redujo el tiempo de respuesta de varios segundos a 0.1 segundos. Eso es rápido.

Pero hay una tecnología en particular en la que hemos estado trabajando durante años. Para nuestra gran alegría (y alivio), finalmente lo lanzamos este verano: mapas de tránsito generados automáticamente.

Transit Maps: aplicación Transit (izquierda), Apple Maps (centro) y Google Maps (derecha)

La idea en sí no es nueva: Google lanzó sus mapas de tránsito hace casi seis años. Pero resulta que es un problema bastante difícil de resolver, y Google (incluso después de todos estos años) todavía no puede generar mapas de tránsito muy bonitos o incluso muy útiles.

Entonces, ¿cómo lo logramos? Con sudor, lágrimas y pensamiento creativo.

1. Formas en un mapa

La idea de crear mapas generados automáticamente es algo que me ha cautivado desde antes de unirme a la aplicación Transit hace tres años. En ese momento, Google era el único jugador en la industria, y para ser sincero, sus mapas de tránsito eran un poco malos. Acabábamos de terminar nuestro algoritmo de súper compresión antes mencionado y nos sentíamos listos para enfrentar un nuevo problema. Pensamos, ingenuamente, que tomaría unos tres meses. Poco sabíamos ...

El primer paso fue mostrar los datos de origen en un mapa. Muchos de los viajes en los datos de tránsito subyacentes ya contenían formas que representan las rutas que tomaron los vehículos de tránsito. Si simplemente dibujáramos todas las formas definidas por todos los viajes, obtendríamos una especie de mapa de tránsito simplista:

Nuestra tecnología de mapas de tránsito, alrededor de noviembre de 2014

Hacer esto fue relativamente simple: configuramos una tubería de procesamiento para extraer las formas de los datos de origen; almacenó las formas en un formato de intercambio de datos; se aseguró de que los datos estuvieran disponibles para el dispositivo; y usé las bibliotecas de mapeo del dispositivo para dibujar una nueva capa con los datos.

Fácil. Tuvimos esto en funcionamiento en un par de semanas.

Pero aunque está cerca, no es un mapa de tránsito real. Todas las líneas fueron dibujadas una encima de la otra. No puede decir qué líneas van a dónde, y la única línea visible fue la que se dibujó la última. Para obtener mapas esquemáticos adecuados donde pueda seguir las líneas con el dedo, necesitará que se dibujen en paralelo y se crucen lo menos posible.

2. Coincidencia con OpenStreetMap

Construir nuestros mapas con formas planteaba otros problemas: ¿qué deberíamos hacer cuando una agencia no proporciona datos de formas o si una agencia proporciona formas muy pobres? Los únicos datos geográficos que tendríamos en esos casos serían las ubicaciones de las paradas. Claro, podríamos dibujar líneas rectas entre las paradas, pero eso es feo, desordenado y confuso.

También es el problema con los mapas de tránsito de Google. En Berlín, Google realiza conexiones en línea recta entre paradas; en Londres, usan algún tipo de interpolación spline que no sigue las pistas reales; y en LA, usan las formas proporcionadas por la agencia a pesar de que la calidad de las formas es realmente bastante mala.

Google Maps en Berlín (izquierda) y Londres (derecha)

Lo curioso es que cuando haces zoom en los mapas, verás que Google a menudo tiene datos para las vías del ferrocarril subyacentes, lo que plantea la pregunta: ¿por qué no combinan las pistas con los datos de la forma? ¿Decidieron que no es importante?

Si bien Google podría no pensar que es importante, ciertamente lo hacemos. Claro, no tenemos acceso a los ricos datos de mapas subyacentes de Google, pero podemos usar la siguiente mejor opción: OpenStreetMap (OSM). Y gracias a su comunidad de geeks de mapas voluntarios, OSM tiene prácticamente todas las vías para las líneas de ferrocarril de transporte público que utilizamos en nuestra aplicación.

Los datos ferroviarios de OpenStreetMap

¡Al crear una forma a lo largo de la cuadrícula de la calle OSM que conecta todos los puntos a lo largo de una ruta determinada, podríamos generar nuestras formas de tránsito! Así que creamos un algoritmo de programación dinámico que sigue caminos o pistas que pueden ser utilizadas por las líneas de tránsito. El algoritmo de creación de formas considera qué tipo de vehículo corre en la línea y minimiza los errores de coincidencia (es decir, las distancias entre la forma generada y las ubicaciones reales de los puntos de origen).

Aquí hay un ejemplo. En el diagrama a continuación, tenemos un viaje con tres paradas, y ninguna información de forma. Extraemos el conjunto de pistas que utiliza el viaje de OSM (líneas grises). Nuestro algoritmo de coincidencia luego encuentra una trayectoria (línea negra) que sigue el OSM, mientras minimiza su longitud y los errores hasta las paradas (e1, e2, e3).

El proceso de coincidencia de forma-OSM

Es difícil hacer que este algoritmo funcione en todos los casos, por lo que a veces, tenemos que proporcionar parámetros para que funcionen líneas específicas. En general, nos da formas de alta calidad para todas las líneas de transporte público que necesitamos hoy, y la mayoría de las que necesitaremos en el futuro, incluso en países en desarrollo donde OSM es a menudo la mejor información disponible.

Un ejemplo que motiva la coincidencia de OSM incluso cuando hay formas disponibles y de buena calidad: en Montreal-West, las formas proporcionadas no siguen la pista (imagen a la izquierda), por lo que a nivel de la calle se ve terrible. Después de la coincidencia de OSM (derecha), las líneas son mucho más suaves.

3. Procesamiento en Pixel Space: esqueletización

OSM nos dio las formas, pero las líneas todavía se dibujaban una encima de la otra. Los mapas de tránsito reales tienen líneas dibujadas en paralelo. Lo que teníamos que hacer era identificar segmentos comunes, dónde viajaban en la misma calle, y luego "juntar" esas líneas.

Entonces, ¿cómo lo hace Google? Parecen calcular segmentos compartidos mirando las paradas. Siempre y cuando dos líneas compartan las mismas paradas, se "juntan". Pero cuando la siguiente parada no se comparte, las líneas "unsnap":

Las líneas de Google olvidan que se conocen de inmediato en la última parada donde se detienen juntos.

¡Pero no es así como viajan realmente los trenes y autobuses! Las líneas permanecen juntas por cierta distancia antes de divergir. Lo que necesitábamos era un algoritmo que encontrara dónde las líneas comienzan a ramificarse en la vida real.

Intentamos calcular las separaciones de ruta en el espacio vectorial, lo que parecía simple al principio: tomar dos líneas que viajan juntas y luego encontrar la línea central del segmento compartido. Sin embargo, esto resultó ser sorprendentemente complicado, ya que seguimos encontrando ejemplos simples que romperían nuestro algoritmo. Un pequeño bucle en la ruta arrojaría desde la línea central hasta el infinito, y también necesitábamos lidiar con múltiples líneas, múltiples ramas, diferentes patrones de parada ...

Después de dos meses de golpear nuestros cerebros contra nuestros teclados, finalmente tiramos la toalla. Simplemente no pudimos encontrar una solución estable y general que funcionara de manera confiable, hasta ...

¡Espacio de píxeles al rescate!

En lugar de procesar las líneas en el espacio vectorial, decidimos probar algo loco. Utilizamos el espacio de píxeles.

Por lo general, el procesamiento basado en píxeles se realiza para datos basados ​​en imágenes. Es muy inusual para el procesamiento de SIG, porque a una resolución de 1 px / metro, nuestra imagen sería de 64 terabytes. La memoria es barata en estos días ... ¡pero no tan barata!

Entonces, ¿cómo lo hicimos? Implementamos una biblioteca especial de imágenes dispersas que podría manejar estas imágenes monocromáticas muy grandes con relativamente pocas áreas blancas.

Luego creamos un algoritmo para dibujar formas de tránsito en un lienzo gigante en blanco y negro que representa el mundo entero, donde cada píxel es equivalente a un metro cuadrado. Cada línea se dibujaba gruesa en el lienzo, por lo que dondequiera que las líneas estuvieran cerca, sus píxeles se fusionaron.

Una vez que se dibujaron todas las líneas, usamos un proceso de "esqueletización" para adelgazar sucesivamente las líneas hasta que cada una tuviera solo un píxel de espesor. Entonces, aunque las líneas ya no se fusionaron, se mantuvieron conectadas, manteniendo la misma topología. Estas líneas finas representan el lugar donde las líneas de tránsito viajan juntas y revelan la estructura de la red.

El blanco representa las líneas de tránsito dibujadas. El

Aunque ahora teníamos las líneas centrales de la red, habíamos destruido más información de la que habíamos obtenido. Lo que teníamos ahora era un montón de píxeles que denotaban el esqueleto, lo que significaba que sabíamos que cada línea debía viajar a lo largo de este esqueleto, pero aún teníamos que averiguar qué líneas viajaban hacia dónde.

Usando el esqueleto, ahora reconstruimos las líneas, a diferencia de las formas que teníamos anteriormente. Luego procesamos la red resultante para deshacernos de los problemas técnicos introducidos por la esqueletización.

Este paso fue largo y tedioso. En total, el dibujo, la esqueletización, la creación de redes y la eliminación de fallas demoraron alrededor de seis meses en desarrollarse. (¡Tanto por tener todo hecho en tres!)

Pero los resultados finales fueron satisfactorios. Teníamos una representación interna de líneas que viajaban juntas y divergían. Se veía así:

Cuando renderizamos las líneas en paralelo, obtuvimos esto:

¡Éxito!

Bastante bueno para una Versión 1. Mucho mejor que Google, ya que puedes averiguar más o menos dónde va cada línea. ¡Estábamos listos para lanzar Mapas de tránsito! Y luego ... sucedió Apple Maps.

En el verano de 2015, después de haber trabajado en nuestros mapas durante la mayor parte del año, finalmente estábamos listos para lanzar nuestra primera versión de Transit Maps. Luego Apple lanzó sus mapas de tránsito, y eran realmente bonitos.

Bonitos mapas de tránsito de Apple

Al instante elevaron el listón de cómo deberían ser los mapas de tránsito. En nuestros dibujos y diseños, el objetivo final era algo similar (o mejor que) a lo que Apple lanzó posteriormente, pero estábamos planeando llegar allí después de lanzar nuestra Versión 1.

En comparación con Apple, nuestra Versión 1 propuesta fue un poco mediocre. Nuestro Diseñador-CEO decretó que vencer a Google no era lo suficientemente bueno, también teníamos que jugar al menos en la misma liga que Apple.

Después de un escrutinio más detallado, planteamos la hipótesis de que Apple estaba dibujando sus mapas manualmente. Hubo grandes retrasos entre el lanzamiento de nuevas ciudades, y había algo extrañamente extraño en el aspecto de los mapas, como si fueran dibujados por humanos, no por computadoras. Esto significaba que, aunque nuestros mapas no eran tan bonitos, nuestro algoritmo todavía estaba por delante del suyo.

En este punto, también sabíamos que la parte difícil había quedado atrás. Habíamos descubierto una red que nos permitiría dibujar líneas en paralelo. Ahora, todo lo que teníamos que hacer era que se viera bien.

4. Orden de líneas de tránsito usando programación lineal entera

Antes de publicar nuestros mapas, necesitábamos deshacernos del feo e innecesario cruce de líneas, que los estaba convirtiendo en un espantoso desastre de espagueti.

Si pudiéramos clasificar las líneas para minimizar el desorden visual cerca de las intersecciones, tendríamos un mapa publicable. Para hacer esto, tuvimos que decidir qué líneas irían a la izquierda y cuáles irían a la derecha, para minimizar sus cruces.

Google tenía (y aún tiene) un problema similar, excepto que sus líneas se entrecruzan incluso cuando solo hay paradas y no hay intersecciones.

¡Oh, vamos en Google! Las líneas deben mantenerse organizadas.

Para nosotros, el entrecruzamiento solo ocurrió cuando las líneas realmente se unieron y divergieron, por lo que ya estábamos mejor que el algoritmo de Google. Eso es porque estábamos almacenando secciones compartidas basadas en la geografía.

Entonces, ¿cómo nos deshacemos de los espaguetis? Primero, probamos una solución heurística: ordenar las líneas en función de dónde terminan, pero esto a menudo fallaba, trabajando en algunos lugares, pero no en otros.

Para mejorar la solución heurística, creamos un modelo matemático que 'puntuaría' un orden dado de líneas, penalizando el cruce de líneas, así como otro desorden visual.

Varios escenarios de intersección posibles, que marcan las fuentes de penalizaciones usando círculos rojos

Como es de esperar, evitar un cruce en un lugar del mapa podría crear otro en otro lugar. ¡Todo está conectado! entonces, ¿qué hicimos? Encontramos el orden de las líneas que tenían el puntaje de penalización global más bajo.

La programación lineal entera fue lo que nos permitió explorar todas las posibilidades y encontrar una solución que minimizara globalmente la función de penalización. Pero el tiempo de procesamiento para la programación lineal entera es exponencial en el tamaño del problema: resolver un problema puede tomar un segundo; ¡Otro problema más difícil puede llevar un año! Eso hizo que su uso fuera riesgoso, incluso en el preprocesamiento "fuera de línea" dentro del back-end.

Estábamos preocupados. Procesar los datos de Chicago nos llevó horas. ¡Un área más grande como el Corredor Noreste (Boston a Washington) podría tomar semanas! Afortunadamente, encontramos un plan de ataque diferente: uno que permitía al solucionador de programación lineal-entera explorar el espacio del problema de manera más eficiente y encontrar soluciones óptimas más rápido. Lo que antes tomaba una hora, ahora tomó 0.2 segundos.

Ver una optimización como esta en acción es sorprendente: cuando ve que el algoritmo toma decisiones, es como presenciar a un matemático brillante que resuelve sin problemas los problemas con las soluciones más claras y concisas.

Clasificación de línea antes / después

Con los otros pasos de procesamiento ya completados en el preprocesamiento en el servidor, los datos ahora se almacenaron en archivos binarios y se enviaron al dispositivo para la representación real de los mapas en cualquier nivel de zoom deseado.

5. Redondeo círculo-arco de líneas

Sin embargo, todavía no habíamos terminado. Los mapas de tránsito esquemáticos dibujados a mano realmente no se parecen a los mapas que se muestran arriba. Sus líneas están bien redondeadas con transiciones suaves en las intersecciones. Queríamos que nuestros mapas tuvieran un aspecto redondeado similar.

Cuando las líneas trazadas alrededor de las esquinas, queríamos que permanecieran perfectamente paralelas, incluso en casos potencialmente degenerativos, como en Chicago. Allí, una gran cantidad de líneas viajan juntas alrededor de curvas cerradas, por lo que dibujarlas en paralelo podría resultar en líneas agrupadas en el interior de la curva.

Por lo general, el redondeo se realiza utilizando curvas bezier, que parecen estar disminuyendo en las curvas. Pero para mantenerse fiel a la apariencia de los mapas de tránsito esquemáticos, las curvas bezier no estaban del todo bien. Los mapas de tránsito tienen líneas rectas que caen bruscamente en segmentos de arco circular. Entonces usamos segmentos de arco para redondear.

Además, a diferencia de las curvas de Bezier, cualquier línea paralela a un arco circular es en sí misma un arco circular. Mientras el radio sea lo suficientemente grande, se nos garantizó que no tendríamos casos degenerativos.

Se nos ocurrió un algoritmo personalizado que, dada una forma, eliminaría y agregaría puntos para redondearlo utilizando segmentos de arco circular. Garantiza un radio mínimo dado al simplificar la geometría según sea necesario. El radio mínimo depende del ancho total de todas las líneas paralelas.

La forma resultante es suave. Está completamente compuesto de líneas rectas y segmentos de arco, lo que significa que siempre podemos dibujar líneas en paralelo sin artefactos o casos degenerativos.

Este enfoque nos dio algo como esto:

El redondeo solo ocurre a lo largo de segmentos compartidos. También puede notar que eliminamos todas las intersecciones. Tratar con las intersecciones era un problema importante porque teníamos que asegurarnos de que cada línea continuara de un segmento al siguiente y se uniera correctamente. También utilizamos el algoritmo generador de arco para tener el mismo aspecto redondeado. Aquí está el resultado final:

Bastante bien, ¿verdad? Pero mientras eran bonitas ... todavía parecían extrañamente desnudas. Eso es porque les faltaban paradas.

Así que decidimos retrasar el lanzamiento una vez más, y agregar un último paso.

6. Agregar paradas

Agregar paradas puede parecer sencillo, pero en realidad requiere una buena cantidad de procesamiento para propagar la información de paradas a través de la larga tubería que habíamos creado.

También encontramos muchos casos en los que varias paradas en los datos en realidad correspondían a una sola estación física, por lo que tuvimos que colapsarlas en una sola parada.

Esto es lo que hicimos. Para paradas con varias líneas, dibujamos una barra blanca con un contorno negro (para contraste) en todas las líneas. Para paradas en una sola línea, dibujamos un círculo simple usando el color de esa línea de tránsito en particular. También agregamos una superposición blanca para reducir el contraste de la capa del mapa a continuación. Este es el resultado final:

Para permitir que los usuarios activen y desactiven las líneas de forma selectiva desde la página de configuración de nuestras aplicaciones, decidimos que el redondeo, así como algunas paradas de procesamiento y renderizado, se deben realizar en el dispositivo. Entonces, en la ciudad de Nueva York, puede deshabilitar todas las líneas de tránsito basadas en Nueva Jersey (o todas las líneas de Nueva York si vive en Nueva Jersey). Con tantas líneas de tránsito en ciertas áreas, esto permite a los usuarios crear mapas totalmente personalizados.

Observe cómo las líneas se centran en función de qué línea están activas y cómo la parada cambia de color.

Conclusión

Así es como lo hicimos. Claro, implementar mapas de tránsito generados automáticamente tomó mucho trabajo, pero valió la pena. Nuestros mapas son muchísimo más potentes que los archivos PDF que está acostumbrado a obtener de las agencias, sin importar los documentos en papel que dobla y guarda en su billetera. ¿Cuáles son las principales diferencias?

Nuestros mapas de tránsito son escalables, por lo que podemos agregar fácilmente nuevas ciudades en el mismo estilo visual, en cualquier lugar del mundo al que nos expandamos. Son personalizables, por lo que los usuarios pueden activar / desactivar redes y modos para crear sus propios mapas de tránsito personalizados. Y también son contextuales: a diferencia del PDF de un mapa de agencia, nuestros mapas incorporan su ubicación, lo que le da una idea de dónde se encuentra en relación con las líneas cercanas y ajusta el aspecto según su nivel de zoom.

Y, en última instancia, nuestros mapas de tránsito esquemáticos proporcionan más que solo la información básica sobre los sistemas de tránsito. Son emblemáticos de las ciudades mismas: importantes piezas de arte funcional que conectan a las personas con sus entornos. Queremos ayudar a construir esa conexión, y creemos que nuestros nuevos Mapas de tránsito hacen precisamente eso.

Estamos entusiasmados de seguir mejorando, pero estamos satisfechos con lo que hemos logrado hasta ahora. Lanzamos con 55 ciudades. La respuesta a nuestra publicación de blog que compara nuestros mapas con los de Google y Apple ha sido increíblemente positiva. Para el equipo de back-end, es genial que la gente vea y aprecie el trabajo y el esfuerzo que ponemos en lo que impulsa la experiencia de la aplicación. Nos motiva a seguir impulsando nuestra tecnología aún más.

Más allá de eso, todavía tenemos muchos más problemas "difíciles" para resolver. Continuaremos trabajando bajo el capó, no solo para tener la aplicación más bonita con la mejor interfaz de usuario, sino la aplicación de tránsito más funcional, potente y precisa que existe.

¿Quieres jugar con nuestros mapas?
Puede obtener Transit de forma gratuita en App Store y Google Play. O conozca más sobre la compañía en nuestro sitio web.

¿Tienes ganas de afrontar desafíos como este para vivir? ¡Estamos contratando!