Dr. Sárközy Ferenc: Térinformatika
Ebben a részben megismerkedünk:
- a topológiai modellel és
- a háló modellel.
A topológia egy olyan matematikai tudomány, mely bizonyos
geometriai tulajdonságokból kiindulva, azok általánosítása alapján, algebrai
törvényszerűségeket határoz meg. A geometriai topológia a téralakzatok
azon tulajdonságait vizsgálja, melyek nem változnak az idomok szakadásmentes
torzítása során. Ilyenek a szomszédság, folyamatosság, tartalmazás.
A 2.2 ábra topológiailag hasonló alakzatokat mutat be.
2.2 ábra -
topológiailag hasonló alakzatok
Míg a sphagetti modell csak vonaldarabokkal operál, a
topológiai modell a topológiai törvényszerűségek kiaknázását lehetővé tevő adat
típusokat is értelmez. Bár a topológiai modell is metrikus térben helyezkedik
el, melynek alapja a koordinátás pontok halmaza s a köztük definiált távolság
fogalom, a pontok a topológiai struktúra felépítésében játszott szerepük
alapján különböző típusokra oszthatók, ezek:
- önálló
pont;
- lánc
(ív) részét képező pont;
- csomópont.
Az önálló pont a valóság modellezése során
kapott olyan objektumok leírására szolgál, melyek területi kiterjedése
elhanyagolható. Ilyen objektumok lehetnek a kutak, források, geodéziai
alappontok, tv-, vagy rádióadó antennák, hidroglóbuszok, kémények, vezetéktartó
oszlopok stb.
A terepi objektumok egy másik csoportja vonalakkal
modellezhető, ilyenek a vízfolyások, utak, vasutak, csővezetékek, föld alatti
és föld feletti kábelek stb. A vonalas objektumok töréspontokat
tartalmaznak, melyek valamely (általában lineáris) törvényszerűségen alapuló
összekötése szolgáltatja a vonalas objektumot. Míg azonban a sphagetti
modellben a vonalat alkotó pontok egyenrangúak, addig a topológiai modell a
vonalakban kétféle ponttípust különböztet meg: a láncolatot (ívet) alkotó töréspontot
és a csomópontot.
A töréspontok valamely egymásutánja alkotja a láncot,
mely mindig két csomópont között helyezkedik el és az egyik csomópontról a
másikra mutat, azaz a lánc irányított. A csomópontok a láncok
végein helyezkednek el, ez vagy abból adódik, hogy a vonalas objektumnak a
csomópontban vége van, vagy abból, hogy a csomópontban az objektum elágazik,
vagy más vonalas objektummal metsződik. Következésképpen egy vonalas objektum
általában kettőnél több csomópontot is tartalmaz.
Az objektumok egy
jelentős száma, pld. a kataszteri rendszerek alapobjektumai, területi
kiterjedésűek és folyamatosan borítják be a felszínt. Ezeknél az objektumoknál
egy a hierarchia magasabb színtjén álló alapobjektum a poligon (zárt sokszög)
felvétele látszik célszerűnek. A poligont az azt alkotó láncok meghatározott
egymásutánja egyértelműen leírja.
Mivel folyamatos területlefedés esetén egy-egy lánc
egyidejűleg két poligonnak is része, értelmezhető a lánc leírásánál,
irányítottságának megfelelően, a jobboldali illetve baloldali poligon fogalma
is. Az irányított láncok eredményesen alkalmazhatók az u.n. szigetek
kezelésénél (2.3 ábra).
2.3 ábra -
irányított láncokból (ívekből) felépített zárt sokszögek (poligonok)
A szigetek kezelése azt jelenti, hogy a befoglaló poligon
területéből a területszámítás során a sziget területét le kell vonni.
Először azt kell
megállapítani, hogy található-e az adott poligonon belül sziget. Ez a 2.3 ábra
II poligonja esetében viszonylag egyszerűen elvégezhető mivel a szigeteként
jelentkező IV poligont csak egy lánc alkotja, melynek baloldali poligonja II,
jobboldali poligonja pedig IV. Ez azonban másképpen nem lehet csak úgy, hogy a
IV poligon sziget a II-ben. Bonyolultabb a helyzet a III poligon V és VI
poligonokból álló összetett szigete esetében. Itt a sziget meglétét úgy
dokumentálhatjuk, hogy keresünk egy olyan összefüggő, önmagában záródó
láncsorozatot, melynek baloldali poligonja a III. A dokumentálandó sziget az
ehhez a lánc együtteshez tartozó jobboldali poligonokból fog állni, azaz
példánk esetén az V és VI poligonból. Megjegyezzük, hogy az olyan
csomópontokat, melyekből nincs elágazás, ilyenek a 2.3 ábrán E és F,
álcsomópontoknak hívjuk. Míg az F álcsomópont létrehozása indokolt volt,
nélküle az egy láncból álló zárt poligon nem értelmezhető, addig az E tipusú
álcsomópont létrejöttét rendszerint digitalizálási hiba okozza, megléte
érdemben nem befolyásolja a legtöbb szoftver munkáját, legföljebb egy kicsit
növeli a futásidőt.
A topológiai modell fő előnyei a sphagetti modellel
szemben elsősorban a tárolás, lekérdezés és karbantartás területén jelentkeznek. Ennek illusztrálására nézzük meg, hogy az alábbi egyszerű poligon
rendszert hogyan tárolja egy topológiai struktúrájú micro GIS szoftver (2.4
ábra).
A vázlat elemzése előtt
megjegyezzük, hogy a szoftverek rendszerint csak a csomópontok és koordinátáik,
a töréspontok és koordinátáik bevitelét igénylik a felhasználóktól, a
táblázatok összeállitásához szükséges többi adatot automatikusan állitják elő.
Amennyiben a poligonok azonosításával kapcsolatban a felhasználónak különleges
igényei vannak, úgy természetesen azokat is be kell vinni.
I. csomópontok
|
p.sz.
|
x
|
y
|
N1
|
x1
|
y1
|
N2
|
x2
|
y2
|
N3
|
x3
|
y3
|
N4
|
x4
|
y4
|
N5
|
x5
|
y5
|
N6
|
x6
|
y6
|
|
II. láncok
|
l.
sz.
|
N1
|
N2
|
FP
|
NP
|
DC
|
C1
|
1
|
2
|
1
|
3
|
2
|
C2
|
2
|
3
|
0
|
0
|
1
|
C3
|
3
|
1
|
4
|
2
|
1
|
C4
|
2
|
4
|
6
|
2
|
2
|
C5
|
4
|
5
|
8
|
3
|
1
|
C6
|
5
|
3
|
11
|
1
|
1
|
C7
|
5
|
6
|
0
|
0
|
1
|
C8
|
6
|
1
|
0
|
0
|
2
|
C9
|
4
|
6
|
12
|
2
|
2
|
|
III. közbenső pontok
|
p.sz.
|
x
|
y
|
P1
|
x1
|
y1
|
P2
|
x2
|
y<sub2
|
P3
|
x3
|
y3
|
P4
|
x4
|
y4
|
P5
|
x5
|
y5
|
P6
|
x6
|
y6
|
P7
|
x7
|
y7
|
P8
|
x8
|
y8
|
P9
|
x9
|
y9
|
P10
|
x10
|
y10
|
P11
|
x11
|
y11
|
P12
|
x12
|
y12
|
P13
|
x13
|
y13
|
|
IV. poligonok
|
pol.sz.
|
C1
|
NC
|
Z1
|
1
|
3
|
Z2
|
4
|
4
|
Z3
|
8
|
3
|
Z4
|
11
|
4
|
|
V. pointerek
|
p.s.sz.
|
PC
|
1
|
1
|
2
|
2
|
3
|
3
|
4
|
-2
|
5
|
4
|
6
|
5
|
7
|
6
|
8
|
-5
|
9
|
9
|
10
|
-7
|
11
|
-3
|
12
|
-6
|
13
|
7
|
14
|
8
|
|
láncok
|
N1: pointer a
kezdő csomópontra
|
N2: pointer a
végső csomópontra
|
FP: pointer az
első közbenső
|
NP: közbenső
pontok száma
|
DC: rajzoló
kód
|
|
poligonok
|
C1: pointer az
első láncpointerre
|
NC: a poligont
alkotó láncok száma
|
PC: pointer a
láncra
|
-: olyan lánc
amit a rögzîtéssel ellentétes irányban kell olvasni
|
|
2.1 táblázat -
micro GIS topológiai modell tárolási struktúrája
Az ábra és a 2.1 táblázat tanulsága szerint a topológiát három
táblázat (II, IV, V) tartalmazza.
A II táblázat a láncokat definiálja olymódon, hogy
megadja melyik csomópontból indul, s melyikbe érkezik a lánc, melyik az első
közbenső pontja, s hány közbenső pontja van. Ez a megadás csak akkor kielégítő,
ha a közbenső pontok koordinátái a III táblázatban a láncok
irányítottságának megfelelő sorrendben helyezkednek el. Az utolsó oszlopban
található "rajzi kódnak" a topológiához csak akkor van köze, ha
segítségével, mint esetünkben, egyszerűen kiválaszthatók a burkoló poligont
alkotó láncok.
A poligonok felépítését a IV, V és II táblázat együttesen
szolgálja. Első ránézésre nem mindenki számára világos az V táblázat szerepe.
Egyesek úgy gondolkodnak, hogy elég volna megadni a poligont alkotó első láncot
és az alkotó láncok számát, s ezen adatok birtokában a II táblázatból a poligon
felépíthető lenne. Ebben a gondolatmenetben az a hiba, hogy egy-egy lánc két
poligonban is szerepel, s fölösleges helyfoglalás volna minden megjelenését beírni
a II táblázatba. E helyett az V táblázatban mindössze két számmal
hivatkozhatunk a kérdéses láncokra.
Végül, gyakorlásképpen
nézzük meg, hogyan lehet a táblázatok felhasználásával meghatározni például a
Z4 poligon területét.
A IV táblázatból a
program megkeresi a Z4-es sort. A poligon azonosító utáni első mezőtartalom
(11) arra utal, hogy az V táblázat 11. sorában van az a pointer (esetünkben
-3), mely a II táblázatban a Z4 poligont alkotó első láncra C3-ra mutat. Mivel
azonban a pointer előjele negatív a láncot fordított haladási értelemben kell
figyelembe venni a területszámításhoz szükséges koordináta táblázat
összeállításakor, azaz először az I táblázatból az N1 koordinátáit majd a II
táblázatból a P5 és P4 töréspontokét, végül ismét az I táblázatból az N3
csomópont koordinátáit vesszük ki. Mivel a IV táblázat negyedik sora második
mezejének tartalma 4, az eljárást még háromszor meg kell ismételni az V
táblázat 12, 13 és 14 sorszámú pointereivel. A terület számító program
készítésénél ügyelni kell arra, hogy a -3 lánc végső csomópontja (N3) azonos a
-6 lánc kezdő csomópontjával, ezért koordinátáit a táblázatba csak egyszer kell
behívni.
Amint láttuk a topológiai struktúra közvetlen lehetőséget
biztosít vonalas objektumok, felületi objektumok összeállítására, illetve az
utóbbiak esetében a szomszédos objektumok meghatározására is.
Még egy gyakran előforduló kérdésre
lehet a topológiai modell segítségével választ adni: benne van-e egy adott pont
egy poligonban (például egy ponttal jellemzett artézi kút a vizsgált
földrészleten belül vagy kívül helyezkedik-e el)?
A választ szolgáltató algoritmus, mivel topológiai
törvényszerűségeket tükröz, független a poligon alakjától.
2.5 ábra - pont a
poligonban algoritmus magyarázó ábrája
Tekintsük a 2.5 ábrát. Húzzunk az A pontból egy tetszőleges
félegyenest. Határozzuk meg a metszéspontjait az I poligonnal. Az ábra tanúsága
szerint három ilyen pont van. Ha az A-tól legtávolabbi metszésponttal kezdjük a
pontok sorszámozását úgy a félegyenes végpontjának (A) a sorszáma 4 lesz.
Végezzük el ugyanezeket a műveleteket a kívülálló B pontból is. A B pontra az
előbbiek szerint adódó sorszám 3. Kísérletünket általánosítva megállapíthatjuk,
hogy a pont akkor van a poligonban, ha a belőle húzott félegyenes poligonnal
alkotott metszéspontjainak számát párosra egészíti ki, és akkor van az idomon
kívül, ha a metszéspontok száma plusz egy - páratlan szám.
(A definícióba azért
kell bevonni magát a pontot is, mivel külső pont esetén a félegyenes gyakran
egyáltalán nem metszi az idomot, azaz 0 metszéspontja van a poligonnal. Mivel a
0 se nem páros se nem páratlan, ezekben az esetekben nem volna megoldás, ha a 0
összeghez nem adnánk hozzá magát a pontot is, azaz egyet).
A háló elmélet alkalmazásának gondolata az utóbbi néhány évben
foglalkoztatja a grafikus adatok modellezésében érdekelt szakembereket.
Maga az elmélet az 50-es évek végétől jelentkezik összefoglaló
monográfiákkal (lsd. pld. [1]). Az újabb matematikai
irodalom mint a számítástudomány megalapozásának egyik modern algebrai
területét tárgyalja a témát [2].
A háló elmélet a rendezési fogalomra épül. Maga a rendezés
bennfoglalási és azonossági relációkat fogalmaz meg valamely halmaz elemei között.
Részlegesen rendezett halmazról akkor
beszélünk, ha a bináris bennfoglalási relációval rendelkező P halmaz minden
x, y, z elemére érvényesek az alábbi kijelentések:
|
(reflexivitás)
|
(1)
|
|
(antiszimetria)
|
(2)
|
|
(tranzitivitás)
|
(3).
|
Ha létezik az x y reláció, úgy x és y
összehasonlíthatóak.
A térinformatika kérdéseire a területi beosztásokat illetően
azonban a részlegesen rendezett halmazok segitségével nem minden kérdésünkre
kapunk választ.
Képzeljük el, hogy egy területet (például egy országot)
különböző szempontok szerint zónákra osztunk (pld. megyehatárok, vízügyi
igazgatóságokhoz tartozó területek, környezetvédelmi felügyelőségek
hatáskörzetei). Tegyük fel azt a kérdést, hogy melyik az a legnagyobb terület,
melyet a régiók adott halmaza (pld. Pest megye, a Középdunavölgyi Vízügyi
Igazgatóság területe, a Győri Környezetvédelmi Felügyelőség) magában foglal.
Matematikai nyelven a legnagyobb alsó határt (infinumot)
keressük. Sajnos azonban a részlegesen rendezett halmazok nem mindig
rendelkeznek legnagyobb alsó illetve a vele duális legkisebb felső határral
(suprémummal). Előző példánk esetében a legkisebb felső határ az a
legkisebb terület, mely a kérdéses halmazelemeket tartalmazza.
A háló egy olyan
parciálisan rendezett halmaz, melyben minden elempárra létezik supremum és
infinum. Ha ez tetszés szerinti elem párra érvényes úgy teljes
hálóról beszélünk. Minden részlegesen rendezett halmaz beágyazható egy
teljes hálóba: ez a normál kiegészítő háló.
A részlegesen rendezett halmazok és hálóvá történő
kiegészítésük kis elemszám esetén jól ábrázolható az un. HASSE-féle
diagrammok segítségével. A 2.6 ábra egy bonyolultabb, a 2.7 ábra egy
egyszerűbb területfelosztás HASSE-diagrammját ábrázolja. Ez utóbbi esetben az
infinum üres halmazként adódik, mivel B-nek és C-nek nincs közös területe.
A háló modellben tárolt földrajzi információ lehetővé teszi a
bennfoglalási (tartalmazási) kérdések egyszerűbb megválaszolását és a modell új
eszközökkel (halmazműveletek) támogatja a fedvénymetszési (overlay) eljárások
végrehajtását. A módszer a fejezet írásakor (96. 11.) még csak az elméleti
megalapozás állapotában volt. Európában a modellel kapcsolatos kutatások W.
KAINZ bécsi kartográfia professzor (jelenlegi munkahelye az ITC Entschede,
Hollandia) nevéhez fűződnek (lsd. pld [3]).
|
|
2.6 ábra - egy terület háromféle felosztása, közös rész
megtalálása
|
2.7 ábra - egy terület
kétféle felosztása, melyeknek nincs közös része
|
Megjegyzéseit
E-mail-en várja a szerző: Dr Sárközy Ferenc