34. FEJEZET - A POLIGON FEDVÉNYEZÉSI MŰVELET (GIS,térinformatika,térkép,geodézia)


   
 
 

34. FEJEZET - A POLIGON FEDVÉNYEZÉSI MŰVELET

 
Tartalom
<<< Előző fejezet               Következő fejezet >>>
 

 

34. Fejezet - A POLIGON FEDVÉNYEZÉSI MŰVELET

Szerkesztette: Denis White, Environmental Protection Agency, Corvallis, OR

Magyar változat: Sárközy Ferenc, Budapesti Műszaki Egyetem

 

A. BEVEZETÉS

A poligon fedvényezés hagyományai

B. A POLIGON FEDVÉNYEZÉSI MŰVELETEK ÁLTALÁNOS ALAPELVEI

Poligon fedvényezést igénylő műveletek

C. FEDVÉNYEZÉSI ALGORITMUSOK

Célkitűzés

Adottak

Eljárás

D. SZÁMÍTÁSI KOMPLEXITÁS

E. METSZÉSI PROBLÉMÁK

1. Szomszédos vonalak

2. Forgács (töredék) poligonok

A forgácsok megszüntetése a fedvényezés alatt

A forgácsok megszüntetése a fedvényezés után

IRODALOM

ELLENŐRZŐ KÉRDÉSEK

 

MEGJEGYZÉSEK

 

34. Fejezet - A POLIGON FEDVÉNYEZÉSI MŰVELET

Szerkesztette: Denis White, Environmental Protection Agency, Corvallis, OR

Magyar változat: Sárközy Ferenc, Budapesti Műszaki Egyetem

 

A. BEVEZETÉS

- az előzőekben megvizsgált egyszerű algoritmusok képezik a vektor GIS programrendszerek egyik legösszetettebb műveletének, a poligon fedvényezési műveletnek az alapját

A poligon fedvényezés használatának hagyományai

- a poligon fedvényezés három hagyományos területe a következő:

1. Tájtervezés

- földrajzi adat-rétegek (pl. szociális és környezeti tényezők) egymásra helyezése olymódon, hogy térbeli kapcsolataik felhasználhatók legyenek a földhasználati döntéseknél

- a téma kulcs műve: McHarg, 1969, Design with Nature

2. Halmazelmélet

- a poligont elképzelhetjük úgy is, hogy egy halmazt képvisel

- amikor két halmaz (poligon), A és B fedésbe kerül, grafikus illusztrációt nyerünk a metszés és unió halmazműveleteihez

- A és B egymást fedő közös területe egyenlő az A.AND.B metszettel

- összevont területük pedig az A.OR.B unióval

34.1. ábra - kiosztandó a Boolean műveletek tizenhat kombinációja

- 16 kombináció vagy Boolean kifejezés hozható létre pl.

- A.AND.(NOT B), azaz A-nak mindaz a területe, amit nem fed B

- NOT (A.OR.B), azaz az A-n és B-n kívüli világ: (NOT A).AND.(NOT B)

- a legtöbb poligon fedvényezési műveletében a metszet tarthat a legnagyobb érdeklődésre számot, vagyis az a terület, amely A-ban és B-ben közös

3. Terület interpoláció

Adott: az A terület lakossága és az a tény, hogy az A és B területek átfedik egymást

Megbecsülendő: a B terület lakossága

- a probléma úgy oldható meg, hogy területarányosan elosztjuk A népességét, azaz a fedett részre eső népesség is arányos a fedett területtel

- ez egyszerű módja annak, hogy megbecsüljük területek népességét más területekre ismert népességi statisztikák alapján

- pl. a választási körzetek népességének becslése a népszámlálási körzetek népessége alapján

- ez a módszer feltételezi, hogy A-n belül a népsűrűség állandó, de léteznek valósághűbb változatai is ennek a technikának

- l. 41. Fejezet

 

 

B. A POLIGON FEDVÉNYEZÉSI MŰVELETEK ÁLTALÁNOS ALAPELVEI

- a GIS normális poligon fedvényezési esetben két térképréteget használ és egymásra helyezi azokat

- mindkét térkép réteget önmagukban átfedés nélküli poligonok borítják

- ha az egyik réteget kéknek, a másikat pedig pirosnak képzeljük, úgy feladatunk abból áll, hogy megkeressük az összes poligont a kombinált lila rétegen

- egy lila poligon attribútumai tartalmazni fogják a létrehozó kék és piros poligonok attribútumait

