[iFlop]

Kas siin foorumis on kedagi, kes on geoinfosüsteemidega kokku puutunud? Probleemi püstitus on järgnev - sisendiks on suur hunnik gps logisid. Kokku üle 10 miljoni punktiga. Väljundiks soovin saada kõiki punkte ümbritsevat välist joont ehk outer boundary'it.

Genereerisin ühe näide ka - sisendiks 3 gps tracki:

Spoiler

Track 1:

<trkpt lat="59.284925283864141" lon="23.401982635259628"/> <trkpt lat="59.281407231464982" lon="23.404629975557327"/> <trkpt lat="59.280533585697412" lon="23.403289960697293"/> <trkpt lat="59.283555429428816" lon="23.403993789106607"/> <trkpt lat="59.296758603304625" lon="23.372893324121833"/> <trkpt lat="59.303108314052224" lon="23.364553581923246"/> <trkpt lat="59.302298035472631" lon="23.364308327436447"/> <trkpt lat="59.302979400381446" lon="23.363655377179384"/> <trkpt lat="59.302781503647566" lon="23.365656053647399"/>

Track2:

<trkpt lat="59.302746886387467" lon="23.363999035209417"/> <trkpt lat="59.298605052754283" lon="23.389223618432879"/> <trkpt lat="59.293650425970554" lon="23.389327470213175"/> <trkpt lat="59.292663624510169" lon="23.394871680065989"/> <trkpt lat="59.287073900923133" lon="23.403928158804774"/> <trkpt lat="59.284617248922586" lon="23.401056183502078"/>

Track3:

<trkpt lat="59.285717541351914" lon="23.40284077450633"/> <trkpt lat="59.284662678837776" lon="23.402929287403822"/> <trkpt lat="59.284217599779367" lon="23.401788510382175"/> <trkpt lat="59.284808021038771" lon="23.400113387033343"/> <trkpt lat="59.285496510565281" lon="23.403317285701632"/> <trkpt lat="59.286619098857045" lon="23.409487875178456"/> <trkpt lat="59.281139178201556" lon="23.420599931851029"/> <trkpt lat="59.280311213806272" lon="23.426740597933531"/> <trkpt lat="59.28347353823483" lon="23.42307728715241"/> <trkpt lat="59.279416194185615" lon="23.425831245258451"/> <trkpt lat="59.279216285794973" lon="23.419706504791975"/> <trkpt lat="59.286826802417636" lon="23.407158879563212"/> <trkpt lat="59.285796331241727" lon="23.402006439864635"/>

Soovitud väljund peaks olema selline:

Spoiler

