Hidrológiai Közlöny 1994 (74. évfolyam)
3. szám - Gáspár Csaba–Józsa János–Simbierowicz, Pawel: Új szemléletmód a numerikus hidraulikában. I. Egyenlőtlen hálók: generálásuk, első alkalmazások
166 HIDROLÓGIAI KÖZLÖNY 1994. 74. ÉVF. 2. SZÁM 2. ábra. Az lb. ábra QZ-cellarendszerének reprezentáns gráfja A QT algoritmus műveletigénye meglepően csekély: könnyen látható, hogy 0(N • L)-lel becsülhető, ahol L a ténylegesen előforduló legnagyobb felbontási szint. Valóban, az algoritmus idejének legnagyobb részét az teszi ki, hogy S pontjairól eldöntjük, hogy azok melyik aktuálisan keletkezett újabb rész-négyzetbe esnek: s miután minden egyes felbontási szinten legfeljebb N pontot kell vizsgálni, ez max. N • L vizsgálatot jelent. Ha most S pontjai többé-kevésbé egyentelesen vannak elosztva Q-ban vagy akár csak egy Q-beli görbe (pl. perein!) mentén, akkor L arányos log N-nel, így a műveletigény kb. 0(N • log N). A legkedvezőtlenebb eset az, amikor minden egyes pont más szintű cellába esik (ekkor L=N), ami 0(N 2)-es műveletigényt jelent. Ez az eset azonban speciális pontelrendeződést tételez fel, és a gyakorlati előfordulása meglehetősen valószínűtlen. A QT-cellarendszer egyértelműen reprezentálható egy irányított gráffal, éspedig a következő módon. Q feleljen meg a gráf kezdőpontjának (gyökérelem): a gráf pontjai reprezentálják az egyes cellákat, míg a gráf élei jelentsék a szétvágást, és mutassanak a szétvágással nyert rész-cellákra mint gráfpontokra. Ily módon fa-struktúrájú gráfot nyerünk, azaz olyat, amely nem tartalmaz zárt hurkot. A fa „levelei", azaz a gráf végpontjai lesznek a további felbontásra már nem kerülő cellák. A 2. ábrán bemutatjuk az lb. ábrán látható QT-cellarendszer reprezentáns gráfját. A fentebb leírt alapalgoritmusnak számtalan változata definiálható a felbontási kritériumok alkalmas módosításával. Lehetséges felbontási feltételek még: - valamilyen adat (fenékszint, szivárgási tényező stb.) értéke és/vagy gradiense a cellában túl nagy (meghalad egy előre adott értéket); - a cellába eső S-beli pontok túl távol esnek a cellaközépponttól, azaz a cella "excentricitása" túl nagy stb. Megjegyzések 1. A QT-algoritmus nyilvánvaló módon akárhány dimenzióban definiálható. Háromdimenziós esetben egy kocka szisztematikus 8-8 részre osztásával állunk szemben. Innen származik elnevezése is: octtree algoritmus (Cheng et al [1988]). A „tree" (fa) elnevezés a cellarendszer gráf-struktúrájára utal. Egydimenziós esetben az algoritmus egy szakasz rekurzív felbontását eredményezi (binary tree, bin-tree). Érdemes megemlíteni, hogy ekkor az N ma x:=l, L^.^N választással definiált algoritmus egyúttal egy rendezési algoritmust is ad S pontjaira. Valóban, a kezdetben rendezetlen S halmaz az 1. szintű felbontáskor olyan S^ S 2 részhalmazra bomlik, melyek külön-külön ugyan nem rendezettek, de egymáshoz képest igen, abban az értelemben, hogy minden S 2-be eső szám nagyobb bármely S rbe esőnél. A felbontást folytatva mindaddig, amíg minden cellában legfeljebb 1 pont marad, az S-beli számok nagyság szerinti rendezéséhez jutunk. 2. A quadtree (octtree) algoritmusokat a hálógenerálásnál már jóval előbb alkamazták a számítógépes grafikában, alakzatok leírására (Jackins és Tanomoto, [1980]). Az algoritmus széles körű alkalmazást nyert sajátos adatstruktúrája következtében - a legkülönfélébb információs rendszerekben is. 3. A QT-hálók mind szélső speciális esetet, tartalmazzák a hagyományos ekvidisztáns hálókat is. Legyen ui. a felbontás (az L^ szintig bezárólag) feltétel nélküli, azaz a cellákat mindig osszuk fel, S-től függetlenül (vagy S pontjai legyenek Q-ban egyenesen elosztva olyan sűrűségben, hogy az L,^ szinttel bezárólag a felbontási kritériumok mindig teljesüljenek), így egy egymást tartalmazó, egyre finomodó uniform és ekvidisztáns hálók sorozatához jutunk. Pontosan ilyenekre van szükség a hagyományos multigrid módszerek alkalmazásához (Brandt, [1984]): hasonló módon lehetséges a multigrid technika QT hálókra való kiterjesztése is. Ezzel részletesebben a sorozat következő cikkében foglalkozunk. Most bevezetünk néhány fogalmat a QT-cellarendszerekkel (hálókkal) kapcsolatban, melyek a továbbiakban alapvető szerepet fognak játszani. Egy cella szülőjének az őt tartalmazó, eggyel kisebb felbontási szinten lévő cellát nevezzük. Azt mondjuk, hogy két cella szomszédos, ha egyik sem tartalmazza a másikat, és van közös perempontjuk. Két szomszédos cella oldal-szomszédos, ha egyikük teljes oldallal illeszkedik a másikhoz; sarok-szomszédos, ha csak közös sarokpontjuk van. A szomszédság triviális az egyenletes (derékszögű és görbevonalú) hálók esetében, de a QT-hálók esetén már nem, és egy adott cellával szomszédos cellák megkeresése - mely alapvető fontosságú lesz a későbbiekben - külön feladatot jelent. Felhasználva a reprezentáns gráfot, a szomszédkeresés viszonylag egyszerű algoritmussal megoldható. Sor1 2 3 4 3. ábra. Testvér-cellák sorszámozása