- a folyamatot úgy tekinthetjük, mint az attribútumok "konkatenálását" (összekapcsolását)

- rendszerint egy új attribútum táblázat is készül, amely vagy a kombinált régi attribútumokból, vagy olyan új attribútumokból áll, amelyek logikai és aritmetikai műveletek segítségével a régiekből kerülnek kialakításra

- a fedvényezéskor létrejövő poligonok számát nehéz előre megmondani

- sok olyan poligon keletkezhet, mely ugyanattól a piros és kék poligon pártól származik, és ugyanazt a lila attribútumot viseli

- ha két térképet hoznak fedésbe az eredmény 3 és 4-szeres ív-metszések keveréke lesz

- négyszeres ív metszések nem általánosak az egyszerű poligon térképek fedvényezésekor

Poligon fedvényezést igénylő műveletek

1. Ablakolás

- olyan művelet, amelyben egy ablakot helyeznek a térképre és az ablakon kívüli részeket elhagyják, a poligon fedvényezésnek egy speciális esete

2. Övezetgenerálás

- a pontok, vonalak és poligonok köré történő övezet generálás egy másik eset

- az övezeteket minden pont és egyenesdarab köré külön generálják

- a kombinált övezetet poligon fedvényezéssel hozzák létre

3. Topológia generálás

- az a folyamat, melyben a digitalizált "spagetti" struktúrából (l. 12. Fejezet) pontokat, vonalakat és területeket hoznak létre

- ahol csak metszi egymást két vonal, a vonalakat elvágják és egy pontot iktatnak közbe

- az eredmény olyan pont, egyenes és terület halmaz, mely különleges szabályoknak engedelmeskedik

 

C. FEDVÉNYEZÉSI ALGORITMUSOK

- a poligonok fedvényezéséhez először meg kell keresni a piros és kék poligon határok összes, egymással alkotott metszéspontját

- az ívek jobban használhatók erre a műveletre mint a poligonok,mivel:

- a metszéspontokat csak egyszer és nem négyszer kell megkeresni

- több címke információ áll rendelkezésre (l. lejjebb)

- példa fedvényezési műveletre

34.2. ábra - Egyszerű fedvényezési példa

Célkitűzés

- fedvényezz két különböző tematikájú térképet és határozd meg az új poligonok kombinált attribútumait

- pl. hozz fedésbe egy talajtérképet egy növényzettérképpel, és hozd létre a poligonok új halmazát, az attribútumok új halmazával együtt

Adott

- két átfedő poligon az alábbiak szerint:

- a piros térképen a poligon attribútuma: A

- a kék térképen a poligon attribútuma: 1

- a külvilág mindkét térképen 0-val van kódolva

- két metsző ív, amely meghatározza a poligonok határát:

1. Piros térkép (vékony vonalak): (0,1) (0,3) (2,3) (2,1) (0,1)

Poligonok: jobboldali poligon A, baloldali poligon 0

2. Kék térkép (vastag vonalak): (1,0) (3,0) (3,2) (1,2) (1,0)

Poligonok: jobboldali poligon 0, baloldali poligon 1

Eljárás

- a metszéspontok meghatározása után hat új ív jött létre, három az egyes számú ívből és három a kettes számú ívből:

1. (0,1) (0,3) (2,3) (2,2)

2. (2,2) (2,1) (1,1)

3. (1,1) (0,1)

4. (1,0) (3,0) (3,2) (2,2)

5. (2,2) (1,2) (1,1)

6. (1,1) (1,0)

- mivel minden bemenő ív jobboldali és baloldali poligon címkéje ismert, a metszéspontok meghatározása után ismertekké válnak az új poligonok címkéi is

- négy új poligon van

- attribútumaik a piros és kék attribútumok kombinációi: 00, A0, A1 és 01

- az ívek jobboldali és baloldali címkéi, a metszések geometriájából levezetve, az alábbiak:

Ív Jobb Bal

1 A0 00

2 A1 01

3 A0 00

4 00 01

5 A0 A1

6 00 01

- egy összetettebb példa:

34.3. ábra - Összetett fedvényezési példa

- ebben az esetben az 1, 2, 4, 5 és 7 sorszámú ívek jobboldali és baloldali címkéi a metszéspontok geometriájából válnak ismertté:

1J: A0 1B: 00

2J: A1 2B: 01

4J: A1 4B: 01

5J: 01 5B: 00

7J: A1 7B: A0