<trkpt lat="59.303108314052224" lon="23.364553581923246"/> <trkpt lat="59.302859539166093" lon="23.364884834736586"/> <trkpt lat="59.302781503647566" lon="23.365656053647399"/> <trkpt lat="59.302859539166093" lon="23.364884834736586"/> <trkpt lat="59.302532561123371" lon="23.36531013250351"/> <trkpt lat="59.298605052754283" lon="23.389223618432879"/> <trkpt lat="59.293650425970554" lon="23.389327470213175"/> <trkpt lat="59.292663624510169" lon="23.394871680065989"/> <trkpt lat="59.287073900923133" lon="23.403928158804774"/> <trkpt lat="59.285906637087464" lon="23.402564087882638"/> <trkpt lat="59.286826802417636" lon="23.407158879563212"/> <trkpt lat="59.286341238766909" lon="23.407962955534458"/> <trkpt lat="59.286619098857045" lon="23.409487875178456"/> <trkpt lat="59.281139178201556" lon="23.420599931851029"/> <trkpt lat="59.280535597354174" lon="23.4250757843256"/> <trkpt lat="59.28347353823483"  lon="23.42307728715241"/> <trkpt lat="59.280311213806272" lon="23.426740597933531"/> <trkpt lat="59.280535597354174" lon="23.4250757843256"/> <trkpt lat="59.279416194185615" lon="23.425831245258451"/> <trkpt lat="59.279216285794973" lon="23.419706504791975"/> <trkpt lat="59.286341238766909" lon="23.407962955534458"/> <trkpt lat="59.285496510565281" lon="23.403317285701632"/> <trkpt lat="59.28539827466011" lon="23.402867009863257"/> <trkpt lat="59.284662678837776" lon="23.402929287403822"/> <trkpt lat="59.284436535090208" lon="23.402349427342415"/> <trkpt lat="59.28416739217937" lon="23.402551850304008"/> <trkpt lat="59.283555429428816" lon="23.403993789106607"/> <trkpt lat="59.282562509179115" lon="23.403764544054866"/> <trkpt lat="59.281407231464982" lon="23.404629975557327"/> <trkpt lat="59.280533585697412" lon="23.403289960697293"/> <trkpt lat="59.282562509179115" lon="23.403764544054866"/> <trkpt lat="59.28416739217937" lon="23.402551850304008"/> <trkpt lat="59.284348022192717" lon="23.402126217260957"/> <trkpt lat="59.284217599779367" lon="23.401788510382175"/> <trkpt lat="59.284808021038771" lon="23.400113387033343"/> <trkpt lat="59.284939114004374" lon="23.400735072791576"/> <trkpt lat="59.296758603304625" lon="23.372893324121833"/> <trkpt lat="59.302532561123371" lon="23.36531013250351"/> <trkpt lat="59.30267765186727" lon="23.364424835890532"/> <trkpt lat="59.302298035472631" lon="23.364308327436447"/> <trkpt lat="59.302979400381446" lon="23.363655377179384"/> <trkpt lat="59.302896754816175" lon="23.364489041268826"/> <trkpt lat="59.303108314052224" lon="23.364553581923246"/>

Siin see näide ka visuaalselt google kaardil:
https://www.google.com/maps/d/viewer?mid=1D6-xS5NIHenCyXkAoW_bkq_L1EjLW6k

Mõned mõtted:

1) Üks variant oleks vastav programm algusest lõpuni ise valmis kirjutada. Üldine arusaam, kuidas seda probleemi lahendada saaks, on mul olemas, aga see on sellist tüüpi probleem, kus tõenäoliselt ei ole vaja hakata ise jalgratast leiutama

2) QGIS - selle vabavaralise programmiga olen pisut mänginud, aga ühtegi vähegi keerukamat asja ma seal teha ei oska.

3) PostgreSQL + PostGIS - alles praegu hakkasin seda uurima. Esmapilgul on tundub see vist kõige mõistlikum suund. Kui just QGISis selle probleemi lahendus päris triviaalne ei ole.

[infidel]

QGISis pead natuke käsitööd selle jaoks tegema või Pythonis veidi juurde kirjutama.
PostGISiga on lahendus täielikult automatiseeritav. Saab kasutada näiteks https://postgis.net/docs/ST_ConcaveHull.html funktsiooni. Samas võib ka näiteks võtta jooned ST_Collect abil kokku, ST_Buffer abil pinnaks ja siis ST_ExteriorRing abil välimine joon.

Mis kujul väljund peaks olema? Kas samuti GPX või midagi muud?

[kalvis]

Mul oli vastupidi vaja seespool ala leida punktid. Paraku oli tööandjal võimas GIS süsteem - seal oli selline päring olemas ja genereeris tavalise CSV faili. Paraku on selline asi GIS süsteemi enda põhine. Väliselt saab teoorias exceli makrodega teha kui koordinaadid teisendada X ja Y väärtusteks. Paraku tuleb ala jagada kolmnurkadeks ja teha IF käsuga - kas on mõnes kolmnurga sees või mitte ja suht triviaalne ülesanne. Netis on vastavad kolnurga sees või väljas algoritmid olemas aga tegu on paraja pähkliga ja üksjagu arvutusvõimsust (ühe kolnurga sees on vaja lahendada 3 võrranditingimust - ruudud, ruutjuured jne.)
Hulknurga puhul saab siiski kasutada üht lihtsustust (see oli üks meetod ka kolmnurkade lahendusviisis) sirgete võrranditekontroll kas on väljapool või seespool. Iga hulknurga külg on sirge võrrand ja kontrollitakse punkti asumist väljapool sirget ja tuleb kontrollida kõik sirged ära. See toimib hästi kui ala on nagu ring. kui ei ole siis tuleb hulknurk jagada osahulknurkadeks, et oleksid ringilaadsed.
Teoorias üks lihtsamaid meetodeid on ringidega - teed miinimumringi ja teed maksimum ringi. Miinimumringi sees olevad punktid on kõik valed. Maksimumringist väljapool on kõik õiged. Kahe ringi vahel olevad punktid on hall ala ja need teed käsitsi.

