Vissza az előzőleg látogatott oldalra (nem elérhető funkció)Vissza a tananyag kezdőlapjára (P)Ugrás a tananyag előző oldalára (E)Ugrás a tananyag következő oldalára (V)Fogalom megjelenítés (nem elérhető funkció)Fogalmak listája (nem elérhető funkció)Oldal nyomtatása (nem elérhető funkció)Oldaltérkép megtekintése (D)Keresés az oldalon (nem elérhető funkció)Súgó megtekintése (S)

Open source fejlesztő eszközök, elméleti rész / Poligon topológia leírása gráfokkal

Tanulási útmutató

Összefoglalás

Ebben a részben bemutatunk egy olyan gráf struktúrát, amellyel leírható a poligon topológia. A szerkezetéből adódóan alkalmas a szomszédsági viszonyok helyes leírására és tárolására.

Poligon topológia leírása gráfokkal

A topológikus tárolás elemei — az eddigiekhez hasonlóan — poligonok, vonalak és pontok. A kérdés az, hogy hogyan tároljuk ezeket az objektumokat úgy, hogy a szomszédsági viszonyok eleve bele legyenek építve az adatszerkezetbe. A relációs modellben a helyes topológiáról magunknak kell gondoskodnunk, az magától nem teljesül (természetesen szoftveres megoldások lehetnek, amelyek arra kényszerítik a felhasználót, hogy ne vétsen topológiai hibát).

A topológikus adatszerkezetnek a következőkre kell képesnek lennie:

Mivel a geometriai objektumok típusa pont, vonallánc és poligon lehet, ezek mind külön térképi rétegek leírására használhatók. Amint láttuk, pontok esetében elegendő azok azonosítóit és helyét (koordinátáit) tárolnunk. A pontok nemcsak összetettebb geometriai objektumok elemei lehetnek, hanem önálló pontszerű entitásai egy információs rendszernek. Ilyen esetekben a pontok grafikai megjelenése tematikus tartalmat is hordozhat. A grafikus megjelenés legtöbbször valamilyen egyezményes grafikus jellel történik, amelyet valamely jelkészletből, ábrázolási konvenció gyűjteményből választunk ki (jelkulcs).

A vonalláncokat (polylineok) célszerű gráfokkal leírni, ahol a vertexek a vonalláncokat alkotó pontok, az élek pedig egy-egy node összekötöttségét reprezentálják. Ezekhez is rendelhetők a megjelenítésre vonatkozó grafikus stílusok (vastag vonal, szaggatott vonal, több párhuzamos vonalból álló egység), de ezek nem érintik a vonalláncokat alkotó node-ok elhelyezkedését.

A poligonokat egy speciális összetett gráfstruktúrával ábrázoljuk, amelyet síkgráfnak neveznek. A síkgráf háromféle elemtípusból áll: terület, él és elágazási pont. A terület reprezentálja a poligonok területeit, az élek pedig a területeket elválasztó polyline-okat, az elágazási pontok pedig a polyline-ok találkozási pontjai lesznek (hasonlóan a 31. ábrán látható táblákhoz).

Síkgráfok

A síkbeli struktúrát valójában két gráfban tároljuk. Az egyik gráf csúcsai az elágazási pontok, ezek között a pontok között élek pedig ott lesznek, ahol ezen a pontok között polyline-ok vannak. Ezekben az élekben tároljuk azt is, hogy tőle jobbra és balra milyen területek vannak. Nevezzük síkgráfnak ezt a gráfot (32. ábra).

A kép (nagyobb változata) külön ablakban is megtekinthető.32. ábra. Példa egy síkgráfra. Az ábra bal oldalán a poligonok, az ábra jobb oldalán a területek által meghatározott síkgráf látható32_dualis_graf_full.png32. ábra. Példa egy síkgráfra. Az ábra bal oldalán a poligonok, az ábra jobb oldalán a területek által meghatározott síkgráf látható
A kép (nagyobb változata) külön ablakban is megtekinthető.33. ábra. A 32. ábrán lévő síkgráf duális gráfja, és a duális gráf a befoglaló területekkel kiegészítve 33_dualis_graf_befoglalo_full.png33. ábra. A 32. ábrán lévő síkgráf duális gráfja, és a duális gráf a befoglaló területekkel kiegészítve

A másik gráf a síkgráf duálisa, amelyben a csúcsok a területek, az élek pedig azt jelentik, hogy egy területnek egy másik a szomszédja. A területhez tároljuk az őt határoló polyline-okat is, egyszóval azt a valódi poligont, amit az reprezentál. A duális gráf szerepe, hogy a síkgráffal együtt leírja a poligonok közti topológiai viszonyokat, és azok geometriáját is. Szomszédságra, elérhetőségre vonatkozó kérdésekre így már könnyen válaszolhatunk (ezzel a struktúrával azonban még nem tudunk egymásba ágyazott területeket tárolni).

