U razvoju softvera često se susreću intrigantni izazovi, osobito kada se radi pod strogim ograničenjima resursa i nastoje smanjiti troškove prije nego što MVP dokaže svoju vrijednost. Povratna geokodiranje Krajem 2019. godine, zajedno s nekoliko prijatelja, radio sam na razvoju male iOS aplikacije pod nazivom Aplikacija omogućuje korisnicima održavanje popisa zemalja koje su posjetili i dijeljenje s drugima. AWAY Evo kako to funkcionira: ako vaš telefon sadrži fotografije, aplikacija, kada zatraži i prima pristup medijskoj knjižnici, može pročitati širinu i dužinu gdje je svaka fotografija snimljena iz EXIF metapodataka. Ovaj proces dobivanja adrese (u ovom slučaju, ime zemlje) iz zemljopisnih koordinata zove se Za upućivanje, obrnuto od ovog procesa - dobivanje zemljopisnih koordinata iz tekstualne adrese - poznat je kao napredna geokodiranje. reverse geocoding rješenja trećih strana Kada smo razvili naš MVP, počeli smo s najjednostavnijom dostupnom i korištenom opcijom. Aplikacija je djelovala, zemlje su automatski dodane na popis, a mi smo počeli privlačiti naše prve korisnike. Appleovo rješenje Međutim, ubrzo smo naišli na značajna ograničenja. Appleovo rješenje bilo je vrlo sporo zbog strogih ograničenja stope mrežnih zahtjeva za njegov API, a nije bio dizajniran za serijsku obradu koordinata. Budući da su korisničke medijske knjižnice često sadržavale tisuće fotografija, proces određivanja zemalja bio je izuzetno vremenski zahtjevan, ponekad traje više od 30 minuta. Takvo dugo čekanje neizbježno je potkopalo viralnost naše aplikacije. Umjesto da odmah dobiju popis posjećene zemlje i dijele ga na Instagramu ili Facebooku, korisnici bi jednostavno otišli bez čekanja na završetak procesa. Nismo mogli pronaći prikladnije rješenje treće strane. , , i drugi slični API-ji ili su imali iste probleme kao i Apple - nisu prikladni za obradu partija i ne nude nikakvu prednost uštede vremena - ili bi bili prohibitivno skupi s obzirom na količinu koordinata koje smo trebali nositi. bilo bi previše skupo zbog troškova iznajmljivanja odgovarajućeg poslužitelja. Google Mapbox Nominacija S nedostatkom pristupačnih opcija na raspolaganju, ja sam, odgovoran za backend, počeo graditi vlastiti API. GeoJSON Prije ovog projekta, nisam imao iskustva s radom s geospatialnim podacima, pa sam morao naučiti sve dok smo razvili aplikaciju. Prva stvar koja mi je bila potrebna za provedbu bila je informacija o državnim granicama kako bi se uskladile koordinate. GeoJSON. GeoJSON je standardna JSON datoteka s specifičnom strukturom koja vam omogućuje opisivanje točaka, linija i oblika proizvoljne složenosti. Na primjer, pretpostavimo da želimo pohraniti informacije o teritoriju Italije. Granične granice zemlje bit će opisane unutar Svaki poligon sastoji se od jednog ili više niza koordinatnih para, gdje prvi i posljednji par koordinata Oblik opisan u prvom nizu će se dodati na ukupnu zemljopisnu zonu, u ovom slučaju, sama Italija, zajedno s otokom Sardinije (otok će biti opisan u zasebnom poligonu). Feature MultiPolygon [lon, lat] Svaki naknadni raspon unutar poligona je neobvezan i predstavlja isključena područja. To će biti potrebno kako bi se isključile teritorije poput gradskih država koje su potpuno okružene Italijom, kao što su San Marino i Vatikan. Koordinacije u tim rasponima moraju biti navedene prema vremenu. Što više točaka navedemo, točnije će biti granice zemlje. Metapodatci, kao što je ime zemlje, mogu se uključiti u ugrađeni Objekt je . properties { "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", } } ] } Priprema geodeta Da bih stvorio svjetsku mapu, morao sam izvoriti najtočnije GeoJSON datoteke s koordinatama svih nacionalnih granica, što se pokazalo iznenađujuće izazovnim. Oslanjao sam se na razne otvorene izvore, uključujući agregirane podatke iz , , i otvoreni geografski podaci iz , između ostalog. Zajednički problem sa svim podacima koje sam dobio bio je njihov kvalitet. Ponekad su se granice preklapale, osobito u slučajevima političkih sporova između regija. U drugim slučajevima, dostupni su samo podaci koji su uključivali teritorijalne vode, što nije bilo prikladno za naše potrebe. morala sam isključiti te vode oduzimanjem oceanske karte od državnih teritorija (posebno zahvaljujući Ponekad je rezolucija (broj koordinata) bila previše niska za pouzdano geokodiranje, što me zahtijeva da potražim alternative. Oceanografski instituti Sljedeći članakNpmjs.org Nominacija Flandrijski pomorski institut Zahtjevi aplikacije bili su prilično zahtjevni: trebali smo precizne, ne preklapajuće granice za svako zemljopisno područje u visokoj rezoluciji bez teritorijalnih voda (za prikaz na karti u aplikaciji), i granice niže rezolucije, uključujući teritorijalne vode (za brže i učinkovitije geokodiranje, posebno za fotografije snimljene na brodovima u blizini obalnih linija - problem koji smo otkrili prilikom rada s rješenjima trećih strana). Nakon tjedan i pol pažljivog rada, uspio sam stvoriti dvije GeoJSON datoteke visoke rezolucije. , opisao granice svih zemalja, uključujući njihove teritorijalne vode, dok je drugi, Svaka datoteka je bila nekoliko stotina megabajta u veličini, a na kraju sam se osjećao kao da sam osobno posjetio svaki kutak svijeta. countries_maritime.json countries_coastline.json vatra Kada je lansirana, ažurirana verzija aplikacije prikupila je sve prethodno neobrađene koordinate fotografija iz korisničke medijske knjižnice u serijama od 10.000 i poslala ih u moj backend u višestrukim zahtjevima. Backend, koji je izgrađen na Node.js-u i smješten na AWS-u, naložio je Prilikom inicijaliziranja datoteke u memoriju.Kada je došao zahtjev s skupom koordinata, koristio je knjižnica za usklađivanje koordinata s odgovarajućim područjima iz datoteke, koja je sadržavala 250 zemalja. countries_maritime.json Poligonalni pogled Popis koordinata podvrgnut je strogoj validaciji jer su, kako se ispostavilo, neke koordinate bile izvan dopuštenog raspona. Također smo odbacili koordinate s visinama većim od 8.850 metara (malo iznad vrha Everesta) kako bismo izbjegli računanje tipičnih fotografija krila zrakoplova u stilu Instagrama (avioni obično lete na visinama iznad 9.000 metara). Kada se pronađe utakmica, identifikatora zemlje iz Nakon obrade svih koordinata, popis zabilježenih identifikatora je dedupliciran, dodao se na korisnikov popis posjećenih zemalja i vratio klijentu kako bi se aplikacija sinhronizirala s backend bazom podataka. property Nakon prebacivanja na naše prilagođeno rješenje, vrhunac (u sintetičkim testovima), mediano vrijeme za obradu korisničke medijske knjižnice smanjeno je na 20–25 sekundi (od registracije korisnika do vraćanja popisa posjećenih zemalja), a Zbog preciznijeg geokodiranja. brzina obrade dosegla 10.000 koordinata u sekundi Prosječan broj dodanih zemalja porastao je za 225% po korisniku Geodata administracija Kako je aplikacija nastavila rasti, korisnici su počeli podnositi zahtjeve za značajke.Jedan od najčešćih zahtjeva bio je dodavanje automatskog prepoznavanja za regije i glavne gradove unutar svake zemlje. Prikupljanje visokokvalitetnih podataka za granice 250 zemalja već je bilo teško. Da bih to riješio, prenio sam teritorije iz JSON datoteke u tablicu Postgres i razvio administrativni sučelje za upravljanje geografskim zonama.Dodatno, integrirao sam admin panel s nekoliko vanjskih API-ja kako bih automatizirao stvaranje lista za regije i gradove na temelju njihovih matičnih zemalja. Prvi problem s kojim sam se susreo bio je inherentna složenost podataka o zemljopisnim regijama.Ne postoji univerzalno jasna razlika između regija i gradova, a različite zemlje imaju različite razine administrativnih podjela. , koristeći uvjete i recursivne pozive za filtriranje po administrativnim centrima, veličini stanovništva i unutarnjim odnosima.To je također uključivalo proučavanje kako podijeliti i organizirati geografske čvorove, njihove odnose i nestane strukture, te ispravljanje nekih pogrešnih podataka. Sljedeći članakApi.de Drugi izazov nastao je kada sam radio s koordinatnim izvorima za regionalne granice. Nakon preuzimanja lista osmId za regije i gradove, morao sam izvući geometrijske granice njihovih granica. Gotovo u potpunosti nedokumentirani Ti su izvori bili nepotpuni, tako da sam morao poslati više zahtjeva i usporediti njihove rezultate, odabirom najboljeg odgovora na temelju kvalitete vraćenih podataka. Sljedeći članakOpenstreetmap.org Sljedeći članakOpenstreetmap.fr Unatoč nedostatku dokumentacije, složenim odnosima podataka i nedosljednostima u izvorima, uspio sam stvoriti stabilno rješenje.Admin panel sučelje sada omogućuje automatsko učitavanje lista gradova i regija za bilo koju zemlju s samo nekoliko klikova, uključujući njihove metapodatke i najbolje dostupne granične geometrije. Kako bi se riješili česti problemi s podacima GeoJSON-a, razvio sam čak i ugrađeni uređač koji omogućuje razdvajanje, spajanje, oduzimanje i crtanje manjkajućih granica. Svi ti alati omogućili su nam, s timom od samo dvije osobe, stvaranje baze podataka regija i gradova koje smo bili ponosni predstaviti korisnicima u roku od mjesec i pol. , svaki s preciznim granicama, i prati broj korisnika koji su ih posjetili. Trenutno, aplikacija podržava 3.134 regije i 28.083 gradova Minimiziranje geodeta Rješavanje 31.467 teritorija s Node.js-om postalo je nemoguće zbog ograničenja performansi i resursa već u koraku inicijaliziranja indeksa. Kao što sam ranije spomenuo, podaci potrebni za prikaz aplikacija i geokodiranje imali su vrlo različite zahtjeve: dok je priprema kartografskih pločica za renderiranje u aplikaciji mogla priuštiti da traje nekoliko minuta, geokodiranje je bilo vrlo osjetljivo na volumene podataka, s brzinom koja je izravno vezana za broj koordinata u teritorijalnim granicama. Eksperimentirao sam s nekoliko algoritama kako bih pojednostavio koordinatne lance poligona. Prvi pristup bio je Njegova je približavanja bila nestabilna, što je dovelo do neusklađenosti u zajedničkim granicama između različitih GeoJSON datoteka, a također je uzrokovalo gubitak manjih detalja, poput otoka. Ramer Douglas Peucker U konačnici, (izdana kao npm paket) na temelju Postojeće implementacije ovog algoritma mogle bi se primijeniti samo na određene dijelove strukture GeoJSON-a, što je riješilo problem stabilnosti rezultata, ali i dalje je uzrokovalo značajnu degradaciju granica i gubitak malih detalja. (s kutom između tri susjedne koordinate kao element gomile) i obrađivao ga kao jednu krivulju s dodatnom logikom za očuvanje zajedničkih točaka. I developed my own implementation Sljedeći članakWhyatt lijepo Razvijala sam vlastitu implementaciju Osim smanjenja volumena podataka, ova restrukturiranje GeoJSON datoteka pomoglo je otkriti brojne pogreške i sukobe unutar podataka: Nezavršene koordinatne arete. Konfliktne serije zbog nepravilnog uklanjanja koordinata. Prazne koordinatne arete. Prekomjerno gniježenje Nepotrebna preciznost u koordinatama. Uspješno sam automatizirao validaciju i ispravljanje tih pogrešaka, djelomično koristeći postojeće alate kao što su: , , , To je uključivalo spajanje zasebnih poligona u multipoligone i zbirke geometrije, smanjenje rezolucije koordinata na potrebnu razinu, ispravljanje smjera koordinata i uklanjanje praznih niza. Poligonalno rezanje @mapbox / geojsonhint @mapbox / geojson-rewind i @mapbox/geojson-extent Kao rezultat toga, postigao sam značajno poboljšanje u učinkovitosti obrade zemljopisnih podataka.Osim toga, stabilnost mog algoritma riješila je problem neusklađenih pojednostavljenih granica između susjednih regija na karti. Posjetite Microservice Unatoč smanjenju računalnog opterećenja kroz pojednostavljenje geodata, postalo je jasno da Node.js definitivno nije idealno rješenje za naše potrebe. Nakon opsežnih istraživanja, uključujući mjerenja performansi i potrošnje resursa, odlučio sam se za potonju – jednostavnu mikroslužbu izgrađenu s Go-om. Poštar Arhitektura mikroslužbi osmišljena je kako bi se povećala brzina obrade koordinatnog para, a istodobno se smanjile nepotrebne operacije. Nakon prvog pokretanja, mikroslužba se povezuje s PostgreSQL-om i preuzima sve relevantne GeoJSON podatke u serije od 100 objekata. Ti se podaci razvrstavaju u strukture, od kojih svaki sadrži poligon i odgovarajući teritorijalni identifikator. Nakon što je uspostavljena struktura array, a Ova vrsta stabla često se koristi za stvaranje indeksa za pretraživanje multidimenzionalnih podataka, kao što su poligoni. stablo omogućuje logaritamsko pretraživanje za najmanji granični pravokut koji uključuje ciljni poligon. R-drvo Nakon što je stablo izgrađeno, mikroslužba ulazi u stanje slušanja, čekajući dolazne zahtjeve. Kada je primljen zahtjev, koji se sastoji od parova koordinata Multithreaded obrada je pokrenuta. Rezultat je niz jedinstvenih identifikatora teritorija koji sadrže navedene koordinate. [lat, lon] Svaka koordinata prvo podliježe pretraživanju kroz R-drvo. Ovo pretraživanje može vratiti pravokut koji sadrži poligon, koji bi potencijalno mogao uključivati koordinatu. Ovaj algoritam djeluje u linearnom vremenu, čineći ga najintenzivnijim dijelom procesa. Međutim, prije nego što izvršim kontrolu radijacije, provjeravam je li identifikator teritorija za poligon već pronađen tijekom obrade drugih koordinata u zahtjevu. Ray-casting algoritam Nakon što sve žice završe svoj rad, niz identifikatora vraća se u Node.js sloj. Ispod sam pokušao predstaviti arhitekturu u sljedećem diagramu: Cijeli proces pretraživanja, osim specifične optimizacije za preskakanje ponavljanih provjera ray-castinga, detaljno odražava kako PostGIS rješava sličan zadatak kada koristi Indeksi su. pokloni Korištenje API-ja izgrađenog oko Go mikroslužbe, U usporedbi, prethodno rješenje Node.js upravljalo je oko 10.000 parova koordinata za 250 zona, uključujući nadglavlje mrežnih zahtjeva i operacija backend. Postigli smo sposobnost obrade oko 100.000 parova koordinata u sekundi Ovo značajno poboljšanje brzine obrade omogućilo je mnogo brže sastavljanje popisa posjećenih zemalja korisnika. Njihovi rezultati aplikacija je vidjela 160% povećanje aktivnih korisnika i 107% povećanje dijeljenja korisnika Rješenje ostaje u upotrebi i danas i nastavlja učinkovito rješavati sve veći volumen zahtjeva i geografskih zona.Naravno, cijeli backend radi s manje od gigabajta RAM-a, pokazujući optimizirano korištenje resursa.
