Informatika | Térinformatika » Útkeresés a GIS-ben

Útkeresés a GIS-ben 2. előadás Az útkeresés fogalma, útkeresési feladatok Útkeresés alatt általában azt az eljárást értjük, mely megadja, hogy egy kiindulópontból mely útvonal(ak) optimális(ak) egy vagy több célobjektum eléréséhez. A feladatot felhasználói szempontból két tipusra oszthatjuk: − a vizsgálat meglévő úthálózaton történik; − a vizsgálat a terepen, úthálózattól függetlenül, azt kizárva vagy benfoglalva történik. Meglévő úthálózat esetén a feladatot rendszerint a szállítási költségek optimalizására használják. − 1996-ban pld. az USA Sears áruházlánc megbízta az ESRI-t, hogy az ArcView Network Analyst segítségével optimalizálja az áruház ellátási útvonalakat (2 000 000 $ megtakarítás évente). − vészjárművek (mentő, tűzoltó) útvonaltervezése; − szolgáltató járművek (iskolabusz, szemétgyűjtő) utvonalak; − inteligens közlekedési rendszerek: − útvonal keresés cím

alapján; − térkép az autóban és GPS navigáció; − közlekedési áramlátok elemzése (honnan hova mátrixok). Ha a vizsgálatot a terepen végzik: − katonai járhatósági térképek; − előzetes útvonal tervezés; − tetszőleges vonalas műtárgy előzetes tervezése. A meglévő úthálózat elemzéséhez előnyösebbek a vektoros rendszerek. A terepi útkereséshez mindkét adatmodell alkalmas, a vektoros rendszert rendszerint raszterizálják a feladat megoldása során. A megoldást minden esetben legrövidebb út kereső gráf algoritmusokkal végzik. Ilyen algoritmus például a Dijkstra algoritmus (Dijkstra holland matematikus (1930) 1959-ben publikálta). Különösen nagy jelentősége van a kérdés megoldásában az attribútumoknak. A vektoros rendszerekben az úthálózat elemzéséhez rendelkezésre áll a tulajdonképpeni gráfstruktúra a csatlakozó attribútumokkal. 1 Ezt az úthálózatot már egyszerű súlyozott irányított gráfokká

alakítani, hiszen az adatbázisban így vannak tárolva (node-link) A kérdés az, hogy milyen attribútumokra lesz szükségünk és ebből miként kaphatjuk meg a súlyokat vagy impedanciát. 2 az ív attribútum táblázathoz csatlakozó forduló táblázat összetett kulcs az ívtől ívig jelentősen javítja az eredményességet a dinamikus szegmentálás Általában nincsennek attribútumok a vesztett magasságokra, gyakran hiányoznak a dinamikus forgalmi adatok is, bár egyes városokban létezik ilyen infrastruktúra (forgalom észlelés, kisugárzás, automatikus attribútum tábla frissítés. El kell dönteni, hogy mit optimalizálunk: időt utat } mindegyikhez a megfelelő impedancia függvényt költséget kell kialakítani (lehetőség képlettel táblázati oszlopot csinálni) Végeredmény impedancia gráf, melyen az utazó ügynök feladat vagy egyszerűbb esetben a két pont közötti legrövidebb út feladat oldandó meg. Raszteres rendszerek esetében −

ki kell jelölni az elemi gráf éleket és cúcsokat; − meg kell határozni az elemi élekre vetíthető impedancia összetevőket különös figyelemmel a meglévő utakra, illetve a leküzdhetetlen terepi akadályokra; − megkell határozni az impedancia számítási képletet; − hatékony legrövidebb út gráfkereső algoritmust kell találni, mivel akár több millió gráf él is szerepel a keresésben; – ha a feladat mint igen gyakran előzetes tervezési célokat szolgál, úgy politikai okokból célszerű több variánst kidolgozó algoritmust használni. Ilyen algoritmus használata esetén gondoskodni kell arról, hogy a két megoldás optimalitásban közel legyen egymáshoz, és ügyesen illusztrált érvekkel a jobb megoldást lehessen elfogadtatni. Legegyszerûbb, ha a pixelek középpontját tekintjük csomópontnak. El kell még döntenünk hogy a gráf éleit 4 vagy 8 irányba képzeljük. Célszerűbb ha 8 irányt választunk, mivel ez pontosabb. A

