Skip Navigation Links Tolo-Logix

Topo-Logix

Egy redundanciamentes topologikus adatszerkezet

Szerző: Elek István

Bevezetés

A topológia jól ismert fogalom a térinformatikával foglalkozók körében. Az OGC szabvány (open Geospatial Consortium) alaposan és részletesen tárgyalja a topologikus minőségű adatok létrehozásának elméleti hátterét, adatbázis technológiai megvalósíthatóságát. Minden piacvezető szoftver követi az OGC előírásait, tartalmaz funkciókat a topológia kezelésére, létrehozására, javítására [1, Arctur-Zeiler]. A térbeli lekérdezések miatt a topologikus adatok megléte alapvető adatminőségi követelmény [14, Samet]. A térképi adatok létrehozásakor, importjakor kell felépüljön a megfelelő topológia, amely eléggé gyakran nem teremthető meg automatikusan. Raszteres adatok feletti félautomatikus (kézi) vektorizáláskor a topológia biztosítása alapvetően a vektorizálást végző személy szakértelmétől függ. Tovább az export/import műveletekből származó adatok topológiája erősen függ az eredeti adatforrás minőségétől. Amennyiben az adatforrás strukturálatlanul tartalmazza a vektoros adatokat (spagetti modell), akkor az import során keletkezett adatok sem lesznek topologikus minőségűek. Az importált adatok topológiájának létrehozása külön beavatkozást igényel, amelyhez a piacvezető GIS szoftverek funkcionalitása számos eszközt biztosít [15, Tomlinson]. Nemcsak a drága kereskedelmi szoftverek, hanem az ingyenesen hozzáférhető nyílt forráskódú rendszerek is.
Ebben a cikkben olyan adatstruktúrákat fogunk bemutatni, amelyek szerkezetükből adódóan megőrzik a topológiát, és a geometriai elemeket (pontokat) nem redundáns módon tárolják. Ezt úgy érik el, hogy a poligonokat, vonalláncokat alkotó pontokat tárolják, és az egyes komplexebb objektumok (poligonok) csak hivatkoznak az őket alkotó pontokra. Ennélfogva a szomszédos poligonok azonos csúcspontjai csak egyszer lesznek tárolva, ezáltal megszűnik a redundáns tárolás, és a szomszédos poligonok között véletlen hézagok, átfedések létrejöttének az esélye. Amint látni fogjuk ez logika kiterjeszthető a nem egy rétegen, egy feature classban tárolt adatokra is. Így akár különböző rétegek csúcspontjait, amelyek azonos nyomvonalon futnak, sem kell redundánsan tárolni. Ezáltal a klasszikus réteg vagy feature class fogalom is lazulni fog. Fontos kiemelni, hogy az OGC [12, OGC szabvány] nem biztosítja az előbb említett tulajdonságokat. Geometriai értelemben korrekt módon definiálja a topologikus minőségi kritériumokat, de nem ad iránymutatást, kikötést a redundáns tárolást illetően, továbbá nem definiál topológia megőrző adatstruktúrákat sem.

Topológia leírás relációs adatbázis-kezelőkkel

A relációs modellel szemben a következő elvárásokat támasztjuk poligonok leírása esetében:
  • tárolja a geometriai elemek topológiai viszonyait
  • ne engedjen meg hibás eseteket (hézag- és átfedésmentesség)
  • a poligonok ne metsszék egymást
  • olyan eseteket is tároljon, amikor egy poligonban egy másik poligon benne van (pl. sziget egy tóban, úszó telkek a lakótelepeken, stb.).
  • tárolja a geometriai entitások attribútumait
  • a tárolt topológiával kapcsolatos kérdésekre könnyen válaszoljon: egy pont hol van, egy vonallánc (polyline) mit metsz, egy poligon mivel szomszédos, milyen másik poligonokat tartalmaz, stb.

Pont-kontúr-poligon struktúra