Definiáljunk ezért a valós területeken kívül egy új típust, a befoglaló területeket. Ezek a valóságban külön poligonként nem megjelenő területek. Ez tulajdonképpen egy befoglaló terület, egy olyan poligonhalmaz kontúrja, amelynek minden elemét el tudjuk érni az őket leíró síkgráf duális gráfjában (33. ábra). A legkülső befoglaló terület tulajdonképp a poligon-struktúra kontúrja, vagyis legfelső szinten az egész kép, a többi szinten pedig egy teljes lyuk egy valódi poligonon belül.

Vissza a tartalomjegyzékhez

Befoglalási fa

A valós és befoglaló területeket hierarchiába rendezhetjük, és fával ábrázolhatjuk. A fa gyökerében a kép kontúrját jelölő befoglaló terület lesz, a gyerekei azok a poligonok, amelyek a duális gráfban elérhetőek belőle. Így minden valós területet hozzárendeltük az őt közvetlenül tartalmazó befoglaló területhez, másrészről az egész képet tartalmazó befogó területen kívül minden befoglaló terület egy valós terület alá tartozik (34. ábra).

A kép (nagyobb változata) külön ablakban is megtekinthető.34. ábra. A valós és a befoglaló területek kontúros jelöléssel. A valós területek betűvel, a befoglalók számmal címkézve, illetve a struktúrájához tartozó befoglalási fa34_befoglalasi_fa_full.png34. ábra. A valós és a befoglaló területek kontúros jelöléssel. A valós területek betűvel, a befoglalók számmal címkézve, illetve a struktúrájához tartozó befoglalási fa

A befoglalási fában a gyökérben az egész területstruktúra kontúrja lesz. A páros szinteken befoglaló, a páratlanokon valós területek vannak. Egy befoglaló terület gyerekei azok a valós területek, amelyek belőle a duális gráf bejárásával elérhetők. A befoglalási fát nem egy teljesen külön adatszerkezetben tároljuk, hanem a duális gráfot egészítjük ki úgy, hogy az leírja a tartalmazásokat is. Ha egy poligonon belül van egy beágyazott poligonrendszer, akkor ennek kontúrja lesz a befoglaló területe. A befoglaló területek is megjelennek a duális gráfban, mégpedig úgy, hogy egy befoglaló területnek szomszédja lesz az összes olyan poligon, amely az adott poligonrendszer szélén van. A területekhez tároljuk azt is, hogy befoglaló vagy valós területet írnak-e le.

Ha valós területet írnak le, akkor tartalmazza a határoló irányított éleket negatív körüljárási irány szerint, és a beágyazott befoglaló területek listáját. Ha az adott terület befoglaló terület, akkor tartalmazza a határoló irányított éleket pozitív körüljárási irány szerint, és a beágyazott valós területek listáját. A síkgráfban a szélen lévő éleknek eddig csak az egyik oldalán voltak területek, mostantól a másik szomszédját is beállítjuk, mégpedig a befoglaló területre. Így a síkgráf és duális gráf élei meg fognak egyezni abban az értelemben, hogy a síkgráf éleinek a duális gráf egy másik szerepét adja meg, azaz, hogy az él által reprezentált polyline két területet választ el.

Mivel az élek megegyeznek a síkgráfban és duális gráfjában, ezért azokat nem is tároljuk kétszer. A duális gráfba azzal teszünk be egy élt, hogy a bal és jobb oldalára eső területeket beállítjuk. Ez azért jó, mert könnyű a használat során egyikről másikra áttérni, valamint egy vonallánc változás egyszerre jelenik meg mindenütt, így ilyen változtatással nem képzelhetőek el topológiailag érvénytelen állapotok. Ezért mondjuk azt, hogy a duális gráf reprezentáció topológikus adatmodellt eredményez.

A síkgráf élei irányítatlanok, de egy élben a polylinet mindkét irányítás szerint tároljuk, hogy az építés során tudjunk hivatkozni mindkét irányításra. A reprezentációban a pontokhoz tároljuk a pont koordinátáját, és a kimenő irányított éleket pozitív körüljárás szerint. Az élek irányítatlan éleket írnak le, de hozzárendelünk egy tetszőleges irányítást, ami szerint leírjuk a kezdő- és végpont azonosítóját, valamint a bal és jobb oldali terület azonosítóját. Ha nincs jobb vagy bal terület, akkor a befoglaló terület azonosítóját használjuk. Ezenkívül tároljuk az élhez tartozó polylinet is.

Az eddig leírt adatszerkezet előnye, hogy támogat minden számunkra fontos műveletet, megőrzi a topológiai helyességet. A következőkben áttekintjük az előállítás módját.

Vissza a tartalomjegyzékhez

Új Széchenyi terv
A projekt az Európai Unió támogatásával, az Európai Szociális Alap társfinanszirozásával valósul meg.

A Társadalominformatika: moduláris tananyagok, interdiszciplináris tartalom- és tudásmenedzsment rendszerek fejlesztése az Európai Unió támogatásával, az Európai Szociális Alap társfinanszírozásával, az ELTE TÁMOP 4.1.2.A/1-11/1-2011-0056 projekt keretében valósult meg.
A tananyag elkészítéséhez az ELTESCORM keretrendszert használtuk.