- a többi ív címkéit is meg kell határozni

- a címkék átadódnak egy poligon körüljárása során az egyik ívről a másikra:

3J: ugyanaz kell, hogy legyen mint 2J és 4J

6B: 2B-ből és 4B-ből

- a 3 számú ív a piros hálózat része volt, így a talaj címkéi ismertek, baloldali címkéjének maradék (kék) része ugyanaz kell, hogy legyen, mint jobboldali címkéjének kék része

- mivel 3J: A1 ezért 3B: B1

- tehát 6J: B1

- hogy kaphatók meg a 8 számú ív kék címkéi?

- használd a pont a poligonban eljárást, hogy megkeresd a befoglaló kék poligont

- használj olyan adatszerkezetet, melyben a poligonhatárt képező ívek belső oldalukkal rámutatnak a poligonban lévő szigetek külső oldalára

- pl. 5J ® 4B ® 6B ® 8B ® 2B ® 5J

- tehát a 8-as számú ív címkéi - 8B: 01, 8J: C1

- az algoritmus végső lépése az összes új poligon azonosítása olymódon, hogy sorra veszi minden poligon körül az azt alkotó íveket mindaddig, amíg minden ív minden bal és jobb oldala nem lesz egy egyedileg számozott poligonnal azonosítva.

 

D. SZÁMÍTÁSI KOMPLEXITÁS

- a poligonfedvényezés számításilag intenzív és időigényes, éppen ezért ez a legkomplexebb művelet a legtöbb vektor alapú GIS programban

- jelölés: ha az n objektum feldolgozására fordított gépidő arányos az n objektum számmal, a számítási komplexitás "n nagyságrendű", vagy az angol elnevezés rövidítésével O(n)

- ha n2-tel arányos, úgy azt mondjuk, hogy "n négyzetnagyságrendű" vagy rövidítve O(n2)

- fontos tudni:

- meddig tart adott számú poligon fedvényezése?

- mi befolyásolja a felhasznált időt?

- nyilvánvalóan az ívek és poligonok száma befolyásolja a szükséges számítások mennyiségét

- rendszerint lehetséges a fedvényezésbe vont poligonok számának meghatározása

- az ívek száma, durván, a poligonak számának háromszorosa

- vannak más tényezők is, amelyek befolyásolják a számítási időt (pl. a cikk-cakkos határvonalak), de ezek mérése nehézségekkel jár

- ha n1 poligont fedésbe hozunk n2 poligonnal, hány poligont kapunk eredményül (feltételezzük, hogy a térképek különbözőek)

- a minimum n1+n2, ha a két térkép poligonjai egyáltalán nem metsződnek

- a maximum a végtelen, ha a vonalak végtelenül cikk-cakkosak

- tipikus esetben, az álpoligonoktól eltekintve, az eredmény 3-4-szer (n1+n2)

- ha mindegyik n1 számú piros poligont össze kell hasonlítani mindegyik n2 számú kék poligonnal, az algoritmus O(n1n2) lesz

- ha egyből meg tudnánk találni mindazokat a kék íveket, amelyek metsződni fognak egy adott piros ívvel, akkor létrehozhatnánk egy O(n1) algoritmust, mely adott feladat nagyságnál jelentősen növelné a hatékonyságot

- hogy ilyen módon találhassuk meg az íveket, egy hatékony térbeli indexelési módszerre van szükségünk

- az egyik legsikeresebb módszer a mozgó sáv elvét alkalmazza:

- rendezzük mind a piros, mind a kék íveket x növekvő értékei szerint

- dolgozzuk fel az íveket balról kezdődően jobbfelé mozogva, mintegy kisöpörve egy sávot a térképen keresztül

- csak a sávba eső ívek lesznek megvizsgálva

- mivel az ívek rendezve vannak, gyorsan megtaláljuk a sávba esőket mind a kék, mind a piros térképen

- a GIS piacon kapható legjobb fedvényező rutinok közel O(n1+n2) idő alatt végzik a műveletet

- egy több tízezer poligonnal rendelkező térkép fedvényezése egy hasonló térképpel egy órán belül elvégezhető egy mérsékelt méretű számítógépen

 

E. METSZÉSI PROBLÉMÁK

- a számítógép pontossága következtében a vonalak akkor is nagy pontossággal lesznek tárolva, ha maga az alapanyag nem elég pontos

1. Egymás melletti vonalak

- a következő rajz egy olyan esetet mutat be, melyben két vonal metszi egymást