A fenti kritériumokat relációs adattáblák kapcsolatrendszerével fogjuk leírni, amely mintegy automatikus biztosítja a poligon topológia megőrzését. Lássunk erre egy példát. Vizsgáljuk meg 1. ábrát. Építsük fel a Pg1, Pg2 és Pg3 poligonokat az őket alkotó kontúrokból (vonalláncokból), vagyis a Pg1{C1, C3, … Ci} kontúrokból, a Pg2{C1, C2, … Cj} kontúrokból, és végül a Pg3{C2, C3, … Ck} kontúrokból. A C1{p1, p2, p3, p4, p5, p6} pontokból, a C2{p6, p7, p8, p9, p10} pontokból, a C3{p6, p11, p12, p13, p14} pontokból áll.


1. ábra. Poligonokat felépítő kontúrok rendszere. Ha csak a pontokat tároljuk a koordinátáikkal, és a kontúrok csak hivatkoznak az őket felépítő pontokra, valamint a poligonok csak hivatkoznak az őket felépítő kontúrokra, akkor egyetlen pontot sem tárolunk redundánsan. További, a topológia megőrzését segítő tulajdonság, hogy egy pont elmozdítása az összes tőle függő objektumra ugyanazt a hatást fogja gyakorolni, vagyis megőrződik a topológia [12, Rigaux, 2002]



Hozzunk létre négy relációs táblát (2. ábra). Az elemi geometriát, vagyis a pontok azonosítóit, és x,y koordinátáit a Points tábla tartalmazza. A Points.id-point a Points táblában elsődleges kulcs. A Contours tábla (a poligonokat alkotó elágazásmentes határvonalak) ezekre a pontokra hivatkozva épül fel, mivel a Points.id-point mezője, mint idegen kulcs, hivatkozik a Points tábla megfelelő rekordjára. Ezen kívül még tartalmaz egy point-order nevű mezőt, amely a pontok összekötési sorrendjét határozza meg.


2. ábra A Polygons tábla a Contours rekordjaiból épül fel. A Polygons tábla tartalmaz egy id-boundary nevű mezőt, amely elsődleges kulcs ebben a táblában, valamint egy id-contour nevű mezőt, amely, mint idegen kulcs, a Contours tábla megfelelő rekordjára mutat. A Polygons tábla annyi vonalláncból áll, ahány határvonala van a poligonnak. [12, Rigaux, 2002]. (Mivel az ábra egy működő rendszerből származik, amely angol nyelvű, ezért angol nyelvűek a tábla nevek is.)



Végül a Settlements tábla (települések), amely a poligonok neveit (vagy bármely azonosítóját) tartalmazza, a Polygons tábla azonosítóira hivatkozik (id-boundary), mint geometriai összetevőre, a többi adata viszont leíró tartalmú (name, type, status). Vegyük észre, hogy ebben az esetben egy csúcspont megváltoztatása a Points táblában (pl. eltolása vagy törlése) nem rontja el a topológiát, ha eredetileg létezett, nem változtatja meg a szomszédsági viszonyokat. Egy ilyen nagy hatékonyságú struktúra már képes biztosítani topologikus tulajdonságok megőrzését. (Törlés esetén triggerek alkalmazásával a törölt pontra való hivatkozásokat is törölni kell a Contours táblából, de ez egy adatbázis-technológiai részletkérdés, amellyel terjedelmi korlátok okán részletesebben nem foglalkozunk).
Példaképpen adjunk meg egy hagyományos SQL parancsot, amely a Settlements táblából kiválasztja a type mező alapján a Balaton part menti településeit. Hangsúlyozni szeretnénk, hogy a lekérdezés eredménye a táblák kapcsolat rendszerének köszönhetően térbelileg is értelmezhető, sőt a legyűjtött adatok, egy megfelelő rajzoló rutin segítségével, kirajzolhatók. Ez a Sql parancs, komplexitása miatt, nyilvánvalóan még nem való egy végfelhasználónak, de az már látható, hogy ilyen parancsokból felépíthető egy olyan függvénykönyvtár, amely szintaktikailag térbeli lekérdezésként fogalmazható meg. Az SQL parancs tehát a következő, amelynek eredményét a 3. ábra mutatja:

