No desenvolvemento de software, moitas veces se atopan con retos intrigantes, especialmente cando operan baixo restricións de recursos rigorosas e se esforzan por minimizar os custos antes de que o MVP demostre o seu valor.
Geocodificación inversa
A finais de 2019, xunto a un par de amigos, traballei no desenvolvemento dunha pequena aplicación para iOS chamadaAWAYA aplicación permite aos usuarios manter unha lista de países que visitaron e compartilo con outros.O concepto básico detrás dela é que os usuarios non precisan introducir manualmente os países que visitaron.
Aquí está como funciona: se o seu teléfono contén fotos, a aplicación, ao solicitar e recibir acceso á biblioteca de medios, pode ler a latitude e lonxitude de onde cada foto foi tomada a partir dos metadatos EXIF.
Este proceso de obter unha dirección (neste caso, o nome do país) a partir de coordenadas xeográficas chámasereverse geocodingPara referencia, a inversa deste proceso -a obtención de coordenadas xeográficas dun enderezo textual- é coñecida como xeocodificación avanzada.
Solucións de terceiros
Ao desenvolver o noso MVP, comezamos coa opción máis sinxela dispoñible e usadaSolución de AppleA aplicación funcionou, os países foron engadidos automaticamente á lista, e comezamos a atraer os nosos primeiros usuarios.
A solución de Apple foi moi lenta debido aos estritos límites de tarifas das solicitudes de rede para a súa API, e non foi deseñado para o procesamento de lotes de coordenadas.Dado que as bibliotecas de medios de usuario moitas veces contiñan miles de fotos, o proceso de determinar os países foi extremadamente demorado, ás veces leva máis de 30 minutos para completar.
En lugar de recibir inmediatamente unha lista de países visitados e compartilo en Instagram ou Facebook, os usuarios simplemente marcharían sen esperar que o proceso rematase.
Non puidemos atopar unha solución de terceiros máis adecuada.Google xa,Mapboxe, e outras APIs similares ou tiñan os mesmos problemas que Apple - sendo mal axeitado para o procesamento de lotes e ofrecendo ningunha vantaxe de aforro de tempo - ou tería sido prohibitivamente caro dado o volume de coordenadas que necesitamos para manexar.Nomeaciónssería demasiado caro debido ao custo de alugar un servidor adecuado.
Sen opcións accesibles off-the-shelf dispoñibles, eu, sendo responsable do backend, comezou a construír a nosa propia API.
Xeoloxía
Antes deste proxecto, non tiña experiencia traballando con datos xeoespaciais, polo que tiven que aprender todo mentres desenvolvemos a aplicación.
A primeira cousa que necesitaba para a implementación era información sobre as fronteiras do país para coincidir coordenadas.GeoJSON.
GeoJSON é un ficheiro JSON estándar cunha estrutura específica que permite describir puntos, liñas e formas de complexidade arbitraria.
Por exemplo, digamos que queremos almacenar información sobre o territorio de Italia.FeatureAs fronteiras do país serían descritas dentro dunhaMultiPolygonCada polígono consta dun ou máis arreglos de pares de coordenadas, onde o primeiro e o último par de coordenadas[lon, lat]A forma descrita na primeira matriz engadirase á zona xeográfica global, neste caso, a propia Italia, xunto coa illa de Sardeña (a illa sería descrita nun polígono separado).
Calquera matriz posterior dentro do polígono é opcional e representa áreas excluídas. Isto será necesario para excluír territorios como as cidades-estados completamente rodeados por Italia, como San Marino e o Vaticano. As coordenadas nestas matrizes deben ser listadas de forma cronolóxica. Canto máis puntos especificamos, máis precisas serán as fronteiras do país.
Os metadatos, como o nome do país, poden incluírse nunpropertiesO obxecto.
{
"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 xeodatos
Para crear un mapa do mundo, tiven que obter os ficheiros GeoJSON máis precisos coas coordenadas de todas as fronteiras nacionais, o que resultou ser sorprendentemente desafiante.
Eu dependín dunha variedade de fontes abertas, incluíndo datos agregados deInstitutos Oceanográficos,Páxinas en npmjs.org, e datos xeográficos abertos deNomeacións, entre outros. Un problema común con todos os datos obtidos era a súa calidade. Ás veces, as fronteiras se sobrepasan, especialmente en casos de disputas políticas entre rexións. noutros casos, só estaban dispoñibles datos que incluían augas territoriais, o que non era axeitado para as nosas necesidades. tiven que excluír esas augas subtraendo o mapa do océano dos territorios do país (en especial grazas aoInstituto Mariñeiro de FlandresÁs veces, a resolución (o número de coordenadas) era demasiado baixo para unha xeocodificación fiable, o que me obrigaba a buscar alternativas.
Os requisitos da aplicación eran bastante esixentes: necesitábamos límites precisos e non superpuestos para cada área xeográfica en alta resolución sen augas territoriais (para mostrar no mapa in-app), e límites de menor resolución incluíndo augas territoriais (para geocodificación máis rápida e máis eficiente, especialmente para fotografías tomadas en buques preto das costas - un problema que descubrimos cando traballamos con solucións de terceiros).
Despois dunha semana e media de meticulosos traballos, logrei crear dous ficheiros GeoJSON de alta resolución.countries_maritime.json, describiu as fronteiras de todos os países, incluíndo as súas augas territoriais, mentres que o outro,countries_coastline.jsonCada ficheiro era varios centos de megabytes de tamaño, e ao final, sentín como se tivese visitado persoalmente cada recuncho do mundo.
fogueira
Cando se lanzou, a versión actualizada da aplicación recolleu todas as coordenadas de fotos anteriormente non procesadas da biblioteca de medios do usuario en lotes de 10.000 e envíounas ao meu backend en múltiples solicitudes.
O backend, construído en Node.js e aloxado en AWS, cargou ocountries_maritime.jsoninicialización.Cando chegou unha solicitude cun lote de coordenadas, usou oPolígono Vistabiblioteca para combinar as coordenadas cos correspondentes territorios do ficheiro, que contiña 250 países.
Tamén descartamos as coordenadas con altitudes superiores a 8.850 metros (un pouco por encima do pico do Everest) para evitar contar as típicas fotografías de Instagram de ás de avións (os avións normalmente voan a altitudes superiores a 9.000 metros).
Cando se atopa un encontro, o identificador do país dende opropertyDespois de procesar todas as coordenadas, a lista de identificadores rexistrados foi deduplicada, engadida á lista do usuario de países visitados e devolta ao cliente para sincronizar a aplicación coa base de datos de backend.
Despois de pasar á nosa solución personalizada, o picoA velocidade de procesamento alcanza as 10.000 coordenadas por segundo(en probas sintéticas), o tempo mediano para procesar a biblioteca de medios dun usuario caeu a 20-25 segundos (desde o rexistro do usuario ata a devolución da lista de países visitados), e oO número medio de países engadidos creceu un 225% por usuariodebido a unha xeometría máis precisa.
Administración xeográfica
A medida que a aplicación continuaba a crecer, os usuarios comezaron a enviar solicitudes de recursos.Unha das solicitudes máis frecuentes foi a adición de recoñecemento automático para rexións e grandes cidades dentro de cada país.
Recoller datos de alta calidade para as fronteiras de 250 países xa era difícil.A perspectiva de recoller datos similares para miles de rexións e cidades era aínda máis aterradora.
Para abordar isto, transferín os territorios do ficheiro JSON a unha táboa de Postgres e desenvolvín unha interface de administración para xestionar as zonas xeográficas.Ademais, integrei o panel de administración con varias APIs externas para automatizar a creación de listas para rexións e cidades baseadas nos seus países nai.
O primeiro problema que atopei foi a complexidade inherente dos datos de rexións xeográficas. Non hai distinción universalmente clara entre rexións e cidades, e os diferentes países teñen diferentes niveis de divisións administrativas.sobrepasado.es, usando condicións e chamadas recursivas para filtrar por centros administrativos, tamaño da poboación e relacións internas. Isto tamén implicou estudar como dividir e organizar os nodos xeográficos, as súas relacións e estruturas anexadas, e corrixir algúns datos erróneos.
O segundo desafío xurdiu ao traballar coas fontes de coordenadas para as fronteiras da rexión. Despois de obter listas de osmId para rexións e cidades, necesitei extraer a xeometría das súas fronteiras.Páxina oficial: openstreetmap.orge, polo tanto, o que non está documentadoPáxina oficial: openstreetmap.frEstas fontes eran incompletas, polo que tiven que enviar varias solicitudes e comparar os seus resultados, seleccionando o mellor encontro baseado na calidade dos datos devoltos.
A pesar da falta de documentación, complexas relacións de datos e inconsistencias nas fontes, puiden crear unha solución estable. A interface do panel de administración agora permite a carga automática de listas de cidades e rexións para calquera país con só uns poucos clics, incluíndo os seus metadatos e as mellores xeometrías de límites dispoñibles.
Para abordar os problemas frecuentes cos datos de GeoJSON, mesmo desenvolvín un editor integrado que permite dividir, fusionar, subtraer e debuxar xeometrías de límites que faltan.
Todas estas ferramentas permitíronnos, cun equipo de só dúas persoas, crear unha base de datos de rexións e cidades que estábamos orgullosos de presentar aos usuarios dentro dun mes e medio.
Actualmente, a aplicación soporta 3.134 rexións e 28.083 cidades, cada un con límites precisos, e rastrexa o número de usuarios que os visitaron.
Minimizar a xeografía
O manexo de 31.467 territorios con Node.js volveuse incontrolable debido ás limitacións de rendemento e recursos xa no paso de inicialización do índice.
Como mencionei anteriormente, os datos necesarios para a exhibición de aplicacións e a xeocodificación tiñan requisitos moi diferentes: mentres que a preparación de placas de mapas para a renderización na aplicación podería permitirse durar minutos, a xeocodificación era moi sensible aos volumes de datos, coa súa velocidade directamente ligada ao número de coordenadas nas fronteiras territoriais.
Experimentei con varios algoritmos para simplificar as cadeas de coordenadas dos polígonos.
O primeiro enfoque foi oRamer-Douglas PáxinasA súa aproximación foi inestable, levando a incongruencias nas fronteiras compartidas entre diferentes ficheiros GeoJSON, e tamén causou a perda de detalles máis pequenos, como illas.
ao final,Desenvolvín a miña propia implementación(publicado como paquete npm) baseado naXogar por queAlgoritmo adaptado para traballar con GeoJSON. As implementacións existentes deste algoritmo só se poderían aplicar a partes específicas dunha estrutura GeoJSON, o que resolveu o problema da estabilidade do resultado pero aínda causou unha degradación significativa das fronteiras e a perda de pequenos detalles.bonecas(co ángulo entre tres coordenadas veciñas como o elemento de pila), e procesado como unha curva con lóxica adicional para a conservación de puntos comúns.
Desenvolvín a miña propia implementaciónAdemais de reducir os volumes de datos, esta reestruturación dos arquivos GeoJSON axudou a descubrir numerosos erros e conflitos dentro dos datos:
- Coordenadas non pechadas.
- Conflictos de matriz debido á incorrecta curvatura de coordenadas.
- Coordenadas de array baleiro.
- Exceso de nidificación.
- Precisión inútil en coordenadas.
Automatizei con éxito a validación e corrección destes erros, en parte usando ferramentas existentes como:Polígono Clip,@mapbox / xeojsonhint,Páxina oficial: geojson-rewind,e tamén @mapbox/geojson-extentEstes incluíron a fusión de polígonos separados en coleccións de multipolígonos e xeometría, reducindo a resolución de coordenadas ao nivel requirido, corrixindo a dirección de coordenadas e eliminando arreglos baleiros.
Como resultado, logrei unha mellora significativa no rendemento do procesamento de datos xeográficos.Ademais, a estabilidade do meu algoritmo resolveu o problema das fronteiras simplificadas desacompañadas entre rexións adxacentes no mapa.
Ir a Microservizos
A pesar de reducir a carga computacional a través da simplificación de datos xeográficos, fíxose claro que Node.js definitivamente non era a solución ideal para as nosas necesidades.postaisDespois de extensa investigación, incluíndo medicións de rendemento e consumo de recursos, optei por este último - un simple microservizo construído con Go.
A arquitectura de microservizos está deseñada para maximizar a velocidade de procesamento do par de coordenadas ao mesmo tempo que minimiza as operacións innecesarias.
Na súa primeira execución, o microservizo conecta a PostgreSQL e recupera todos os datos relevantes de GeoJSON en lotes de 100 obxectos. Estes datos son analizados en estruturas, cada unha contendo un polígono e o identificador de territorio correspondente.
Unha vez creada a estrutura array, unÁrbore REste tipo de árbore é moitas veces usado para crear índices de busca para datos multidimensionais, como polígonos.A árbore permite buscas logarítmicas para o rectángulo límite máis pequeno que inclúe o polígono obxectivo.
Despois de construír a árbore, o microservizo entra nun estado de escoita, agardando as solicitudes de entrada.
Cando se recibe unha solicitude, que consiste en pares de coordenadas[lat, lon]O resultado é unha serie de identificadores de territorio únicos que conteñen as coordenadas proporcionadas.
Cada coordenada primeiro sofre unha busca a través da árbore R. Esta busca pode devolver un rectángulo que contén un polígono, que podería potencialmente incluír a coordinación.Algoritmos de Ray-CastingEste algoritmo funciona en tempo lineal, o que o fai a parte máis intensiva de recursos do proceso. Con todo, antes de executar o control de descarga de raios, verifico se o identificador de territorio para o polígono xa se atopou durante o procesamento de outras coordenadas na solicitude.
Despois de que todos os feeds rematen o seu traballo, a matriz de identificadores é devolta á capa Node.js. Abaixo, tentei representar a arquitectura no seguinte diagrama:
Todo o proceso de busca, ademais da optimización específica para saltar controis repetidos de descarga de raios, reflicte de preto como PostGIS xestiona unha tarefa similar cando usaagasalloos índices.
Usando a API construída ao redor do microservizo Go,Atopamos a capacidade de procesar arredor de 100.000 pares de coordenadas por segundoEn comparación, a solución anterior de Node.js manexou arredor de 10.000 pares de coordenadas para 250 zonas, incluíndo a superposición de solicitudes de rede e operacións de backend.
Esta mellora significativa na velocidade de procesamento permitiu unha compilación moito máis rápida das listas de países visitados polos usuarios.A aplicación viu un aumento do 160% no número de usuarios activos e un aumento do 107% no número de usuarios compartidos.os seus resultados.
A solución segue en uso hoxe e continúa a manexar un volume crecente de solicitudes e zonas xeográficas de forma eficiente.