- a következő rajz egy hasonló esetet mutat be, ahol azonban a vonalak nem metszik egymást

- szükség van olyan algoritmusokra, amelyek különbséget tudnak tenni ezek között a nagyon különböző állapotok között

2. Forgács (töredék) poligonok

- a fedvényező algoritmusok egzaktan számítják a vonalak metszését (l. 14. Fejezet)

- minden fedvényező műveletben valószínű, hogy lesznek olyan vonalak, melyeknek egybe kellene esniük, de mégsem esnek egybe pl. a digitalizálási hibák következtében

- ezeket forgácsoknak, álpoligonoknak vagy "parti hullám"-nak nevezik

34.4.ábra - Két kép fedvényezése

- ha egy n1 pontból álló ívet vagy poligont fedésbe hozunk egy n2 pontból álló ívvel vagy poligonnal, akkor maximum [2n1n2/(n1+n2)-3] forgács képződhet

- két lehetséges megközelítés:

a. törölni a fedvényezési művelet alatt, vagy

b. később törölni

A forgácsok törlése a fedvényezés alatt

- ezt a módszert használják általánosan a kereskedelmi GIS szoftverek

- ez a megközelítés a vonalakat "fuzzy"-nak tekinti

- definiálj egy tolerancia határt minden vonal számára, amely megfelel a digitalizált és valódi vonal közötti bizonytalanságnak

- e szélességű sávot hoz létre minden vonal körül

- digitalizált vonalak esetén ez a szélesség 1 mm lehet

- az e segítségével eldönthető, hogy azok a vonalak, melyeknek helyzete e -nál kisebb mértékben különbözik egymástól, azonos vonalak

- ezt a két vonalat aztán össze lehet vonni egy vonallá

Probléma

- nem nehéz nehézségre bukkanni:

- az A és B vonalak e -on belül vannak, tehát azonosak

- a B és C vonalak e -on belül vannak, tehát azonosak

- de az nem biztos, hogy A és C is e távolságon belül lesz egymástól

- azoknak a poligon fedvényezési rutinoknak, amelyek "röptében" oldják meg a forgácsok törlését, ezzel a problémával is foglalkozniuk kell

A forgácsok eltávolítása a fedvényezés után

- szükség van intelligens kritériumokra, hogy megkülönböztethesse a forgácsokat a valódi poligonoktól

- eltávolítási kritériumok többek közt:

- terület: a forgácsok kicsik

- alak: a forgácsok hosszúak és vékonyak

- ívek száma: a forgácsoknak rendszerint csak 2 határoló ívük van, a valódi poligonoknak ritkán van csak 2 ívük

- változó attribútumok: ha az A és B poligonok közötti piros ívet fedésbe hozzuk az 1 és 2 poligonok közötti kék ívvel, akkor a forgácsok A2 és B1 között fognak váltakozni

- csomópontok: a forgácsok négy elágazású csomópontban végződnek, míg a valódi poligonoknál gyakoribb a hármas elágazás

- láncolódás: a forgácsok a láncokban való előfordulás tendenciáját mutatják

- annak a megbízhatósága, hogy jól döntünk-e a forgácsokról, rohamosan nő azután, hogy elkezdjük a munkát az ív mentén

- azaz a "forgács" attribútum erősen korrelált

- ha egy forgácsot detektáltunk, a helyettesítő vonalát a tengelyébe lehet elhelyezni

 

IRODALOM

McHarg, I.L., 1969. "Design with Nature", Doubleday, New York

Goodchild, M.F., és N. S. Lam, 1980. "Areal Interpolation," Geoprocessing 1:297-312

 

ELLENŐRZŐ KÉRDÉSEK

1. McHarg jól leírta a fedvény technikát a GIS és a poligon fedvényezés adventje előtt. Vitasd meg a technika számítógépesítésének előnyeit és lehetséges hátrányait.

2. Írd le és illusztráld két poligon (A és B) 16-féle Boolean kombinációját.

3. Ismertesd és vitasd meg a területinterpolálás alternatív módszereit Goodchild és Lam, 1980 alapján.

4. Vitasd meg a raszter és vektor módszer relatív előnyeit a poligon fedvényezésben. Azonosítsd, hogy milyen alkalmazásoknál jönnek felszínre az egyes módszerek előnyei.

 
Tartalom
<<< Előző fejezet               Következő fejezet >>>
 



 
 


©GIS Figyelő