SELECT polygons.id-contour
FROM settlements, polygons, contours, points
WHERE type=`Parti`
AND settlements.id-boundary=polygons.id-boundary
AND polygons.id-contour=contours.id-contour
AND contours.id-point=points.id-point
ORDER BY polygons.id-contour, point-num
GROUP BY name


3. ábra
A parti települések lekérdezésének eredménye a sötétszürkével kitöltött poligonok halmaza [4, Elek]



Vizsgáljuk meg gyakorlati szempontból az 1. ábrán látható poligonstruktúrát. Sem a layer, sem a fature class logikájú rendszerekben nem lehetséges, hogy egy poligonnak eltérő színű határoló vonalai legyenek, vagyis vizualizációs attribútumokat csak az egész poligonra vonatkozóan adhatunk meg. Márpedig a gyakorlatban ilyen igény felmerülhet. Különösen geológiai térképeken láthatunk ilyen poligonokat (4. ábra). Ennek a földtani térképezésre jellemző okai vannak, a részletek jelen pillanatban nem érdekesek. Az azonban érdekes, hogy ilyen probléma megoldását a térinformatikai rendszerek gyakorlati művelői úgy oldják meg, hogy létrehoznak egy új réteget, amelyre az előbbi poligon réteg vonalláncokra szétvágott rendszere kerül rá, ekkor pedig már lehetségessé válik az eltérő színezés ezen az új rétegen.




4. ábra
Földtani térkép részlet, ahol egy poligont különböző típusú vonalak határolnak (a sötét poligon bal oldali határa szaggatott, jobb oldali határa tömör vonal). A hagyományos layer/feature class logikájú rendszerekben egy objektumnak csak egyféle határoló vonala lehetséges



A fenti példában a poligonok szétvágása, és így a réteg megduplázása okaként az eltérő színezést említettük, de számos más okból is felbukkanhat effajta szétvágási igény. A gyakorlatban nem ritkán előfordul, hogy nemcsak a poligon egészéhez, hanem az őt alkotó, alacsonyabb hierarchiájú geometriai elemekhez is (határoló vonalak, sarok pontok, stb.) szükséges lehet attribútum adatok hozzárendelése (pl. egy épület sarka a telekhatáron leíró adata ennek a pontnak, miközben az épület poligon alkotó elemeként is szerepet játszik, de ilyen minőségben a ponthoz nem, csak a poligon egészéhez rendelhető adat).
Az adatbázis konzisztencia szempontjából ez a megoldás nemcsak, hogy nem elegáns, de kifejezetten kockázatos. A poligonok szétvágásával létrejövő vonallánc halmaz elszakadt az eredeti poligon halmaztól, és ha abban valamilyen változás áll be, akkor annak a vonallánc halmazra történő átvezetéséről gondoskodni kell. Arról már nem is beszélve, hogy ezzel a ,,megoldással'' többszörös redundanciát viszünk az adatbázisba, amely már önmagában kockázati tényező.
Vegyük észre, hogy az 1. ábrán látható struktúrában azonban lehetséges eltérő színeket megadni a kontúroknak minden nagyobb erőfeszítés nélkül. Ráadásul szükségtelen redundáns rétegeket létrehozni, poligonokat vonalláncokká szétszedni, a különböző rétegek összhangjáról gondoskodni.
A következőkben be fogunk mutatni egy olyan adatszerkezetet, amely a poligonok és a pontok közvetlen kapcsolatát írja le kontúrok beiktatása nélkül. Ez a logika kiterjeszthető pontok és vonalláncokkal leírható rétegek rendszerére is. Ezt is fel fogjuk vázolni.

Pont-poligon struktúra