korlátozott útirányok okozta hibák Helyes út maximuma: Korlátozott út NYÍLT MEZÕ ERDÕ VÍZEK lr = lt 1+1 ( v2 2 2 ) + (1 + 1 2 = ) 2 2 2+ 2 ≈ 1.082392200 A felvett megengedett utak pixelenként két féle hosszat tesznek lehetõvé: ha a pixel oldalhossza l, úgy a rövidebb oldal l/2, a hosszabb pedig 1.41*l/2 hosszú. ,-l/2-, ,-l/2-, v1 1 3 Ha figyelembe vesszük, hogy a haladást nehezítõ körülmények egyenértékûek azzal, hogy megnyujtjuk az utat, az ellenállási tényezõk bevezetésével a feladatot visszavezethetjük a legrövidebb út keresésre. Hasonló eredményre jutunk, ha a megtett utat haladási vagy építési költség gráffal helyettesítjük. A költségeket (ellenállást) befolyásoló tényezõk (rétegek): − domborzat − talajok − vizek – felszínborítás − földhasználat − közlekedési hálózat A tervezési céltól függõen más és más súllyal kell figyelembe venni az egyes tényezõket. Ha

járhatósági térképet tervezünk, úgy az utakat ábrázoló vékony pixeleket kell figyelembe venni és az utakon azok tipusának megfelelõen zérus vagy bármely terephez képest csökkentett ellenállást veszünk figyelembe. Ugyancsak járhatósági térképek esetén a vízfolyások vastag raszterezést igényelnek, mivel ellenkezõ esetben az ábrán létható módon egyes gráfoldalak nem vesznek tudomást az akadály meglétérõl. Tervezés esetén a tényezõk figyelembe vételét a tervezési irányelvek szabják meg. Például, ha nagyfeszültségû vezetéket tervezünk, úgy célszerû, ha az útat merõlegesen metszi, ezért az útnak viszonylag nagy ellenállást kell adnunk. A probléma lokalizálható, ha az ellenálás vektor, mint az IDRISI-ben. Az ellenálások megválasztásánál célszerû iterációs eljárást alkalmazni, mivel az elõbbi példánkat figyelembe véve nem közömbös a tényezõ megválasztásánál, hogy a vezeték hányszor metszi az

úthálózatot. A következõkben ismertetendõ legrövidebb útkeresõ Dijkstra algoritmus A* heurisztikus módosítása két pont esetére lehetővé teszi a keresési gráf jelentős csökkentését. Az ábrán látható az akadály, a legrövidebb irány, bizonyos cellák legrövidebb iránya, a végpont, és azok a cellák, melyeket meg sem kellett vizsgálnia az algoritmusnak. Az algoritmus ugyanis mindaddig keresi a legrövidebb irányokat míg el nem éri a célpontot, ezután már nem vizsgálódik a gráf még be nem járt részein. Minél kisebb a költség annál világosabb a szín a példában. A fe- kete négyzet a keresési tartomány 4 A 3 rövid út példában a zöld az erdõt, a sötét kék a tavakat jelöli. Az “út” megkerüli az akadályokat a tervezett út kikerüli a feketével pontozott “ellenséges” területeket felhasználva a meglévõ utat és elkerülve az erdõket itt az ellenséges terület költségét végtelenre választották. 5

a fekete pontokkal jelölt “ellenséges” területetrõl történõ belátást nem tudja teljesen elkerülni (a súly itt nem végtelen), hisz átkelés csak a hídon van, de a láthatóság minimális, Az algoritmus a jobb utakat választja, annak ellenére, hogy az erdõn keresztül vezetõ közvetlen távolság sokkal rövidebb, az utak költsége mintegy 200-szor kisebb mint a közönséges terepen haladás költsége. Érdekes, hogy a baloldalon a kissé hosszabb vastagabb utat választotta a rövidebb vékonyabbal szemben. csak a fehér ponttal határolt zónán belüli pixeleket vonta be az A* algoritmus a keresésbe, szemben a fekete négyzettel jelölt keresési tartománnyal. Ez kevesebb mint a keresési pixelek negyede. Bonyolultabb esetekben ez felmehet a pixelek feléig. 6 Ez a kiinduló gráf, a kezdõ pont a D, a költségeket barna számok jelölik az élek mellett. Az eredményt ez az ábra mutatja, ahol a D-tõl számított legrövidebb utakat alkotó élek

kék színnel vannak jelölve, a csomópontok melletti kék számok pedig a D-tõl mért legrövidebb távolságok. Az első lőpésben az algoritmus meghatúrozza D távolságát saját magától ami természetesen 0. Ezután 10-szer megismétlõdik a következõ eljárás: megjavítjuk a távolság becslést a választott csúcspont szomszédos csúcspontjaira és kiválasztjuk a D-hez legközelebbi, még kiválasztatlan élet. elsõ lépésben kiszámítjuk A, E, és J távolságát, s mivel az utóbbi a legkisebb kijelöljük a DJ élet és J csúcspontot. második lépésben megismételjük most már J-ről a vizsgálatot K-ra és Ere, E-re 12-t kapunk, ez nagyobb mint a meglévő 7 ezért ezt nem változtatjuk, K-ra 5-öt kapunk, ez a J csomópontról szomszédos legkissebb csomóponti érték: bekékítjük. 7 harmadik lépésben K-ról számoljuk E, F, G, L értékeit. E kivételével a többi értéket pirossal beírjuk, Enek pedig bekékítjük korábban kapott