[iFlop]

infidel, Tänud kaasa mõtlemast! Esialgu proovisin PostGISi nende samade testandmetega. ST_ConcaveHull puhul tundus, et jooni, või õigemini seda, kuidas punktide vahel liiguti, ignoreeritakse ning tulemus arvutatakse lihtsalt kõikide punktide järgi. See mulle kahjuks ei sobi.

Aga ST_ExteriorRing + ST_Buffer + ST_Collect kombo toimib ideaalselt
Lisaks joonistatakse 1m raadius ka juurde, mis mulle pigem meeldib.

Mõlemad väljundid lisasin samale kaardile:
https://www.google.com/maps/d/viewer?mid=1D6-xS5NIHenCyXkAoW_bkq_L1EjLW6k

Eks näis kuidas see päris andmetega toimib. Mis väljundisse puutub, siis igasugune tekstikujuline koordinaatide jada sobib. Hetke päring oli selline, kus iga track on LINESTRING:

[infidel]

ST_ConcaveHull puhul on oluline teine parameeter (pctconvex) - kui palju tulemust siledamaks tõmmatakse.
Selle asemel, et joont tüüpide geometry ja geography vahel konverteerida, võiks ta kohe sellisele kujule (nt geography või siis Eesti koordinaatsüsteemis geometry, SRID=3301) panna, mis meetriga kaugusi lubab. Nii käib arvutus veidi ressursisäästlikumalt.
Väljundina võid kasutada ST_AsKML, siis tõstab kohe Google kaardile sobivale kujule. Või siis talletada tulemus tabelina, QGIS suudab neid kenasti näidata.

[iFlop]

Liigutasin päris andmed baasi ning ST_ExteriorRing + ST_Buffer + ST_Collect kombo töötas ilusti ühe väikse andmeseti peal. Aga see põhiline andmesest, kuhu jäi üle 9 miljonit punkti, mis jaotatud ~1400 linestringi peale, sellest midagi välja ei tulnud. Päring tahtis liiga palju mälu saada.

Järgmisena proovisin seda, et tegin igast line-stringist polügoni, kasutades seda sama kombot + lihtsustamine ning salvestasin selle baasi. Mingi hetk liikusin juba QGISi ning sealt edasi Dissolve + Delete holes + Multipart to singleparts (sest algandmetes jäi ikkagi mingit jura sisse) + Polygons to lines ja lõpuks gpx export. Tulemuseks täpselt see, mida soovisin

Nüüd vaatasin, et QGISis saab sama moodi line-stringidest buffer abiga polügone teha
Samas see PostGIS ja QGISi kombo ongi antud juhul kõige mõistlikum. Seda välisjoone tulemit võiks ehk paar korda aastas uuendata ning kui lähteandmed baasis, saab QGISis neid ka teistel viisidel visualiseerida.

infidel, tänud veelkord kaasa mõtlemast!

[ref]

[iFlop]

ref, jah, vaikimisi seadistus. Masinas 16GB mälu ning antud Postgre päring tiksus üle poole tunni enne kui selle ise ära lõpetasin. Selle aja jooksul sõi päring kogu arvuti mälu ära ning lisaks swappis päris korralikult SSD'le. Aga järgmisel korral vaatan kindlasti mälu seadistuse üle ja proovin veel.
Aga õnneks olen nüüd QGISi piisavalt kasutanud ja saan selle programmi loogikale pihta. Lõpptulemuse saamiseks on ikkagi vaja veidi käsitööd teha ning QGIS tundub selleks sobivam, kuigi eks seda saaks ka otse andmebaasis teha.