A fentebb bemutatott szerkezetnél egyszerűbb struktúrát mutatunk be ebben a fejezetben [5, Elek]. Az 5. ábrán látható poligonokra az OGC szabvány szerint minden poligonhoz tárolni kell a saját pontjait: A{1,2,3,4}, B{3,4,5,6}, C{3,6,7,8,9}, D{2,3,9,10,11}, ami egyértelműen redundáns tárolást eredményez. A bemutatandó, redundancia mentes adatszerkezetben koordinátákat csak a pontokhoz rendelünk. A poligonok hivatkozni fognak ezekre a pontokra, így redundáns tárolás ebben az esetben sem áll fenn. A következőkben bemutatjuk a relációs táblák rendszerét, amely a fenti célokat megvalósítja.




5. ábra
Az A,B,C,D poligonok, és az őket alkotó {1,2,3,4,5,6,7,8,9,10,11} jelű pontok láthatók




6. ábra
Az 5. ábrán látható A,B,C,D poligonok reprezentációja a Points, Polygons, Pgs táblákkal



Mielőtt megnéznénk a táblák kapcsolatrendszerét, vessünk egy pillantást az 5. ábrára. Hozzunk létre három adattáblát (6. ábra). A Points tábla tartalmazza a pontok egyedi azonosítóit (Points.Ptid) és koordinátákat (Points.Xcoord, Points.Ycoord).

CREATE TABLE Points
(Ptid INT NOT NULL IDENTITY,
Xcoord FLOAT NULL, Ycoord FLOAT NULL,
PRIMARY KEY (Ptid))

 A Polygons táblában poligononként annyi rekord van, ahány pontból áll az adott poligon. Egy idegen kulcsa van (Points.Ptid), amely azokra a rekordokra mutat (Points.Ptid) a Points táblában, amelyek alkotják a poligonokat.