legkisebb értékét, mivel az összes rendelkezésre álló érték közül ez a legkisebb. negyedik lépésünket értelem szerint E-ről kezdjük és kiszámoljuk innen A, B, F értékeit. A-ra, F-re nagyobbat kapunk, meghagyjuk régi értékét, B--re beírjuk 9-et, mivel a legkisebb érték három csúcson is 9, bármelyiket választhatjuk, mi kékítsük be F-et azzal az éllel amivel 9 kijött. ötödik lépésünkben F-ről B-t és G-t számítjuk, de mivel nagyobbak a meglévőknél meghagyjuk a piros értékeket. A legkisebb érték most 9 az An és B-n, kékítsük be A-t, a 9-et produkáló DA éllel együtt hatodik lépésben A-ból csak B-t tudjuk meghatározni, de ez 18 lenne, tehát meghagyjuk B meglévő 9-ét és mivel ez a legkisebb, bekékítjük a létrehozó EB éllel. hetedik lépésben B-ből kiszámoljuk C-t és G-t, G nagyobbra adódik (18) a meglévő 11-nél ezért ezt meghagyjuk, C-hez pedig beírunk 14-et. Mivel a hálózatban legkisebb még nem kék

érték a G-n 11, azt bekékítjük a létrehozó KG éllel együtt. nyolcadik lépésben G-ről számoljuk C, H és Lértékét. H értékét 11+4=15 beírjuk, C és L nagyobbra adódott a régi értékeknél, ezért azokat megtartjuk. Mivel a legkisebb még nem kék érték L ezt bekékítjük a létrehozó KL éllel együtt. kilencedik lépés: L-ből kiszámoljuk H-t, de ez nagyobb a meglévő értéknél ezért azt meghagyjuk, a legkisebb érték 14 a C-n ezért bekékítjük a létrhozó BC éllel együtt. tizedik lépésben C-ről kiszámítottuk H-t, de nagyobb lett a meglévő értéknél ezért azt meghagytuk. A legkisebb még nem kék érték H-nál 15, ezért ezt bekékítjük a létrehozó GH éllel együtt. 8 A létrejött hálózat kék vonalai megadják D-től a kérdéses csúcsig a legrövidebb topológiát, a csúcsok melletti számok pedig az út hosszát. Természetesen a “hossz” csak választott mérőszám, mely lehet költség, idő, komfort, és

más felhasználási tényező is. IDRISI földhasználat mezőgazdaság súrlódás 1 magyarázat alapköltség lombos erdő 4 a fákat ki kell vágni, elvinni, eladni tűlevelű erdő 5 olcsóbban adható el városi 1000 burkolat 1 elővárosi 1000 parlag-sóder víz 1 1000 olyan nagy költség, hogy virtuális határ alapköltség olyan nagy költség, hogy virtuális határ alapköltség Tervezendő gyárhoz (fehér kör) leágazást tervezünk a távvezetékről (piros vonal). – először megbecsüljük, hogy a különféle földhasználaton haladni hányszorosa a mezgazd.terepi haladásnak, mely 1; pszihikai határ – a fenti értékekkel value fájlt kell csinálni – Az így kapott érték fájl és az eredeti kép felhasználásával az ASSIGN művelettel létrehozunk egy FRICTION nevű súrlódási képet. – a távolságszámítás alapját meghatározó objektumot tartalmazó vektor fájlt (NEW PLANT) raszterizálnunk kell (az INITIAL-lal előbb

üres képet csinálunk neve PLANT, majd a POINTRAS-szal rávisszük a NEW PLANT nevű vektoros pontobjektumot). – a COST függvényt futtatjuk Cost Push módban az Analyzis/Distance csoportból, bemenő adatai az előbbi PLANT illetve a FRICTION, a kimenő kép neve COSTDIST. A művelet eredményekép-pen létrejövő kép, melyet a következő lapon mutatunk be, azonban még nem a legrövidebb út, hanem csak a kijelölt ponttól mért súlyozott, pixelenként akkumulált költség-távolsági kép. – az INITIAL-lal POW ER nevű üres képfájlt gyártunk, majd a LINERAS-szal raszterizáljuk – végül a PATHWAY-nak be adva a COSDIST és POW ER bemenő adatot megkapjuk NEWLINE-t. – ezt vektorizálva ráraktuk az erdeti kompozitra és .map kiterjesztássel kompozit térképként elmentettük. megoldhatnánk a végeredményt olyan OVERLAY val mely a maximális értékeket viszi át, ha elötte a raszteres newline-t átosztályozzuk, úgy hogy a vonal értékei nagyobbak legyenek

bármelyik értéknél az eredeti raszteren. 9