En el desarrollo de software, uno a menudo se enfrenta a desafíos intrigantes, especialmente cuando opera bajo restricciones de recursos estrictas y se esfuerza por minimizar los costos antes de que el MVP demuestre su valor.
Geocodificación inversa
A finales de 2019, junto con un par de amigos, trabajé en el desarrollo de una pequeña aplicación para iOS llamadaAWAYLa aplicación permite a los usuarios mantener una lista de países que han visitado y compartirla con otros.El concepto básico detrás de ella es que los usuarios no necesitan introducir manualmente los países que han visitado.
Así funciona: si tu teléfono contiene fotos, la aplicación, al solicitar y recibir acceso a la biblioteca de medios, puede leer la latitud y longitud de donde se tomó cada foto a partir de los metadatos EXIF.
Este proceso de obtener una dirección (en este caso, el nombre del país) de las coordenadas geográficas se llamareverse geocodingPara referencia, el inverso de este proceso – obtención de coordenadas geográficas de una dirección textual – se conoce como geocodificación avanzada.
Soluciones de terceros
Al desarrollar nuestro MVP, comenzamos con la opción más simple disponible y utilizadaSolución de AppleLa aplicación funcionó, los países se añadieron automáticamente a la lista, y comenzamos a atraer a nuestros primeros usuarios.
Sin embargo, pronto encontramos limitaciones significativas.La solución de Apple fue muy lenta debido a los estrictos límites de tarifas en las solicitudes de red a su API, y no estaba diseñada para el procesamiento de lotes de coordenadas.Dado que las bibliotecas de medios de usuario a menudo contenían miles de fotos, el proceso de determinar los países era extremadamente demorado, a veces llevaba más de 30 minutos para completar.
En lugar de recibir inmediatamente una lista de países visitados y compartirla en Instagram o Facebook, los usuarios simplemente se irían sin esperar a que el proceso terminara.
No podíamos encontrar una solución de terceros más adecuada.Google, deMapbox, y otras APIs similares o tenían los mismos problemas que Apple - siendo poco adecuados para el procesamiento de lotes y ofreciendo ninguna ventaja de ahorro de tiempo - o habrían sido prohibitivamente caros dado el volumen de coordenadas que necesitábamos manejar.Nominadossería demasiado caro debido al costo de alquilar un servidor adecuado.
Sin opciones asequibles disponibles, yo, siendo responsable del backend, comencé a construir nuestra propia API.
GeoJSON
Antes de este proyecto, no tenía experiencia trabajando con datos geoespaciales, así que tuve que aprender todo a medida que desarrollamos la aplicación.
Lo primero que necesitaba para la implementación era información sobre las fronteras del país para coincidir con las coordenadas.Un formato ampliamente utilizado para almacenar estructuras de datos geográficos esGeoJSON.
GeoJSON es un archivo JSON estándar con una estructura específica que le permite describir puntos, líneas y formas de complejidad arbitraria.
Por ejemplo, digamos que queremos almacenar información sobre el territorio de Italia.FeatureLas fronteras del país se describirían dentro de unMultiPolygonCada polígono consta de uno o más arreglos de pares de coordenadas, donde el primer y el último par de coordenadas[lon, lat]La forma descrita en la primera matriz se añadirá a la zona geográfica general, en este caso, Italia misma, junto con la isla de Sardinia (la isla se describiría en un polígono separado).
Cualquier arreglo posterior dentro del polígono es opcional y representa áreas excluidas. Esto será necesario para excluir territorios como ciudades-estados completamente rodeados por Italia, como San Marino y el Vaticano. Las coordenadas en estos arreglos deben estar listadas a la hora. Cuanto más puntos especifiquemos, más precisas serán las fronteras del país.
Los metadatos, como el nombre del país, se pueden incluir en unpropertiesEl objeto.
{
"type": "FeatureCollection",
"features": [
{
"type": "Feature",
"geometry": {
"type": "MultiPolygon",
"coordinates": [
[ // Polygon
// Exterior ring, Italy
[ [20, 35],[10, 30],[10, 10], ... ,[45, 20],[20, 35]],
// Interior "excluding" ring, San-Marino
[ [30, 20],[20, 15],[20, 25], ... ,[30, 20]]
],
[ // Polygon
// Exterior ring, Sardinia
[ [40, 40],[20, 45], [45, 30], ... ,[40, 40]]
]
]
},
"properties": {
"country": "Italy",
}
}
]
}
Preparación de Geodata
Para crear un mapa del mundo, tuve que originar los archivos GeoJSON más precisos con las coordenadas de todas las fronteras nacionales, lo que resultó ser sorprendentemente desafiante.
Confío en una variedad de fuentes abiertas, incluyendo datos agregados deInstitutos Oceanográficos, dePublicaciones de npmjs.org, y datos geográficos abiertos deNominados, entre otros. Un problema común con todos los datos que obtuve era su calidad. A veces, las fronteras se superponían, particularmente en casos de disputas políticas entre regiones. En otros casos, sólo estaban disponibles los datos que incluían aguas territoriales, lo que no era adecuado para nuestras necesidades. tuve que excluir esas aguas subtrayendo el mapa del océano de los territorios del país (especialmente gracias a laInstituto Marítimo de FlandesOcasionalmente, la resolución (el número de coordenadas) era demasiado baja para una geocodificación fiable, lo que me obligó a buscar alternativas.
Los requisitos de la aplicación eran bastante exigentes: necesitábamos límites precisos, no superpuestos para cada área geográfica en alta resolución sin aguas territoriales (para mostrar en el mapa en la aplicación), y límites de menor resolución incluyendo aguas territoriales (para geocodificación más rápida y eficiente, especialmente para fotografías tomadas en buques cerca de las costas - un problema que descubrimos cuando trabajamos con soluciones de terceros).
Después de una semana y media de trabajo meticuloso, logré crear dos archivos GeoJSON de alta resolución.countries_maritime.jsonlas fronteras de todos los países, incluyendo sus aguas territoriales, mientras que el otro,countries_coastline.jsonCada archivo era de varios cientos de megabytes de tamaño, y al final, me sentía como si hubiera visitado personalmente cada rincón del mundo.
Fuego
Cuando se lanzó, la versión actualizada de la aplicación recopiló todas las coordenadas de fotos previamente no procesadas de la biblioteca de medios del usuario en lotes de 10.000 y las envió a mi backend en múltiples solicitudes.
El backend, construido en Node.js y alojado en AWS, cargó elcountries_maritime.jsonarchivo a la memoria en la inicialización. Cuando llegó una solicitud con un lote de coordenadas, utilizó elPolígono de Vistabiblioteca para coincidir las coordenadas con los territorios correspondientes del archivo, que contenía 250 países.
La lista de coordenadas fue sometida a una estricta validación ya que, como resultó, algunas coordenadas estaban fuera del rango permitido.También descartamos las coordenadas con altitudes superiores a 8.850 metros (un poco por encima del pico del Everest) para evitar contar con las típicas fotografías de Instagram de las alas de los aviones (los aviones suelen volar a altitudes superiores a 9.000 metros).
Cuando se encuentra un encuentro, el identificador del país desde elpropertyDespués de procesar todas las coordenadas, la lista de identificadores registrados se deduplicó, se añadió a la lista del usuario de países visitados y se devolvió al cliente para sincronizar la aplicación con la base de datos backend.
Después de cambiar a nuestra solución personalizada, el picoLa velocidad de procesamiento alcanzó las 10.000 coordenadas por segundo(en pruebas sintéticas), el tiempo mediano para procesar la biblioteca de medios de un usuario se redujo a 20-25 segundos (desde el registro del usuario hasta la devolución de la lista de países visitados), yEl número medio de países añadidos creció un 225% por usuariopor una geometría más precisa.
Administración geográfica
A medida que la aplicación continuaba creciendo, los usuarios comenzaron a enviar solicitudes de características.Una de las solicitudes más frecuentes fue la adición de reconocimiento automático para regiones y ciudades principales dentro de cada país.
Recopilar datos de alta calidad para las fronteras de 250 países ya había sido difícil.La perspectiva de recopilar datos similares para miles de regiones y ciudades era aún más aterradora.
Para abordar esto, transferí los territorios del archivo JSON a una tabla de Postgres y desarrollé una interfaz de administración para administrar zonas geográficas.Además, integré el panel de administración con varias APIs externas para automatizar la creación de listas para regiones y ciudades basadas en sus países madre.
El primer problema que encontré fue la complejidad inherente de los datos de la región geográfica. No hay distinción universalmente clara entre regiones y ciudades, y los diferentes países tienen diferentes niveles de división administrativa.sobrepasar.es, utilizando condiciones y llamadas recursivas para filtrar por centros administrativos, tamaño de la población y relaciones internas. Esto también involucró el estudio de cómo dividir y organizar los nodos geográficos, sus relaciones y estructuras ancladas, y corregir algunos datos erróneos.
El segundo desafío surgió al trabajar con las fuentes de coordenadas para las fronteras regionales. Después de recuperar listas de osmId para regiones y ciudades, tuve que extraer la geometría de sus fronteras.Enlace a OpenStreetMap.orgy casi totalmente no documentado.Páginas en OpenStreetMap.frEstas fuentes eran incompletas, así que tuve que enviar varias solicitudes y comparar sus resultados, seleccionando la mejor combinación basada en la calidad de los datos devueltos.
A pesar de la falta de documentación, complejas relaciones de datos y inconsistencias en las fuentes, pude crear una solución estable.La interfaz del panel de administración ahora permite la carga automática de listas de ciudades y regiones para cualquier país con solo unos pocos clics, incluyendo sus metadatos y las mejores geometrías de límites disponibles.
Para abordar los problemas frecuentes con los datos de GeoJSON, incluso desarrollé un editor integrado que permite dividir, fusionar, subtraer y dibujar geometrías de límites faltantes.
Todas estas herramientas nos permitieron, con un equipo de sólo dos personas, crear una base de datos de regiones y ciudades que estábamos orgullosos de presentar a los usuarios en un mes y medio.
Actualmente, la aplicación soporta 3.134 regiones y 28.083 ciudades., cada uno con límites precisos, y rastrea el número de usuarios que los han visitado.
Minimizar los datos geográficos
El manejo de 31.467 territorios con Node.js se hizo incontrolable debido a las limitaciones de rendimiento y recursos ya en el paso de la inicialización del índice. Mi primera idea para abordar este desafío fue reducir el tamaño de los datos de GeoJSON mientras minimizaba cualquier degradación visual.
Como mencioné anteriormente, los datos necesarios para la exhibición de aplicaciones y la geocodificación tenían requisitos muy diferentes: mientras que la preparación de placas de mapas para la renderización en la aplicación podía permitirse durar minutos, la geocodificación era altamente sensible a los volúmenes de datos, con su velocidad directamente ligada al número de coordenadas en las fronteras territoriales.
He experimentado con varios algoritmos para simplificar las cadenas de coordenadas de los polígonos.
El primer enfoque fue elRamer-Douglas y PeuckerSu aproximación era inestable, lo que llevó a desajustes en las fronteras compartidas entre diferentes archivos GeoJSON, y también causó la pérdida de detalles más pequeños, como islas.
En definitiva,He desarrollado mi propia implementación(publicado como paquete npm) basado en elEncuentran por quéLas implementaciones existentes de este algoritmo sólo podían ser aplicadas a partes específicas de una estructura GeoJSON, lo que resolvió el problema de la estabilidad de los resultados pero todavía causó una degradación significativa de las fronteras y la pérdida de pequeños detalles.Hecho(con el ángulo entre tres coordenadas vecinas como el elemento heap), y lo procesó como una curva con lógica adicional para la conservación de puntos comunes.
He desarrollado mi propia implementaciónAdemás de reducir los volúmenes de datos, esta reestructuración de los archivos GeoJSON ayudó a descubrir numerosos errores y conflictos dentro de los datos:
- Array de coordenadas no cerradas.
- Conflictos de arreglos debido a la incorrecta curvatura de coordenadas.
- Coordenadas de array vacío.
- Exceso de nidos.
- Precisión en las coordenadas.
He automatizado con éxito la validación y corrección de estos errores, en parte utilizando herramientas existentes como:Polígono cortado, de@mapbox / geojsonhint, de@MAPBOX / Geojson-rewind, dey @mapbox/geojson-extentEstas incluyeron la fusión de polígonos separados en colecciones de multipolígonos y geometría, la reducción de la resolución de las coordenadas al nivel requerido, la corrección de la dirección de las coordenadas y la eliminación de los matices vacíos.
Como resultado, logré una mejora significativa en el rendimiento del procesamiento de datos geográficos. Además, la estabilidad de mi algoritmo resolvió el problema de las fronteras simplificadas incompatibles entre regiones adyacentes en el mapa.
Ir al microservicio
A pesar de reducir la carga computacional a través de la simplificación de geodata, se hizo claro que Node.js definitivamente no era la solución ideal para nuestras necesidades.PostalesDespués de una extensa investigación, incluyendo mediciones de rendimiento y consumo de recursos, opté por este último —un simple microservicio construido con Go.
La arquitectura de microservicios está diseñada para maximizar la velocidad de procesamiento de par de coordenadas al tiempo que se minimizan las operaciones innecesarias.
En su primera ejecución, el microservice se conecta a PostgreSQL y recupera todos los datos relevantes de GeoJSON en lotes de 100 objetos. Estos datos se analizan en estructuras, cada una de las cuales contiene un polígono y el identificador de territorio correspondiente.
Una vez creada la estructura, unR árbolEste tipo de árbol se utiliza a menudo para crear índices de búsqueda de datos multidimensionales, como los polígonos. El árbol permite búsquedas de tiempo logarítmico para el rectángulo fronterizo más pequeño que incluye el polígono objetivo.
Después de que se construya el árbol, el microservicio entra en un estado de escucha, esperando las solicitudes entrantes.
Cuando se recibe una solicitud, compuesta por pares de coordenadas[lat, lon]Se inicia el procesamiento multithreaded.El resultado es un conjunto de identificadores de territorio únicos que contienen las coordenadas proporcionadas.
Cada coordenada primero se somete a una búsqueda a través del árbol R. Esta búsqueda puede devolver un rectángulo que contenga un polígono, que podría potencialmente incluir la coordenada.El algoritmo de Ray-CastingEste algoritmo funciona en tiempo lineal, por lo que es la parte más intensiva en recursos del proceso. Sin embargo, antes de ejecutar el control de descarga de rayos, verifico si el identificador de territorio para el polígono ya se ha encontrado durante el procesamiento de otras coordenadas en la solicitud. Si lo es, el control de descarga de rayos se salta, reduciendo significativamente el tiempo de procesamiento del servicio.
Después de que todos los hilos hayan completado su trabajo, el conjunto de identificadores se devuelve a la capa Node.js. Abajo, he intentado representar la arquitectura en el siguiente diagrama:
Todo el proceso de búsqueda, además de la optimización específica para saltar los controles repetidos de descarga de rayos, refleja de cerca cómo PostGIS maneja una tarea similar cuando utilizaEl regalolos índices.
Usando la API construida en torno al microservicio de Go,alcanzamos la capacidad de procesar alrededor de 100.000 pares de coordenadas por segundoEn comparación, la solución anterior de Node.js gestionó alrededor de 10.000 pares de coordenadas para 250 zonas, incluyendo la superposición de solicitudes de red y operaciones de backend.
Esta mejora significativa en la velocidad de procesamiento permitió una compilación mucho más rápida de las listas de países visitados por los usuarios.La aplicación registró un aumento del 160% en el número de usuarios activos y un aumento del 107% en el número de usuarios compartidos.sus resultados .
La solución sigue en uso hoy en día y continúa manejando un volumen creciente de solicitudes y zonas geográficas de manera eficiente.Sin duda, todo el backend opera con menos de un gigabyte de RAM, mostrando su uso optimizado de recursos.