CREATE TABLE Polygons
(idPolygons INT NOT NULL IDENTITY, idPoint INTEGER NOT NULL,
name VARCHAR(50), pointOrder INTEGER NULL,
PRIMARY KEY (idPolygons) FOREIGN KEY (idPoint)

Végül hozzuk létre a Pgs táblát, amely annyi rekordból áll, ahány poligon van. Az idegen kulcsa azokra a Polygons nevű táblában lévő azonosítókra mutat, amelyek a poligont alkotják. A Pgs tábla reprezentálja az egyes poligonokat, mint geometriai egységeket. Ehhez a táblához lehet az egyes poligonokra vonatkozó attribútum adatokat kötni (település név, vagy helyrajzi szám).

CREATE TABLE Pgs
(idPg INT NOT NULL IDENTITY, name varchar(50),
PRIMARY KEY (idPg), FOREIGN KEY(idPolygons))

Ez az adatstruktúra nemcsak a redundancia mentességet biztosítja, hanem egy további, nagy lényeges információ tárolását is szükségtelenné teszi. A poligonok topológiáját az OGC alapján megvalósító rendszerek azt is tárolják, hogy egy poligonnak mely más poligonok a szomszédai. (Az ORACLE ezt úgy oldja meg, hogy a kontúrok tárolásakor rögzíti, hogy a vonallánc melyik oldalán mely poligon van). A bemutatott adatmodellben erre nincs szükség, ugyanis egy egyszerű Sql paranccsal megállapítható, hogy egy adott pontra mely poligonok mutatnak rá. Márpedig, ha egy pont több poligonnak is alkotó elem, akkor egyben annak szomszédja is kell legyen.

Spagetti konverziója topologikus struktúrába

Mivel szinte minden létező adatunk valamilyen spagetti topológiájú struktúrában áll rendelkezésünkre, ezért ezek átalakítása az előző részben vázolt topologikus struktúrába, alapvető feladat. Amint az OGC ajánlásban olvasható [12, OGC szabvány], a poligonok kezdő és végpontjait is tárolják a spagetti szerkezetek, miközben ezek ugyanazok a pontok. Az első lépés ezen pontok kiszűrése. A következő lépés a szomszédos poligonok közös pontjainak kiszűrése, és a pontok tárolása a Points táblában, majd a A Polygons és a Pgs táblák létrehozása és feltöltése. Ezek végrehajtása SQL [3, Celko] parancsokat végrehajtó alkalmazások kifejlesztésével érhető el. Ezen alkalmazások elkészültek az ELTE Informatikai Karán, a Térképtudományi és Geoinformatikai Tanszéken. A programok Windows Serveren futnak, az alkalmazások VisualStudio.net-ben készültek.
Terjedelmi korlátok okán a konverziót a cikkben nem tudjuk részletesen leírni, de akit a problémakör mélyebben érdekel, az teljes részletességgel megismerheti a folyamatot a következő könyvből: Elek István: Topologikus térbeli adatstruktúrák. A könyv teljes egészében letölthető a http://mapw.elte.hu/elek/pdf/topo.pdf címről.

A vonaltopológia egy relációs modellje

A fentiekhez hasonlóan, amikor poligonokat írtunk le relációs táblák kapcsolat rendszerével, vonalas geometria elemek is reprezentálhatók redundancia mentesen [5, Elek]. A spagetti modellben a keresztező vonalak közös pontjaik mindkét objektumban tárolódnak, így redundancia keletkezik (7. ábra).




7. ábra
Kereszteződő vonalak. A C jelű görbe 4. pontja, és a B jelű görbe 2. pontja közös. Ugyancsak közös a B jelű görbe 4. pontja, és az A jelű görbe 4. pontja. A jobb elkülöníthetőség kedvéért az egyes görbék pontjait görbénként más szimbólummal jelöltük




8. ábra
Kereszteződő vonalak közös pontjait nem tároljuk kétszer. Azonosítóik alapján állapítható meg, hogy egy pont egy vagy több vonal létrehozásában játszik-e szerepet



A 8. ábrán láthatók a vonalakat alkotó pontok, melyek közül néhány több vonalhoz is tartozik (a 4. és 9. jelű pontok). Ha a pontokat, koordinátáikkal együtt egy csak pontokat tartalmazó táblában, a vonalakat reprezentáló hivatkozásokat pedig egy másik táblában tároljuk, akkor ez a redundancia megszüntethető.




9. ábra
Vonalak redundancia mentes tárolását biztosító adatszerkezet



A Points, Lines és Plines táblák létrehozása

Hozzunk létre egy csak pontokat tartalmazó táblát (Points), amely a pontok azonosítóit, és koordinátáit tartalmazza. Hozzunk létre továbbá egy Lines és egy Plines nevű táblát. A Lines tartalmazza a vonalat alkotó pontok hivatkozásait, mégpedig szám szerint annyit, ahány pontból áll az adott vonal. A Plines nevű tábla a vonal objektumot tartalmazza a leíró adataival, és a Lines táblára való hivatkozással (9. ábra). Ez az adatszerkezet nem tartalmaz redundáns pontokat, így egy-egy megváltoztatása (mozgatása vagy törlése) nem okoz szakadást az eredetileg szakadás mentes vonal topológiában. Azt azért látni kell, hogy ha egy közös pontot törlünk a Points táblából, akkor a kereszteződő vonalak többé nem kereszteződnek (egymás felett haladnak el).
Vegyük észre, hogy ez az adatszerkezet a redundancia mentes tároláson kívül további előnyöket is tartogat. Útvonal optimalizáló algoritmusok számára nagy segítség lehet ez az adatszerkezet. Az útvonal optimalizáló algoritmusok (pl. Dijkstra, Warshall) esetében adottnak vesszük az érintendő pontok meglétét, miközben egy valóságos térinformatikai rendszerben (amely spagetti topológiájú network modellt használ), egyáltalán nem nyilvánvaló, hogy egy adott pontból indul e többfelé is él. Ennek megkereséséről külön gondoskodni kell valamely térbeli kereső funkció segítségével. A relációs táblákban tárolt vonalhálózatok esetében fel sem merül, hogy van-e elágazási lehetőség az adott pontban, hiszen nincs szükség esetlegesen eltérő rétegekben, feature classokban tárolt vonalak közös részeinek megkeresésére (pl. a fűutak és mellékutak más-más rétegen vannak)

Összegzés

Az OGC szabvány alapján lehetséges ugyan korrekt topológiájú adatrendszerek létrehozása, de a szabvány nem garantálja a topológia megőrzését és a redundancia mentes tárolást. A előző részben arra mutattunk egy megoldást, hogy lehetséges poligon topológiát megőrző adatstruktúra létrehozása, valamint arra is, hogy hálózati modellt követő, vonalláncok esetében is lehetséges a kapcsolatrendszert is magában foglaló redundancia mentes adatszerkezet létrehozása. Sajnálatos módon ez a struktúra nem követi az OGC szabványt, mivel a redundancia mentes tárolásból következően ellentmond az OGC szabvány előírásainak. Amennyiben a sebesség tesztek megfelelőnek bizonyulnak az OGC alapú létező megoldásokkal összehasonlítva, akkor el lehet gondolkozni a szabvány továbbfejlesztésén.

Gyakorlati alkalmazás

A cikkben ismertetett kutatás-fejlesztés az ELTE Informatikai Karán, a Térképtudományi és Geoinformatikai Tanszéken készült. A munka eredményeként elkészült egy kísérleti szoftver, amely Mapinfo MIF, ESRI shape formátumból az ismertetett redundancia mentes, topológia megőrző struktúrába konvertálja az adatokat. A hatékonysági tesztek folyamatosan készülnek, egyre nagyobb adatmennyiségek átalakítása történt meg (pl. Magyarország megyéi, járásai, külterület határai, stb.). Több tízezer poligont tartalmazó poligonállományokra is működőképesnek bizonyult a modell. Noha a konverziós folyamat lassú, a végeredmény már a gyakorlatban is megfelelő működési sebességgel használható.
A redundanciamentes topologikus minőségű tárolás állami feladatok ellátása esetén is hasznos lehet. A cikkben ismertetett eljárás bármely adatbázis kezelő rendszerrel megvalósítható, a MS Sql Serverrel éppen úgy, mint a Postgres/Postgis-szel, vagy akár egy mdb fájlban is létrehozhatók ilyen struktúrák.

Irodalomjegyzék

1. D. Arctur -- M. Zeiler: ,,Designing Geodatabases'', ESRI, 2004
2. R. Burke: ,,Getting to know ArcObjects'', ESRI Press, 2003
3. J. Celko: ,,SQL felsőfokon'', Kiskapu kiadó, 2002, ISBN 963 9301 20 5
4. Elek István: ,,Térképek, adatbázisok, információs rendszerek'', ELTE Eötvös kiadó, 2011, ISBN 978 963 312 039 2
5. Elek István: Topológikus térbeli adatstruktúrák, 2014 (http://mapw.elte.hu/elek/pdf/topo.pdf )
6. ESRI Shapefile Technical Description -- ESRI White Paper, July
7. Hajnal P.: ,,Gráfelmélet'', Poligon kiadó, 2003
8. J. Han -- M. Kamber: ,,Adatbányászat'', Panem Könyvkiadó, 2004, ISBN 963 545 394 9
9. Laurini -- Thomson: ,,Fundamentals of Spatial Information Systems'', Academic Press, 1992
10. A. Mitchell: ,,The ESRI Guide to GIS Analysis'', ESRI, 1999
11. MacEachren -- Taylor: ,,Visualization in Modern Cartography'', Elsevier, 2005
12. OGC szabvány leírása: http://www.opengeospatial.org
13. P. Rigaux -- M. Scholl -- A. Voisard: ,,Spatial Databases with Application to GIS'', Morgan Kaufmann Publishers, 2002
14. Hanan Samet: ,,The Design and Analysis of Spatial Data Structures'', Addison-Wesley, 1994, ISBN 0-201-50255-0
15. R. Tomlinson: ,,Thinking About GIS'', ESRI Press, 2007