Gyors térinformatikai algoritmusok mobiltelefon lefedettség vizsgálatához

Eötvös Loránd Tudományegyetem Informatikai Kar Algoritmusok és Alkalmazásaik Tanszék

Gyors térinformatikai algoritmusok mobiltelefon lefedettség vizsgálatához

Dr. Hajder Levente Megbízott óraadó, ELTE Tudományos főmunkatárs, Sztaki

Tóth Sándor Programtervező informatikus BSc

Budapest, 2015

Tartalomjegyzék 1 Bevezetés ........................................................................................................................................ 3 1.1 A szakdolgozat motivációja, a megoldandó feladat ................................................................ 3 1.2 A megoldandó feladat során felmerülő probléma ................................................................... 5 2 Pont a poligonban vizsgálat matematikai háttere ........................................................................... 7 2.1 Az illeszkedés vizsgálat geometriai elemzése ........................................................................ 7 2.1.1 Síkidomra illeszkedés vizsgálata általános esetben ........................................................ 7 2.1.2 Síkidomra illeszkedés vizsgálatának speciális esetei ...................................................... 8 2.1.3 Bemenő (poligon) adatokra vonatkozó megkötések ....................................................... 9 2.1.4 Poligon oldalára vagy csúcsára illeszkedő pont vizsgálata ........................................... 10 2.1.5 Poligonra illeszkedés vizsgálata általános esetben ........................................................ 11 2.1.6 Kivételek, speciális esetek melyek lekezelendőek ........................................................ 12 2.1.6.1 Poligon csúcsára illeszkedő félegyenes ................................................................. 12 2.1.6.2 Poligon oldalára illeszkedő félegyenes vizsgálata ................................................ 13 2.1.6.3 Oldal végpontjára illeszkedő félegyenes vizsgálata .............................................. 14 2.1.6.4 Poligon oldalára illeszkedő pont vizsgálata .......................................................... 17 2.1.6.5 Poligon csúcsára illeszkedő pont vizsgálata .......................................................... 17 2.1.6.6 Összetett poligonok vizsgálata .............................................................................. 18 2.2 Az illeszkedés vizsgálat vektoralgebrai megvalósítása ........................................................ 20 2.2.1 Pont illeszkedése téglalap területére ............................................................................. 20 2.2.2 Pont illeszkedése egyenesre .......................................................................................... 20 2.2.3 Pont illeszkedése szakaszra ........................................................................................... 21 2.2.4 Félegyenes és szakasz metszéspontja ............................................................................ 21 3 Felhasználói dokumentáció .......................................................................................................... 22 3.1 A demo alkalmazás célja ....................................................................................................... 22 3.2 Az alkalmazás futtatása ......................................................................................................... 22 3.3 A grafikus felület elemei ....................................................................................................... 23 3.3.1 Mif fájl szerkezete ......................................................................................................... 24 3.3.2 Mif fájl megnyitása ....................................................................................................... 26 3.3.3 Navigáció a térképen ..................................................................................................... 27 3.3.4 Alkalmazott módszer kiválasztása ................................................................................ 28 3.3.5 Illeszkedésvizsgálat indítása ......................................................................................... 28 3.3.6 Illeszkedésvizsgálat eredménye .................................................................................... 29 4 Fejlesztői dokumentáció ............................................................................................................... 31 4.1 A fejlesztőkörnyezet .............................................................................................................. 31 4.2 Az alkalmazás architekturális tagozása ................................................................................. 31 4.2.1 Kommunikáció a szálak között ..................................................................................... 31 4.2.2 Rétegfüggetlen osztály .................................................................................................. 32 4.2.3 Perzisztencia réteg ......................................................................................................... 32 4.2.4 Üzleti logikai réteg ........................................................................................................ 33 4.2.5 Megjelenítési réteg ........................................................................................................ 35 4.3 Pont a poligonban vizsgálat megvalósításai, az optimalizálás lépései ................................. 36 4.3.1 A szakdolgozat statisztikájának készítéséhez használt mintaadat ................................. 36 4.3.2 „Brute force” módszer ................................................................................................... 38 4.3.3 „Keep model” módszer ................................................................................................. 39 4.3.4 „MBR check” módszer ................................................................................................. 41 4.3.5 „Qt contain” módszer .................................................................................................... 43 4.3.6 Geometry bin hash módszer .......................................................................................... 43 4.3.6.1 Hashelés általános bemutatása .............................................................................. 43 4.3.6.2 Geometriai hashelés .............................................................................................. 46 4.3.6.3 A módszert megvalósító algoritmus ...................................................................... 52

4.3.6.4 Futási idő, műveletigény statisztika a módszerre a mintaadatokkal ..................... 53 4.3.6.5 A módszer alkalmazása a meglévő vállalati rendszerbe integrált „dobozos” szoftverben ......................................................................................................................... 53 4.3.7 Gyorsított geometry bin hash módszer ......................................................................... 54 4.3.8 Geometry band hash módszer ....................................................................................... 55 4.4 A módszerek összehasonlítása .............................................................................................. 56 5 Tesztelési terv ............................................................................................................................... 58 5.1 Felhasználói felület funkcionális tesztelése .......................................................................... 58 5.2 Illeszkedésvizsgálat módszerek tesztelése ............................................................................ 59 5.2.1 Az illeszkedésvizsgálat blackbox teszt esetei ............................................................... 59 5.2.2 Az illeszkedésvizsgálat whitebox teszt esetei. .............................................................. 60 6 Melléklet: forráskódok ................................................................................................................. 62 7 Irodalomjegyzék ........................................................................................................................... 68

1 Bevezetés A bevezetésben röviden ismertetem a szakdolgozatom témaválasztásának okát, hátterét, a gyakorlati életben tapasztalt azon nehézséget, amelyre megoldást kerestem.

1.1 A szakdolgozat motivációja, a megoldandó feladat Magyarországi mobiltelefon szolgáltatónál rádiós mérőrendszer fejlesztőként végzett munkám során másfél évtizede használok térinformatikai alkalmazásokat. A munkám során sok esetben használok rádiós mérőatóval végzett, földrajzi helyhez (a mérőautó útvonalán 10-20 méterenkénti pontokhoz) kapcsolódó mérésadatokat, valamint rádiós jelterjedési modellek segítségével valószínűsített mobilhálózat lefedettségi, ellátási területet poligonokkal leíró adatokat. Egy mobilszolgáltató, vagy a hozzá forduló ügyfél, szabályozó hatóság számára ezen rádiós mérések, modellek alapján megválaszolható kérdések lehetnek például: - pontszerűen megadott földrajzi címen milyen (technológiai, szolgáltatásminőségi paraméterekkel jellemezhető) lefedettség van, illetve várható, - mely területeken van közelmúltbeli mobil hálózatfejlesztésnek (lefedettségben, sávszélességben) pozitív hatása, - egy műszaki hiba (pld. bázisállomás leállása) mely területeken, milyen jellegű szolgáltatáskiesést, degradációt eredményezhet, - pontszerűen vagy poligonnal megadott földrajzi címen mely bázisállomás(ok) a kiszolgálók, melyeken keresztül biztosan tud, valószínűleg tud, vagy biztosan nem tud kapcsolódni a hálózathoz a mobil készülék (megadott technológia, szolgáltatásminőségi paraméterekkel). Mind a fenti kérdések megválaszolása a bevezető elején említett mérésadatok, rádiós modellek alapján, mind pedig maguknak a modelleknek a szimulálása, a mérésadatok feldolgozása jelentős részben térbeli vagy síkbeli objektumoknak átfedés illetve illeszkedés vizsgálatára vezethető vissza. Jelen szakdolgozatban az illeszkedésvizsgálatoknak csak egy, de a fentiek során nagyon gyakra használt: „pont a poligonban” vizsgálatának módszereire térek ki, azaz 3

annak eldöntésére, hogy megadott pont megadott poligon határvonalán belül, vagy kívül helyezkedik -e el. Példa: nézzük az alábbi térképet:

1. Ábra: 439.25 MHz -es rádiófrekvenciás jel terjedési terepmodell alkalmazásával kapott jelszint (térerő) térkép [1]

Lehetséges kérdés például: a 1. ábrán látható állomás modellezett jelszintje alapján, három

lehetséges

küszöbszintet

(dB

-ben)

megadva

mely

településeken

valószínűsíthető: - beltéri (épületen belüli) vételi lehetőség (geometriailag megfogalmazva: mely pontok esnek a piros és sárga területre), - kültéri (épületen kívüli) vételi lehetőség (mely pontok esnek a zöld területre), - magas pontra elhelyezett, irányított, nagy nyereséges Yagi antennával (lásd 2. ábra) való vételi lehetőség (mely pontok esnek a világoskék területre).

4

2. Ábra: Yagi antenna [2]

Az 1. ábrán az egyes küszöbszintekhez (sárga, zöld, kék) tartozó területek határvonalát poligonként megadva 3 lefedettségi poligont kapunk. Vizsgáljuk, hogy az egyes városok, helyszínek a poligonon belül, vagy kívül esnek.

1.2 A megoldandó feladat során felmerülő probléma Több térinformatikai, kész, „dobozos” alkalmazás használata során tapasztalom, hogy ezek

„pont a poligonban”

lekérdezéseinek

performanciájában jelentős

különbségeket mutatnak. A 2000-es évek óta a mobil technológiák, bázisállomások számának jelentős növekedése, valamint a szolgáltatások igénybevételi feltételeinek sokszínűsége (különböző felhasználási célnak, eszköznek különböző sávszélesség, jel erősség, jel/zaj viszony arány küszöbszintjei lehetnek) nagy mértékű bonyolultság növekedést eredményezett. Az egyes mobil technológiákra vonatkozón mind a mérési pontok darabszáma mind az országos lefedettségi térképeket definiáló poligonok töréspontszáma milliós nagyságrendű. Több szoftvergyártó kereskedelmi térinformatikai szoftverével dolgoztam, ezek között található olyan régebbi, már nem supportált, nem frissített termék is, amely kifejezetten rossz performanciát mutat a pont a poligonban lekérdezések területén (1 pont lekérdezésének perces nagyságrendű időtartama van). Ezen elavult, központi 5

termék köré nagyon összetett, bonyolult egyedi fejlesztésű rendszer épült, melynek performanciája komoly problémát jelent, melyre a hosszú távú megoldás a központi kereskedelmi termék lecserélése korszerűbb szoftverre. Ezen megoldás azonban a teljes köré épülő rendszert alapjaiban érintő, várhatóan hosszabb munkafolyamat lesz, ezért gyors megoldásként vizsgáltam, hogy mi lehet a jelenlegi rendszer szűk keresztmetszete, illetve lehetséges-e a meglévő keretek között felgyorsítani a lekérdezéseket. A vizsgálat eredménye pozitív lett, a geometriai adatok megfelelő módosításával nagyságrenddel gyorsabbá sikerült tenni a meglevő alkalmazást is, melynek módjára a szakdolgozat 4.3.6.5 A módszer alkalmazása a meglévő vállalati rendszerbe integrált „dobozos” szoftverben fejezetben részletesen kitérek. Mindemellett el kezdett érdekelni annak vizsgálata, hogy hogyan lehetséges az, hogy nagyságrendi eltérések mutatkoznak az egyes termékek között, vajon milyen algoritmusok, optimalizálási módszerek állhatnak ezek hátterében? A szakdolgozatban bemutatott, pont a poligonban vizsgálat módszerek alapjai publikus dokumentációkon alapulnak (lásd Irodalomjegyzék), de a gyakorlati életből, saját tapasztalatom által, saját munkámmal, ötletekből finomodtak, fejlesztettem tovább, melyeket összefoglalva mutatom be ezen szakdolgoztban, mellékelve az általam Qt fejlesztőkörnyezetben [11] C++

nyelven fejlesztett, az egyes módszerek performanciájának különbségét

szemléltető demo alkalmazással.

6

2 Pont a poligonban vizsgálat matematikai háttere Először geometriai szempontból fogom elemezni, hogyan dönthető el egy pontról, hogy egy adott poligonon belül helyezkedik -e el, majd a számításhoz felhasználható vektoralgebrai módszereket ismertetem.

2.1 Az illeszkedés vizsgálat geometriai elemzése A geometriai elemzés során ismertetem a síkidomra, poligonra illeszkedés vizsgálatának általános elvét, illetve a felmerülő, az általános vizsgálattal nem, vagy hibás eredményt adó kivételes esetek okát, arra való megoldásaimat.

2.1.1 Síkidomra illeszkedés vizsgálata általános esetben A vizsgálatokat Euklideszi síkon, derékszögű (Descartes) koordináta rendszerben végzem el. Síkbeli pont síkidomra illeszkedésének vizsgálata azon a megfigyelésen alapul, hogy ha egy (végtelen) egyenes metszi a (véges kiterjedésű) síkidomot, akkor az egyenes egy síkidomon kívüli P1 pontjából az egyenesen egy irányban haladva, minden metszéspontnak, ahol beérkezünk a síkidom területére, kell legyen egy metszéspont párja, ahol kilépünk a síkidomból, lévén, hogy a véges kiterjedésű síkidomból az egyenes a végtelenben biztosan a síkidomon kívül van.

3. Ábra: síkidom egyenessel vett metszéspontjainak száma általános esetben páros: minden belépési ponthoz tartozik egy kilépési pont. 7

Amennyiben a síkidomba több alkalommal lépünk be (pld. konkáv poligonok, lyukas síkidomok esetében), akkor síkidomba való belépő és kilépő metszéspontok sorrendje kötött, minden belépés után kilépésnek kell következnie (azaz egy egyenes mentén haladva nem léphetünk be kétszer a síkidomba, majd kétszer ki). Így ha a vizsgált pontból kiinduló félegyenesnek páratlan számú metszéspontja van a síkidommal (például a 3. Ábrán P2 pont), akkor a félegyenesre illeszkedő egyenest vizsgálva összesen páros számú metszéspont csak úgy lehetséges, ha a vizsgált pont épp egy belépő és egy kilépő metszéspontpár között helyezkedik el, következésképp a vizsgált pont a síkidomon belül helyezkedik el. Ha pedig a pontból kiinduló félegyenesnek páros számú metszéspontja van a síkidommal (például a 3. Ábrán P1 pont), akkor a félegyenesre illeszkedő egyenesen összesen páros számú metszéspont csak úgy lehetséges, ha a pont egy belépő metszéspont előtt helyezkedik el, következésképp a vizsgált pont a síkidomon kívül helyezkedik el.

2.1.2 Síkidomra illeszkedés vizsgálatának speciális esetei Kivételes esetek, amelyek a fenti, általános illeszkedés esetében helyes szabály (páros, páratlan metszéspontszám) alól speciális illeszkedés miatt kivételek és a megvalósítás során ezen speciális illeszkedéseket szükséges lesz külön lekezelni: - ha a „belépő” metszéspont egyben „kilépő” is (például ha a félegyenes egy pontban érinti a síkidomot), - ha a metszéspontok száma végtelen (ez abban az esetben fordul elő, ha a félegyenes és a síkidom határa illeszkedik egy szakaszon).

8

4. Ábra: kivételes esetek, melyek külön lekezelendőek (példa)

Az általános, illetve speciális illeszkedésű esetek konkrét lekezelésének, az ellentmondás

feloldásának

ismertetését

már

csak

poligonokra

(sokszögekre)

vonatkozóan fogom a szakdolgozat későbbi fejezeteiben ismertetni.

2.1.3 Bemenő (poligon) adatokra vonatkozó megkötések Az általánosabb, síkidomra illeszkedés után térjünk át a speciálisabb, poligonokra való illeszkedésvizsgálatra. A módszerek során felteszem, hogy a bemenő poligonok geometriailag szabályosak, azaz: •

legalább 3 oldallal rendelkeznek,

•

minden oldal hossza nagyobb, mint 0 (azaz egy oldal kezdő és végpontja nem eshet egybe)

•

nincs 2 olyan oldal, amely egymást metszi.

9

A poligonok lehetnek azonban összetettek, azaz az input adat tartalmazhat: •

különálló részpoligonokat (például: különálló kontinensek),

•

részpoligonokon belül lyukakat (például: tavak a kontinenseken),

•

a lyukakon belül további részpoligonokat (például: szigetek a tavakban),

•

szigeteken belül további lyukakat (belső tavak),

•

és így tovább, tetszőleges mélységig...

A geometriai szabályosságnak (nem lehetnek metsző oldalak) valamennyi különálló részpoligonra (szigetre, lyukra) külön-külön és összességében is teljesülnie kell, függetlenül attól, hogy az oldalak azonos poligonhoz tartoznak-e (azaz összességében nem lehet olyan oldal párost találni, amelyek metszőek legyenek).

2.1.4 Poligon oldalára vagy csúcsára illeszkedő pont vizsgálata Ha a vizsgált pont a poligon határára, azaz a poligon oldalára vagy csúcsára illeszkedik, akkor a pontot jelen szakdolgozatban a poligonra esőnek tekintem. Bizonyos felhasználás során elképzelhető, hogy ennek a fordítottja célszerű (a határvonalat nem a poligonhoz tartozónak tekinteni). Az ismertetett algoritmusok minimális módosítással mindkét döntés mellett egyformán működnek, így hatékonyság szempontjábol nem lényeges kérdés, hogy melyik változat mellett döntünk. Az viszont már meghatározó kérdés lesz több algoritmus esetében, hogy ezzel az esettel (poligon oldalára, csúcsára illeszkedést) a számítások során általában külön is kell, illetve érdemes foglalkozni: - egyrészt gyorsítható vele a számítás: ha a poligon valamely oldalára esik a pont, akkor fölösleges további oldalakkal való metszéseket vizsgálni, a „pont a poligonban” eldöntendő kérdés megválaszolható (jelen esetben a döntésem alapján: illeszkedik), - másrészt több esetben a módszerből levezetett geometriai, matematikai képlet ilyen speciális esetekben hibát (például 0-val osztás), vagy ellentmondásokat eredményezhet (például a metszéspontok száma alapján téves döntést hoznánk) ezért a kivételes esetek lekezelése miatt szükséges vele külön foglalkozni. Ezen ellentmondásokra tehát az egyes módszereknél kitérek.

10

2.1.5 Poligonra illeszkedés vizsgálata általános esetben Alapesetben tehát vizsgálandó, hogy a pontból tetszőleges irányba felvett félegyenesnek a poligonnal hány metszéspontja van. Ha a metszéspontok száma: - páros: akkor a pont kívül esik a poligonon, - ha páratlan, akkor a pont a poligonra illeszkedik.

A metszéspontok meghatározásához a poligon oldalait egymás után (mint szakaszokat, a szakaszhoz tartozónak tekintve a két végpontját is) megvizsgálom, hogy van-e metszéspontja az előbbi módon meghatározott félegyenessel. Ha a szakasznak és a félegyenesnek van metszéspontja, akkor egy változóban növelem a metszéspontok számát (megszámlálás programozási tételét alkalmazva). Miután végigiteráltam az összes poligon oldalon, az összeg eredményeképp eldönthető az illeszkedés.

5. Ábra: Általános esetben a pontból indított félegyenesnek a poligon oldalaival számított összes metszéspontjai darabszámának paritása alapján eldönthető az illeszkedés. Az 5. ábrán látható általános esetekben egyértelműen eldönthető a metszéspontok számának paritása alapján az illeszkedés.

11

2.1.6 Kivételek, speciális esetek melyek lekezelendőek Nézzük meg a speciális eseteket, melyekhez kivételek lekezelése szükséges, különben az alap algoritmus hibás, inkonzisztens eredményt adna. A kivételes esetek többsége esetében a kivétel megfogalmazása szinte magában hordozza annak lekezelését is. Néhány speciális elhelyezkedésű félegyenes esetében azonban ez nem igaz, azaz azok lekezelése nem feltétlenül magától értetődő, így a következő három fejezetben először ezen három, nem kézenfekvő módon lekezelhető kivételt ismertetem, ezután pedig ismertetem az egyszerűbb eseteket is.

2.1.6.1 Poligon csúcsára illeszkedő félegyenes

6. Ábra: Csúcsra illeszkedő félegyenes ellentmondásos esete. P1 és P2 esetében a poligon oldalaival vett metszéspontok pontosan ugyanazok (egybeesnek P2 -vel)

A 6. ábrán a P1 ponthoz tartozó félegyenesnek és a P2 ponthoz tartozó félegyenesnek pontosan ugyanazok a poligon oldalaival vett metszéspontjaik (egybeesnek P 2 -vel) mégis a P1 kívül esik a poligonon, míg a P2 illeszkedik. Az alap algoritmussal egyiket sem tekinteném illeszkedőnek. Ellentmondás feloldása: a metszéspontok számítása során a poligon oldalára (így a csúcsára is) illeszkedést ellenőrzöm. Ha illeszkedik a pont a poligon valamely oldalára, akkor a megszámlálást abbahagyom, és illeszkedőnek tekintem a pontot. 12

2.1.6.2 Poligon oldalára illeszkedő félegyenes vizsgálata

7. Ábra: Oldalra illeszkedő metszésvizsgálathoz használt félegyenes ellentmondásos esete

A 7. ábrán a P1 ponthoz és P2 ponthoz tartozó félegyenesnek végtelen számú metszéspontja van a poligon f oldalával, mivel a félegyenesek illeszkednek az oldalra. P2

pont

poligonra

illeszkedését

könnyen

el

fogja

dönteni

az

oldalra

illeszkedésvizsgálattal módosított algoritmus, az f oldalra illeszkedés alapján. P1 pont illeszkedésének vizsgálatánál a félegyenes és az f oldal metszésvizsgálata nem célravezető, mivel végtelen sok metszéspontjuk van, ez paritás szempontjából nem vizsgálható. Mivel azonban az illeszkedő f oldal esetén nem történhet átlépés a poligon területére / területéről az ellenkező oldalról, így helyesen döntök, ha az f oldalt (általánosan a félegyenesre illeszkedő oldalakat) nem veszem figyelembe a metszéspontok számlálásánál. A 7. ábrán látható problémának ezen módon való lekezelése (félegyenesre illeszkedés esetén az oldalt ne vegyük figyelembe a metszéspontok számának meghatározásánál) azonban önmagában még kevés, a vázolt elhelyezkedés ugyanis egy új, az eddig vázolt megoldásokkal nem lekezelhető további problémát vet fel. Nézzük a következő, általánosabb esetet a problémára!

13

2.1.6.3 Oldal végpontjára illeszkedő félegyenes vizsgálata

8. Ábra: Oldal végpontjára illeszkedő metszésvizsgálathoz használt félegyenes ellentmondásos esete I.

A 8. ábrán két poligon, S1 és S2 látható. A P pontból induló félegyenesnek pontosan ugyanazok a metszéspontjai S1 -gyel, mint S2 -vel (az f oldallal való végtelen metszéspontot az előzőek alapján már nem veszem figyelembe). Mégis P pont S1 -gyen kívül, míg S2 -n belül helyezkedik el. A következő ábrán látható, hogy az ellentmondás nem csak abban az esetben jelentkezik, ha valamelyik (jelen esetben f) oldalra illeszkedik a vizsgálathoz használt félegyenes.

14

9. Ábra: Oldal végpontjára illeszkedő metszésvizsgálathoz használt félegyenes ellentmondásos esete II.

A 9. ábrán két poligon, S1 és S2 látható. A P pontból induló félegyenesnek pontosan ugyanazok a metszéspontjai S1 -gyel, mint S2 -vel: S1 esetében g és f; S2 esetében g és f' oldalak közös végpontjai. Mégis P pont S1 -gyen kívül, míg S2 -n belül helyezkedik el. Ellentmondás

feloldása:

mivel

az

illeszkedésvizsgálat

azon

alapul,

hogy

megszámolom, hányszor történik áthaladás a poligon (síkidom) határvonalain, meg kell különböztetem azt az esetet, amikor nem történik ténylegesen áthaladás határvonalon attól az esettől, amikor történik. Annak eldöntéséhez, hogy történik-e tényleges áthaladás a határvonalon, a következőt teszem: ha a félegyenesnek egy f oldallal való metszéspontja pontosan az f oldal egyik végpontjára (a poligon csúcsára) illeszkedik, akkor csak abban az esetben számítom a metszéspontot a be/kilépések megszámlálása során, ha az f oldal másik végpontja a félegyenessel meghatározott két félsík közül egy kiválasztott (az én megvalósításomban: a félegyenes fölötti) félsíkban helyezkedik el. A 10. ábrán bemutatom, hogy így módosítva a metszéspontok megszámlálását, helyes paritású eredményt kapunk.

15

10. Ábra: Annak eldöntése, hogy csúcsra illeszkedő félegyenes esetén történik-e ténylegesen poligon határvonalán áthaladás: a metszéspont számláláskor az f, g oldal másik (a félegyenesre nem illeszkedő) végének a kiválasztott félsíkban kell lennie.

A 10. ábra szerint vázolt esetekben S1 poligonhatáron áthaladás megszámlálásánál f oldalt figyelembe veszem, g oldalt nem (mivel g oldal félegyenesre nem illeszkedő végpontja nem a megfelelő félsíkban van). Így a poligonhatáron áthaladást helyesen f, g -re összesen egyszer számolom. S2 poligonhatáron áthaladás megszámlálásánál mind az f', mind a g' oldalt figyelembe veszem, így összesen kétszer számolom, azaz a paritás, így az illeszkedésvizsgálat szempontjából helyesen. Ez gyakorlatilag annak felel meg, mintha ugyanabban a pontban be, majd kilépünk a poligonból. S3 poligonhatáron áthaladás megszámlálásánál sem az f'', sem a g'' oldalt nem veszem figyelembe, így egyszer sem számolom, azaz paritás, így az illeszkedésvizsgálat szempontjából helyes. A csúcsra illeszkedő sugár metszésvizsgálatnál a félsíkra illeszkedés vizsgálatával való korrekció ötletét Dr. Sárközi Ferenc műve alapján használtam [3]. A következő fejezetekben az egyszerűbb kivéleteles eseteket ismertetem.

16

2.1.6.4 Poligon oldalára illeszkedő pont vizsgálata

11. Ábra: Poligon oldalára illeszkedő pontok esetén a metszéspontok számának paritása nem egyértelműen dönti el az illeszkedést

A 11. ábrán a P1 ponthoz tartozó félegyenesnek kettő, míg a P 2 ponthoz tartozó félegyenesnek egy metszéspontja van a poligon oldalaival. Az alap algoritmust használva (azaz metszéspontok paritása alapján) ebben az esetben nem egységesen döntenék, P1 pontot nem illeszkedőnek, míg a P2 pontot a poligonra illeszkedőnek tekinteném. Ellentmondás feloldása: a korábban már bevezetett módosítással, azaz a metszéspontok számítása során a poligon oldalára illeszkedés ellenőrzésével helyes eredményt kapok. Ha illeszkedik a vizsgált pont a poligon valamely oldalára, akkor a megszámlálást abbahagyom, és illeszkedőnek tekintem a pontot.

17

2.1.6.5 Poligon csúcsára illeszkedő pont vizsgálata

12. Ábra: Csúcsra illeszkedő pontok esetén a metszéspontok számának paritása nem egyértelműen dönti el az illeszkedést A 12. ábrán a P1 ponthoz tartozó félegyenesnek kettő, míg a P2 ponthoz tartozó félegyenesnek három metszéspontja van a poligon oldalaival. Az alap algoritmust használva ebben az esetben nem egységesen döntenék, P2 pontot illeszkedőnek, míg a P1 pontot a poligonra nem illeszkedőnek tekinteném. Ellentmondás feloldása: az előző esethez hasonlóan, a metszéspontok számítása során a poligon oldalára (így a csúcsára is) illeszkedést ellenőrzöm. Ha illeszkedik a pont a poligon valamely oldalára, akkor a megszámlálást abbahagyom, és illeszkedőnek tekintem a pontot.

2.1.6.6 Összetett poligonok vizsgálata Összetett (azaz például különálló szigetekből, vagy poligonon belül lyukakat tartalmazó poligonok) az egyes részpoligonokat egységesen, azonos módon: a sarokpontjai megadásával tárolom. A részpoligonok esetében nem szükséges tehát explicit eltárolni, vizsgálni, hogy az adott részpoligon egy poligont, vagy lyukat ír-e körül.

18

13. Ábra: Összetett síkidom / poligon esetében a határvonal átlépés megszámlálása szempontjából indifferens, hogy a határvonal lyukat vagy szigetet ír körül.

A 13. ábrán a két részpoligont, S1-et és S2-t pontosan ugyanolyan módon, egy-egy vektorban a csúcsaik koordinátáival tárolom, a közöttük lévő viszonyra (S 1 tartalmazza S2 -t), hierarchiára vonatkozó információ tárolása nélkül. A síkidom határon áthaladás megszámlálása szempontjából ugyanis indifferens, hogy az adott határvonal milyen jellegű poligonrészt (lyuk, vagy sziget) ír körül, a határvonal átlépés darabszáma csak, ami lényeges. Természetesen ehhez szükséges a 2.1.3. fejezetben írt, geometriai szabályosság betartása (azaz nem lehetne például a fenti képen S 1 és S2 is sziget, azaz a félegyenesen haladva nem léphetünk kétszer be a poligonba, majd kétszer ki. Illetve nem lehet S1-nek és S2-nek egymást metsző oldalpárja).

19

2.2 Az illeszkedés vizsgálat vektoralgebrai megvalósítása A fenti geometriai vizsgálatok megvalósításához, valamint az illeszkedésvizsgálat optimalizálása, és a demo alkalmazásban a megjelenítéshez a következő vektoralgebrai képleteket, megoldásokat alkalmazom.

2.2.1 Pont illeszkedése téglalap területére Az X : (x , y) pont illeszkedik a P : (p x , py) , Q : (qx , qy) pontokkal, mint két átellenes sarkával megadott téglalap területére, ha •

Min(px ,qx) ≤ x ≤ Max(px ,qx) és

•

Min(py ,qy) ≤ y ≤ Max(py ,qy)

2.2.2 Pont illeszkedése egyenesre Az X : (x , y) pont illeszkedik a P : (p x , py) , Q : (qx , qy) két pontjával megadott egyenesre, ha x px qx

y py qy

1 1 1

=0

A pont egyenesre illeszkedésének eldöntésére több más módszer is alkalmazható lenne, például: •

az egyenes implicit behelyettesítéssel,

egyenletének

meghatározásával

és

abba

•

a pontból húzott sugár és az egyenes metszéspontjának meghatározása segítségével.

A lehetséges módszerek közül a választásom azért esett Dr. Hajder Levente előadásjegyzetében [4] szereplő fenti módszerre, mert más módszerekkel ellentétben ezen módszernél nincs szükség kivételek lekezelésére (más módszereknél szükséges lehet végtelen meredekség illetve 0-val való osztás elkerülésének ellenőrzése), valamint a fenti determináns a csupa 1-es oszlop miatt számítási igényben sem jelentős. A kivételes esetek (0-val osztás, végtelen meredekség) hiánya párhuzamos programozásos megvalósítás (pld. grafikus kártya programozás) esetében jelenthet számottevő könnyedséget. 20

2.2.3 Pont illeszkedése szakaszra Az X : (x , y) pont illeszkedik a P : (p x , py) , Q : (qx , qy) két végpontjával megadott szakaszra, ha •

X illeszkedik P és Q egyenesére és

•

X illeszkedik a P és Q (átellenes sarokpontokkal definiált) téglalapra

2.2.4 Félegyenes és szakasz metszéspontja Az X : (x , y) pontból kiinduló v : (1, 0) irányvektorú félegyenes (sugár) metszi a P : (px , py) , Q : (qx , qy) két végpontjával megadott szakaszt, ha s=

y 0− p y ∈ [0,1] q y −p y

A metszéspont ekkor: m = p + s (q - p) Ahol p a P -be mutató vektor, q a Q -ba mutató vektor, m a metszéspontba mutató vektor (Dr. Hajder Levente előadásjegyzete alapján [5]).

21

3 Felhasználói dokumentáció 3.1 A demo alkalmazás célja A PolygonDemo alkalmazás különböző módszerekkel valósítja meg síkbeli pontok poligonra illeszkedésének vizsgálatát. Az egyes módszerek hatékonysága, futási ideje között több nagyságrendi eltérés lehet, az alkalmazás célja ezen hatékonyságbeli különbségek demonstrálása.

3.2 Az alkalmazás futtatása Az szakdolgozathoz csatolt CD-n található (bin/PolygonDemo) futtatható állomány 32 bites Ubuntu 14.04 verziójú operációs rendszerhez készült. A futtatás előfeltétele Linux operációs rendszer alatt a Qt core és Qt gui (libqt5core5a és libqt5gui5) csomagok telepítése. Ennek telepítése Ubuntu 14.04 operációs rendszer esetében terminal ablakban a következő parancsokkal lehetséges: sudo apt-get install libqt5core5a sudo apt-get install libqt5gui5

Más operációs rendszeren való használathoz szükséges a forráskódot az adott operációs rendszerre (fejlesztővel) lefordítani, a futtatáshoz szükséges csomagokat pedig a Getting started with Qt [11] dokumentáció alapján telepíteni. Ezután, a PolygonDemo állományt merevlemezre kell másolni, majd futtatható attribútumot beállítani: chmod +x PolygonDemo

Majd az alkalmazás indítása: ./PolygonDemo

22

3.3 A grafikus felület elemei Az alkalmazás indítása után a következő ablakot látjuk:

14. Ábra: A demo alkalmazás kezdőképernyője A felső eszközsoron található ikonokkal tudjuk az alkalmazást vezérelni. Az ikonok funkciója: Ikon

Funkció Open: poligonokat leíró MIF fájl megnyitása Zoom in: az eszközt kiválasztva, majd a térképre kattintva a térképi nézetet közelíthetjük Zoom out: az eszközt kiválasztva, majd a térképre kattintva a térképi nézetet távolíthatjuk Pan: az eszközt kiválasztva, majd a térképen az egér bal gombját lenyomva tartva a térképi nézetet mozgathatjuk (vonszolhatjuk) Start check: a kiválasztott pont-a-poligonban meghatározási módszert elindíása Brute force pont-a-poligonban vizsgálat kiválasztása Keep model pont-a-poligonban vizsgálat kiválasztása MBR pont-a-poligonban vizsgálat kiválasztása Qt keretrendszer kiválasztása

saját

pont-a-poligonban

vizsgálatának

23

Gemoetry bin hash pont-a-poligonban vizsgálat kiválasztása Gyorsított gemoetry bin hash pont-a-poligonban vizsgálat kiválasztása Gyorsított gemoetry band hash pont-a-poligonban vizsgálat kiválasztása

3.3.1 Mif fájl szerkezete A MIF fájl szerkezetéről általános leírás található a mellékelt interchange_file.pdf dokumentumban, mely a MapInfo Professional térinformatikai szoftver felhasználói dokumentációjának [12] része. A fenti általános leírás nagyon részletes, a MIF fájlokról a PolygonDemo alkalmazás használatához elégséges tudnivalók a következők: A MIF fájl szöveges állomány. A mellékelt CD-n a data könyvtárban található minta állomány. A fájlszerkezet megértéshez nézzük a következő tartalmú példát:

24

Version 800 Charset "WindowsLatin2" Delimiter "," CoordSys NonEarth Units "m" Bounds (0, 0) (10000000, 10000000) Columns 2 Id Decimal(10, 0) Gridcode Decimal(10, 0) Data Region 2 5 100 100 100 200 200 200 200 100 100 100 4 130 130 150 180 180 130 130 130 Pen (1,2,0) Brush (2,16777215,16777215) Center 150 150 Region 1 5 300 100 300 200 400 200 400 100 300 100 Pen (1,2,0) Brush (2,16777215,16777215) Center 150 150

A fejlécben található karakterkódolásra, koordinátarendszerre, leíró (attribútum) mezőkre vonatkozó információkat figyelmen kívül hagyja az alkalmazás. A megadott koordinátákat Descartes -féle (derékszögű) koordinátarendszerben értelmezi, földrajzi koordinátarendszereket (pld. WGS-84, UTM) nem ismer. Megjegyzés: a pont-apoligonban számítási módszer földrajzi koordinátarendszer esetében is működik, amennyiben a poligon nem lép át térképszelvény határon (azaz a poligonnak mindegyik csúcsa ugyanazzal a transzformációval, vetítéssel van meghatározva). Szintén figyelmen kívül hagyja az alkalmazás a megjelenési stílusra vonatkozó Pen, Brush, Center clause -okat (az alkalmazás a megjelenítéshez fix vonal, kitöltési stílusokat használ). A poligonok leírása a Region kulcsszóval kezdődik. A Region kulcsszó utáni szám az összetartozó részpoligonok számát jelenti. Így a Region 2

25

tehát egy poligont és azon belül egy lyukat, vagy 2 külön szigetből álló poligont jelent. A következő szám a poligon csúcsainak száma + 1 (mivel a MIF specifikáció szerint [12] az első csúcs, egyben az utolsó is kell legyen, tehát kétszer szerepel), majd az x, y koordinátapárok szerepelnek, szóközzel elválasztva. Tehát például a: Region 2 5 100 100 100 200 200 200 200 100 100 100 4 130 130 150 180 180 130 130 130

A képen látható (100,100) (200,200) befoglalójú négyzetet és azon belül egy háromszög alakú lyukat definiálja.

3.3.2 Mif fájl megnyitása Az Open

ikonra kattintás után (az operációs rendszernek megfelelő) fájl open

dialógusablak jelenik meg, ahol kiválasztható a betöltendő, poligonokat tartalmazó MIF fájl.

15. Ábra: A MIF fájl kiválasztásra szolgáló dialógusablak A MIF fájl beolvasásakor a korábbi esetleges betöltött poligonok, illetve vizsgált teszt pontok térkép nézetről törlődnek, és a térkép a beolvasás ideje alatt kék háttérrel 26

jelenik meg.

16. Ábra: a MIF fájl beolvasása után a betöltött poligon látható az ablakban A fájl betöltése után a térképi nézet automatikusan a poligonok középpontjára ugrik, a nézet x irányú kiterjedése pedig poligonok x koordináta irányú kiterjedése lesz. A MIF fájl beolvasása közben új fájl megnyitása kezdeményezhető, ha a felhasználó ismételten az Open

ikonra kattint. Ekkor a folyamatban lévő fájl beolvasása

leállításra kerül, és az újonnan kiválasztott fájl fog betöltődni.

3.3.3 Navigáció a térképen A térképen zoomolás, nézet mozgatása a korábban már említett ikonokkal történhet: Ikon

Funkció Zoom in: az eszközt kiválasztva, majd a térképre kattintva a térképi nézetet közelíthetjük Zoom out: az eszközt kiválasztva, majd a térképre kattintva a térképi nézetet távolíthatjuk Pan: az eszközt kiválasztva, majd a térképen az egér bal gombját lenyomva tartva a térképi nézetet mozgathatjuk (vonszolhatjuk)

27

3.3.4 Alkalmazott módszer kiválasztása Az illeszkedésvizsgálat módszerének kiválasztása a kiválasztott módszer nevével megegyező feliratú nyomógombra kattintva, tehát a következőkkel lehetséges:

17. Ábra: Az illeszkedésvizsgálat módszerének kiválasztására szolgáló nyomogombok Az aktuálisan kiválasztott módszer (a 17. ábrán az „MBR check”) kerettel kiemelve jelenik meg. A módszerek a listában a várható hatékonyság sorrendjében szerepelnek (várhatóan a bal oldali futási ideje a leghosszabb, a jobb oldalié a legrövidebb). Az egyes módszerek közötti pontos különbség ismertetését lásd a fejlesztői dokumentációban.

3.3.5 Illeszkedésvizsgálat indítása A betöltött poligonokra az illeszkedésvizsgálat indítása a Start check

ikonra

kattintva lehetséges. Az illeszkedésvizsgálat a Magyar szabvány szerinti EOV (Egységes Országos Vetület) koordinátarendszerben [13] Magyarország területére eső 3760 darab (fix elhelyezkedésű), rácspontokra illesztett pontokra fut le. Az illeszkedésvizsgálat folyamán a már vizsgált pontok folyamatosan kerülnek fel a térképre, az illeszkedésvizsgálat alatt a térképi navigáció (zoomolás, nézet mozgatása) továbbra is használható. Szintén választható új MIF fájl megnyitása, illetve új módszerrel az illeszkedésvizsgálat újraindítható, ezen esetekben az éppen futó vizsgálat megszakad. A térképre a már vizsgált pontok közül az illeszkedő pontok piros, a nem illeszkedőek fekete színnel kerülnek fel.

28

18. Ábra: A vizsgált pontok közül a poligonra illeszkedő pontok piros, a nem illeszkedőek fekete színnel jelennek meg

3.3.6 Illeszkedésvizsgálat eredménye A vizsgálat során a hatékonyság méréséhez, statisztika készítéséhez az alkalmazás a standard outputra szöveges formában a futással kapcsolatos következő információkat írja ki: Number of points in MIF file: 76798 MBR calculation START "13:05:42.149" CHECKSTART "13:05:42.209" END "13:05:43.529" Intersection calculation = 2482818

29

Mely információk értelmezése: Státusz bejegyzés

Jelentés

Number of points in MIF file: 76798

A MIF fájlban lévő poligonok összesen 76798 csúcsból állnak

MBR calculation

A kiválasztott kalkulációs metódus

START "13:05:42.149"

A kalkuláció kezdetének időpontja

CHECKSTART "13:05:42.209"

A csúcsok listájából a kiválasztott módszerhez tartozó modellalkotás befejezésének az időpontja (modellalkotás: pld. a hash kódok, részpoligonok MBR -jeinek kiszámítása). Az első teszt pont illeszkedésének vizsgálata ezután kezdődik.

END "13:05:43.529"

Az utolsó teszt pont illeszkedésének vizsgálatának befejezése.

Intersection calculation = 2482818

Az illeszkedésvizsgálat során a metszésvizsgálatok száma.

30

4 Fejlesztői dokumentáció 4.1 A fejlesztőkörnyezet A demo alkalmazás C++ programozási nyelven, a nyílt forráskódú Qt Creator 3.0.1es verziójú fejlesztőkörnyezetben készítettem [11]. A Qt fejlesztőkörnyezet több platformon elérhető (Windows, Linux, Mac OS X) a telepítéséről, használatával kapcsolatos tudnivalókat az adott operációs rendszerre vonatkozóan lásd az előbbi hivatkozáson. A fejlesztőkörnyezetben a teljes demo alkalmazás megnyitásához a File > Open File or Project... menüpontot, majd a PolygonDemo.pro projekt filet kell megnyitni.

4.2 Az alkalmazás architekturális tagozása Az alkalmazás megvalósítása során a háromrétegű szoftver architektúrájú megvalósítás elvét [6] követtem, azaz az alkalmazás osztályait a következő rétegekre osztva valósítottam meg: megjelenítési réteg, üzleti logikai réteg, perzisztencia réteg.

4.2.1 Kommunikáció a szálak között A megjelenítés külön szálban fut (annak érdekében, hogy a grafikus felület a hosszabb műveletek során ne fagyjon be). A megjelenítési szál és más szálon feldolgozást végző objektumok közötti kommunikációt a Qt „Signals and slots” objektumok közötti kommunikációt biztosító mechanizmussal valósítottam meg. Ezen mechanizmus a Qt objektumok között kényelmes, típusellenőrzött, könnyen konfigurálható kommunikációt biztosít a következő módon: minden QObject osztályból származtatott osztály definiálhat signal (jelzés) és slot (nyílás) módosítóval megkülönböztetett függvényeket. A QObject::connect függvénnyel összekapcsolható egy signal egy adott objektumból egy másik objektum slot függvényével (vagy akár több objektummal is) és a kapcsolat az objektumok signal-ja és slot-ja között bejegyzésre kerül a Qt metaobjektum kezelő rendszerébe. A jelzés kibocsájtásakor (amely az emit utasítással történik) a signal az összes hozzá tartozó slot -hoz a metaobjektum kezelő rendszer által automatikusan eljut, azaz a signal kibocsájtásakor a kapcsolódó objektumok slot függvényei a megfelelő paraméterezéssel meghívásra kerülnek.

31

19. Ábra: Qt objektumok összekapcsolása signals and slots mechanizmussal [7].

Bővebb információ a Signals and slots mechanizmusról: a [7], iletve a mechanizmus működéséről különböző szálak között a [8] hivatkozásokban található.

4.2.2 Rétegfüggetlen osztály A Generator osztály az alkalmazás indításakor létrehozza az összes réteg működéséhez szükséges objektumokat, melyet a header fájlban kommenttel is jelzek: // Generator osztály // Feladata az alkalmazás összes rétegének // a szükséges objektumok létrehozása class Generator : public QObject

4.2.3 Perzisztencia réteg A réteg az input adatok (vektoros MIF fájl) olvasását valósítja meg. A réteghez tartozó osztályok: Osztály

Funkciója

FileHandler

interfacet biztosít a magasabb rétegek felé, amin keresztül kiszolgálhatóak a réteg által biztosított fájlbetöltéssel kapcsolatos műveletek

MifParser

a MapInf MIF vektoros fájl beolvasását valósítja meg

32

Az osztályok alapvető funkciója részletesebben, a header fileok commentjeiből kimásolva: // FileHandler osztály // Létrehozza a vektoros adatokat beolvasó MifParser objektumot // és interfacet biztosít közötte, illetve a model réteg // (vectorHandler osztály) között class FileHandler : public QObject // MifParser osztály // A poligon adatokat tartalmazó vektoros // Mif filet beolvasását valósítja meg class MifParser : public QObject

4.2.4 Üzleti logikai réteg A réteg a pont-a-poligonban meghatározási módszerek megvalósításához szükséges osztályokat tartalmazza. A módszerek közötti különbséget lásd a 4.3 Pont a poligonban vizsgálat megvalósításai, az optimalizálás lépései fejezetben. A rétegben lévő osztályok: Osztály

Funkciója

AbstractContainCalculate

absztrakt osztály, az összes módszerek közös szülője

BruteForceCalculate

a Brute force módszert megvalósító osztály

GeoLineF

geometriai szakaszt és szükséges műveleteit valósítja meg

GeometryHashBandCalculate

a Geometry Hash Band módszert megvalósító osztály

GeometryHashBinCalculate

a Geometry Hash Bin módszert megvalósító osztály

GeoRectF

geometriai téglalapot valósítja meg

HashBandLineF

a GeoLineF osztály kiegészítése a Geometry Hash Band módszerhez szükséges hash kód számítással

HashBinLineF

a GeoLineF osztály kiegészítése a Geometry Hash Bin módszerhez szükséges hash kód számítással

KeepModelCalculate

a Keep model módszert megvalósító osztály

MBRCalculate

az MBR módszert megvalósító osztály

QtContainCalculate

a Qt contain calculate módszert megvalósító osztály

RayLineF

a GeoLineF osztály kiegészítése a „végtelenbe” húzott sugár műveleteivel

VectorHandler

interfacet biztosít az alacsonyabb és magasabb rétegek felé, amin keresztül kiszolgálhatóak a réteg által biztosított (pont-a-poligonban meghatározáshoz kapcsolódó) műveletek

és

pont-a-poligonban

szükséges

műveleteit

33

Az osztályok alapvető funkciója részletesebben, a header fileok commentjeiből kimásolva: // GeoLineF osztály // Szakaszt, valamint a rajta értelmezett, szükséges // vektoralgebrai műveleteket megvalósító osztály class GeoLineF // GeoRectF osztály // Téglalapot, valamint a rajta értelmezett, szükséges // vektoralgebrai műveleteket megvalósító osztály class GeoRectF : private QRectF // AbstractContainCalculate osztály // Absztrakt osztály, az egyes pont-a-poligonban // meghatározási módszerek szülő osztálya. // A grafikus felület fagyása elkerülése érdekében // külön szálban kerül végrehajtásra class AbstractContainCalculate : public QThread // BruteForceCalculate osztály // Pont-a-poligonban meghatározási módszert // megvalósító osztály class BruteForceCalculate : public AbstractContainCalculate // GeometryHashBandCalculate osztály // Pont-a-poligonban meghatározási módszert // megvalósító osztály class GeometryHashBandCalculate : public AbstractContainCalculate // HashBandLineF osztály // A GeoLineF (szakasz) osztály // kiegészítése a HashBand módszer szerinti // geometriai hash kód számítással class HashBandLineF : public GeoLineF // GeometryHashBinCalculate osztály // Pont-a-poligonban meghatározási módszert // megvalósító osztály class GeometryHashBinCalculate : public AbstractContainCalculate // HashBinLineF osztály // A GeoLineF (szakasz) osztály // kiegészítése a HashBin módszer szerinti // geometriai hash kód számítással class HashBinLineF : public GeoLineF // KeepModelCalculate osztály // Pont-a-poligonban meghatározási módszert // megvalósító osztály class KeepModelCalculate : public AbstractContainCalculate // MBRCalculate osztály // Pont-a-poligonban meghatározási módszert // megvalósító osztály

34

class MBRCalculate : public AbstractContainCalculate // QtContainCalculate osztály // Pont-a-poligonban meghatározási módszert // megvalósító osztály class QtContainCalculate : public AbstractContainCalculate // RayLineF osztály // A GeoLineF (szakasz) osztály // kiegészítése a sugár specifikus vektoralgebrai // művelettel (sugár - szakasz metszéspont számítással) class RayLineF : public GeoLineF // VectorHandler osztály // Létrehozza a felhasználó választása szerinti // Pont-a-poligonban meghatározási módszernek megfelelő // objektumot és interfacet biztosít // a perzisztencia és megjelenítési réteg felé class VectorHandler : public QObject

4.2.5 Megjelenítési réteg A réteg a megjelenítéshez, felhasználói interakcióhoz szükséges osztályokat tartalmazza. A réteghez tartozó osztályok: Osztály

Funkciója

MainWindow

A fő ablakot megvalósíto osztály

MapWidget

A grafikus felület központi, térképi nézetet tartalmazó Widgetet megvalósító osztály

MifLoader

A MIF fájl beolvasását a grafikus felületen elindító osztály

// Felsorolások headerje // A grafikus felület kezeléséhez szükséges felsorolások // (kiválasztott menüpontok, tool -ok megnevezése) definiciói enum MapTool {PAN, ZOOMIN, ZOOMOUT}; enum CalculationMethod { BRUTE_FORCE, KEEP_MODEL, BINARY_MBR, GEOMETRY_BIN_HASH, GEOMETRY_BAND_HASH, MBR_CHECK, QT_CONTAIN}; // MainWindow osztály // A grafikus felület, fő ablakot, menüelemek kezelését // megvalósító osztály class MainWindow : public QMainWindow // MapWidget osztály // A grafikus felület központi, a térképes, // vektoros adatokat megjelenítő Widget eleme class MapWidget : public QWidget

35

// MifLoader osztály // A vektoros MIF poligon adatokat beolvasást // a felhasználói interakció nyomán elindító osztály // A grafikus felület fagyása elkerülése érdekében // külön szálban kerül végrehajtásra class MifLoader : public QThread

4.3 Pont a poligonban vizsgálat megvalósításai, az optimalizálás lépései A fejezetben a pont poligonra illeszkedés vizsgálatának hatékonyságjavítására tett lépéseit, különböző módszereit, illetve demo alkalmazás hatékonyságmérésének, statisztikájának készítéséhez használt mintaadatokat ismertetem.

4.3.1 A szakdolgozat statisztikájának készítéséhez használt mintaadat A szakdolgozathoz az optimalizálás bemutatásához demo alkalmazást készítettem, melynek bemenő poligon adatainak megadását MIF (MapInfo Interchange Format) típusú fájl beolvasásával valósítom meg. A demo alkalmazáshoz működéséhez, a poligonok megadásához szükséges tudnivalókat lásd a felhasználói dokumentáció fejezetben. A poligonok megadására, tárolására szolgáló adatszerkezet a MIF fileban a poligonok a csúcsaik listája. A beolvasáskor, az egyes rétegek közötti adatátadáskor szintén ezt az adatszerkezetet használom. Az egyes illeszkedésvizsgálatot megvalósító módszerek belső adattárolására azonban már más adatszerkezeket (pld: oldalak listáját, hash kóddal kiegészített oldalak listáját) is használok.

36

Az általam használt mintaadatok (az üzleti érzékenység miatt sok évvel korábbi, nem megnevezett rádiós technológiára és jelszintre vonatkozó, jelenleg már nem aktuális adatokat tartalmazó) magyarországi mobil lefedettségi térképek: Minta Csúcsok poligon száma

1. minta

Minta nézet

221 462

2. minta 1 133 127

37

A minta poligonokra való illeszkedést minden módszer esetében állandó, rácsszerűen a következő mintapontokra vonatkoztatva vizsgálom: Mintapontok száma

Mintapontok elhelyezkedése

3760

4.3.2 „Brute force” módszer Brute force (magyarul nyers erő) módszer során az alap algoritmust, bármilyen optimalizálás, átalakítás nélkül alkalmazom. Így tehát minden vizsgált pont esetében felépítem az oldalak listáját és az összes oldallal metszésvizsgálatot végzek.

20. Ábra: Brute force (nyers erő) módszere, az alap algoritmus szerinti metszésvizsgálat alkalmazása minden részpoligon minden oldalára 38

A módszer alkalmazása során tehát annyi metszésvizsgálat szükséges, ahány oldala összesen van az összes részpoligonnak. A 20. ábrán például összesen 22 oldal lévén, 22 metszésvizsgálat lesz szükséges. A módszerhez tartozó algoritmus:

Eredmények a mintaadaton: 1. minta Metszésvizsgálatok száma Futási idő a mintapontokkal [óra:perc:mp]

2. minta

860 980 629 4 092 439 362 0:15:54

1:12:22

4.3.3 „Keep model” módszer Keep model (model megtartása) módszer abban különbözik a Brute force módszertől, hogy az eljárás elején felépített oldalak listáját nem törlöm az egyes pontok 39

vizsgálata után, hanem megtartom, és csak az összes pont vizsgálata után dobom el. Ezáltal valamivel több memóriát igényel, de egymás után több pont megvizsgálása esetén hatékonyabb a Brute force módszernél. A módszerhez tartozó algoritmus:

Eredmények a mintaadaton: 1. minta Metszésvizsgálatok száma Futási idő a mintapontokkal [óra:perc:mp]

40

2. minta

860 980 629 4 092 439 362 0:06:51

0:15:15

4.3.4 „MBR check” módszer MBR (Minimal Bounding Rectangle, azaz legkisebb befoglaló téglalap) módszer során a metszéspont vizsgálatot csak azon részpoligonok oldalaival végzem el, amelyek esetében a vizsgált pont a poligon (x,y koordináták minimális és maximális értékei alapján meghatározott) legkisebb befoglaló téglalapjába esik, mivel ezen esetben lehetséges, hogy a pont egyáltalán az adott poligonon belül lehet.

21. Ábra: MBR (Minimal Bounding Rectangle) esetén csak azon poligonok oldalaival történik metszésvizsgálat, amelyek legkisebb befoglaló téglalapjára illeszkedik a vizsgált pont. A fenti példán P1 esetében 0 darab, P2 esetében pedig 2 darab poligon oldalaival. A módszer megvalósításához a következő adattípust használom: typedef struct { GeoRectF MBR; QList lines; } MBRPolygon;

Ahol

GeoRectF : átellenes sarkaival megadott téglalap osztály, QList< > : listát megvalósító template (generikus) osztály, GeoLineF : végpontjaival megadott szakasz osztály.

A módosítással több száz, több ezer, különálló részpoligonokból álló összetett terület esetén jelentős számú metszéspontvizsgálat takarítható meg. A befoglaló legkisebb téglalapok meghatározása, valamint az azokra való illeszkedésvizsgálat mind plusz számításigényben, mind a plusz memóriahasználatban elhanyagolható a keep model 41

módszerhez képest. A módszerhez tartozó algoritmus:

Eredmények a mintaadaton: 1. minta Metszésvizsgálatok száma Futási idő a mintapontokkal [p:mp]

42

2. minta

9 100 101

649 904 316

0:20

8:41

4.3.5 „Qt contain” módszer Ezen módszer során a Qt fejlesztőkörnyezet beépített pont-a-poligonban vizsgálatát használom. Tekintettel arra, hogy a Qt környezet elrejti a pontos agoritmust (pontosabban mivel nyilt forráskódú környezetről van szó: aránytalanul nagy erőforrást jelentene számomra annak kiderítése) a pontos módszer, így a metszésvizsgálatok száma általam nem ismert. Az eredményeket a kereskedelmi szoftver performanciájával való összehasonlítás céljából adom meg. Az eredmények futási idejének nagységrendje alapján nagy valószínűséggel a következőkben bemutatandó Geometry bin hash módszerhez hasonló megvalósítás szerint működik. Eredmények a mintaadaton: 1. minta Metszésvizsgálatok száma Futási idő a mintapontokkal [mp]

2. minta

nem ismert

nem ismert

18.38

97.71

4.3.6 Geometry bin hash módszer Az már bemutatott MBR módszer további optimalizálásra ad lehetőséget: az összehasonlítások

száma

ugyanis

térbeli

indexeléssel,

hashelésel

jelentősen

csökkenthető. Alkalmas indexelés, hashelési módszer választásával ugyanis a metszésvizsgálat szempontjából eleve kizárható jelentős számú poligon oldal, amelyekkel biztos nem lesz metszéspont. Indexelés esetében a poligon, vonalszakaszok MBR -einek (azaz min, max koordináták) -ra történő indexekkel történhet például a keresés a metszésvizsgálat szempontjából szóba jövő poligonokra. Jelen szakdolgozatomban nem indexeléssel, hanem hasheléssel valósítottam meg a hatékonyság javítását, ennek módszerét ismertetem a következőkben.

4.3.6.1 Hashelés általános bemutatása A hashelés a programozási feladatok közül a keresés hatékonyságának javítására alkalmas módszer. A következőkben egy neveket és telefonszámokat tartalmazó példán keresztül mutatom be a hashelés működését, a hatékonyság javításának elvét. 43

Tekintsük a következő (telefonkönyvi adatokat tartalmazó) táblázatot (fizikai adatszerkezete tetszőleges, lehet memóriában tárolt tömb, fájl rekordok, stb):

Név

Telefonszám

Sherman Medina

555-4321

Ian Carlson

666-9012

Elaine Keller

309-1949

Nicholas Webb

554-7986

Tracy Daniels

309-4413

Marion Wade

444-4321

Luis Paul

666-5322

Billie Greer

554-3242

Gerard Bridges

309-9898

Thomas Ryan

555-3222

Szeretnénk a telefonkönyvből például Luis Paul telefonszámát megtudni. A fenti adatmodellben ezt lineáris kereséssel tudjuk megtenni, azaz a lista első elemét megvizsgáljuk, és megnézzük, hogy a bejegyzés a keresett nevet tartalmazza -e. Ha igen, akkor megállunk, megtaláltuk a keresett telefonszámot. Ha nem, továbblépünk a következő sorra, ahol ugyanúgy elvégezzük a vizsgálatot. Ezt sorról sorra ismételjük, amíg a keresett nevet meg nem találjuk, vagy a lista utolsó elemét is megvizsgáltuk. Ezzel a módszerrel n darab listaelem esetén, a keresés várható műveletigénye: n/2 , azaz (feltételezve, hogy egyenlő valószínűséggel keresem a lista bármely elemét) várhatóan a lista elemszámának a felét kell végignézni, mire megtaláljuk a keresett telefonszámot. Hashelés segítségével a következőképp gyorsíthatjuk fel a keresést. Meghatározunk egy alkalmas Keresés mezőjének alaptípusa→ ℕ függvényt, amely megadott keresett értékre mindig ugyanazt a természetes számot generálja. A fenti listában (lévén, hogy a keresés személynevekre történik, így a keresés alaptípusa szöveg) ez speciálisan egy String→ ℕ függvény, aminek a megvalósítása 44

célszerűen lehet a nevek (ASCII, UTF-8) karakterkódjai alapján számított valamilyen függvény. A táblázat felépítésekor a keresés mezőjére alkalmazott hash függvény egyértelműen meg fogja határozni a listában való lehelyezkedést, a következőképpen: ha a táblázatnak m sora van, akkor a keresés mezőjére alkalmazott hash függvényérték MOD m -edik sorába kerül az adott bejegyzés. A lenti táblázatban tehát az elfoglalt pozíció már a Név hash kódjától (MOD m) függ, a hash kódot feltüntettem a Név után zárójelben.

Pozició

Név (hash kód)

Telefonszám

0

Nicholas Webb (39)

554-7986

2

Sherman Medina (54)

555-4321

3

Luis Paul (55)

666-5322

4

Tracy Daniels (225)

309-4413

5

Marion Wade (44)

444-4321

Billie Greer (33)

554-3242

9

Thomas Ryan (9)

555-3222

10

Elaine Keller (36)

309-1949

11

Ian Carlson (24)

666-9012

12

Gerard Bridges (38)

309-9898

1

6 7 8

A táblázatban (alkalmas hash függvény esetén) a keresés ekkor konstans (azaz a tárolt elemszámoktól független) műveletigénnyel kereshető, a következőképp: 1. Meghatározzuk a „Luis Paul” szöveg hash kódját: 55. 2. Kiszámoljuk a a hash kódnak a táblázat sorainak számával vett maradékát = 55 MOD 13 = 3. 3. A keresett bejegyzés tehát a táblázat 3. sorában található (ha van ebben a sorban bejegyzés). 4. Ha nincs ebben a sorban bejegyzés, akkor a táblázat nem tartalmazza a keresett nevet. Ha (hash kód ütközés esetén) több bejegyzés is van az adott sorban, akkor egy 45

lehetséges megoldás: a táblázatban azonos sorhoz tartozó elemeket láncolt listában tárolva, lineáris kereséssel folytatható a kérdéses elem keresése. A hash tábla kialakításánál felmerülő kérdésekre (pld. alkalmas táblaméret megválasztása,

karbantartása,

hash

ütközés

lekezelése)

nem

térek

ki

(a

megvalósításához a Qt fejlesztőkörnyezet QHash generikus adattípusát használom, amely ezen feladatokat elvégzi). A szakdolgozatban általam megvalósítandó feladata viszont a geometriai objektumok alkalmas hash függvényének megvalósítása, melyet a következőkben ismertetetk.

4.3.6.2 Geometriai hashelés A

hashelést

a

poligont

alkotó

oldalak

és

végtelenbe

húzott

sugár

metszésvizsgálatának felgyorsításához fogom haszálni. A célom, hogy lényegesen lecsökkentsem a metszéspontvizsgálatok darabszámát, azáltal hogy a sugár hash kódjának megfelelő hash kódú oldalakkal legyen csak szükséges a metszésvizsgálatot elvégezni. Ehhez olyan hash kód függvényt kell definiálnom, amely ha két szakasz egymást metszi, akkor biztosan azonos, ha nem metszőek, akkor pedig nagy valószínűséggel különböző hash kódot rendel. Az megvalósítandó hash függvénynek tehát a helyesség és hatékonyságjavítás érdekében a következőket kell biztosítania: - a függvény az értékek széles skáláját vegye fel, lehetőleg egyenletes eloszlásban (a hashelés csak ekkor lesz várhatóan konstans műveletigényű), - az egymást metsző geometriai objektumok hash függvénye azonos értékű legyen, - az egymást nem metsző objektumok hash értéke lehetőleg különbözzön.

A fenti kritériumokat egyszerre egy szakaszhoz egy hash kód hozzárendelésével nem tudom teljesííteni, ezért az előző fejezetben ismertetett általános hasheléshez képest a megvalósításomban a hash függvény egy Szakasz → {ℕ} függvény, azaz a függvény értékkészlete természetes számok halmaza. A hash kód halmaz egy eleme (egy természetes szám) egy téglalap alakú részterületre illeszkedést fog jelenteni.

46

A hash kódok (rész téglalapokra illeszkedés) meghatározásának lépéseit a következő ábrasorozaton mutatom be:

22. Ábra: A geometriai hash kód meghatározás első lépése. Meghatározom az összes poligont magában foglaló MBR -t.

23. Ábra: az átláthatóság kedvéért az ábrán nézzük csak az s1 sugár, és három oldal (o1 , o2 , o3) hash kódjainak meghatározását a továbbiakban.

47

24. Ábra: első lépésben az MBR hosszab oldalának felezőpontjainál két rész téglalapra osztom az eredeti téglalapot. A két fél téglalap közül a bal oldali a legutolsó helyiértékű bitjén 0 a jobb oldali 1- es értékű hash kódú lesz (a hash kód többi bitje még nem ismert). Ha az éppen számított szakasz (akár csak részben) illeszkedik a fél MBR területére, az adott szakaszra és téglalapra rekutzívan meghívom ugyanezt a téglalapfelezés eljárást.

25. Ábra: a következő lépésben a bal (előző ábrán xxx0 kódú) és jobb (előző ábrán xxx1 kódú) oldali téglalapot vízszintesen felezem, és a második helyiértékű bit értéke lesz 0 vagy 1 attól függően, hogy a alsó vagy felső fél téglalapról van szó (xxx0 → xx00 és xx10, illetve xxx1 → xx01 és xx11 hash kódú téglalapokká felezem).

48

26. Ábra: további rekurzióval folytatom a téglalapfelezés eljárást azon résztéglalapokra, amelyeket az adott szakasz érint (az ábrán szereplő szakaszokkal az xx00 felbontása x000 és x100 -ra már például nem történik meg, mivel egyik szakasz sem érinti az xx00 téglalapot. Így csak a hash kódok alakulásának szemléltetéséért szerepelnek az ábrán az x000 és x001 résztéglalapok).

27. Ábra: az eljárást megadott szintig folytatva meghatározom az adott szakaszhoz rendelt hash kódok (résztéglalapok) halmazát.

49

A fenti módszerrel tehát a következő (bináris formátumú) hash kódok kerülnek az egyes szakaszokhoz: s1 : {1001, 1101} o1 : {1101, 0101} o2 : {1011} o3 : {1010, 0010} A hash táblába az oldalakat minden hozzá meghatározott hash kóddal bejegyzem (a gyakorlatban egy példányt hozok létre az oldal objektumból és a hash táblába egy rá mutató pointer kerül). Így például a fenti oldalakat tartalmazó hash tábla: Pozició

Geometriai hash kód

Oldal pointer

0

1101 (13)

o1*

0010 (10)

o3*

0101 (5)

o1*

10

1010 (10)

o3*

11

1011 (11)

o2*

1 2 3 4 5 6 7 8 9

12

Két szakasznak akkor lehetséges metszéspontja, ha van közös hash kódjuk, mivel ekkor van olyan közös hash téglalap, amelyet mindkettő szakasz érint. A metszéspontok megszámlálásához tehát elég csak a sugár hash kódjaival megegyező hash kódokhoz tartozó oldalakat kikeresnem a hash táblából, és csak ezekkel metszésvizsgálatot végeznem. Előfordulhat, hogy a vizsgált sugár és egy poligon oldal nem csak egy, hanem több közös hash téglalapot is érint. 50

28. Ábra: az s1 sugárnak és o1 oldalnak több közös geometriai hash kódja is van, mind az 1001 mind pedig a 1101 -es kódú téglalapot érinti mindkét szakasz. A metszéspont megszámlálásakor a helyes eredmény érdekében ezen ismétlődéseket detektálni szükséges.

A metszéspontok megszámlálásakor egy „vizsgált_oldalak” halmazban (melyet QHashSet típussal valósítok meg) nyilvántartom a már vizsgált oldalak egyedi sorszámát és metszésvizsgálat előtt ellenőrzöm, hogy az adott oldallal történt-e már metszésvizsgálat. Ha már történt, akkor nem végzem el újra, mivel ez esetben ugyanazt a metszéspontot számolnám még egyszer meg.

51

4.3.6.3 A módszert megvalósító algoritmus A módszert megvalósító algoritmus a fentiek figyelembevételével a következő:

52

4.3.6.4 Futási idő, műveletigény statisztika a módszerre a mintaadatokkal A gyakorlati tapasztalataim szerint a módszert megvalósítása során a területfelezést addig érdemes folytatni, amíg egy bin mérete az átlagos poligon oldalhosszánál kb. 1 nagyságrenddel nagyobb. Ha ennél kisebbre állítom a hash bin méretet, akkor a nagy számosságú hash tábla bucketek miatti memóriafoglalási illetve, a hash tábla karbantartási műveletek száma miatt a hash tábla kezelése miatt romlik a performancia. Ennél nagyobb hash bin méret esetén viszont a hashelés nem, illetve kevésbé éri el a célját, mivel egy – egy bucketbe nagyon sok elem kerül. A mintaadataim kb. 30 – 60 méteres átlagos oldalhosszakat tartalmaznak és a hash bin-ek előállításakor 13 téglalapfelezés beállításakor értem el a legjobb eredményeket. Mivel a mintaadat kb. 500 x 300 km -es területet fed le, így (7 illetve 6 felezés során) egy bin mérete kb. 3900 x 4700 méteresre adódik a legjobb eredményt adó 13 felezés alkalmazása során. Eredmények a mintaadaton: 1. minta Metszésvizsgálatok száma Futási idő a mintapontokkal [mp]

2. minta

1 332 227

9 620 476

17.62

82.30

4.3.6.5 A módszer alkalmazása a meglévő vállalati rendszerbe integrált „dobozos” szoftverben Bár a módszer a szakdolozatban bemutatottak közül nem a leggyorsabb eredményt adja (a következőkben bemutatandó Geometry band hash gyorsabb), azonban előnye, hogy a területfelezés elvét használva, az input adatok (poligonok) módosításán keresztül a meglevő, dobozos

(így számomra ismeretlen pontos algoritmusú) szoftveren is

nagyságrendi performanciajavulást sikerült elérni. Ennek érdekében az input adatot a területfelezés elve szerint apróbb részekre bontom, majd a feldarabolt területet elmentem, és a dobozos alkalmazásban feldarabolva használom. Ezen dobozos alkalmazás feltehetőleg az „MBR check” módszerhez hasonlót valósít meg, azaz a százezres nagyságrendű oldalak közül csak azon részpoligon oldalaival végez metszésvizsgálatot, amelyek MBR poligonja

53

illeszkedik a vizsgált pontra. A feldarabolást a MapInfo Professional szoftver saját fejlesztőkörnyezetében, MapBasic programozási nyelven készítettem el.

4.3.7 Gyorsított geometry bin hash módszer A Geometry bin hash módszer gyorsítását a következő két ötlet alapján valósítottam meg: 1. A poligonokat alkotó oldalak hash kód számítása

(valószínűségi alapon)

gyorsítható: lévén, hogy a poligon oldalai folytonosan egymás után megadva következnek a MIF fájlban, így nagy valószínűséggel azonos hash binben helyezkednek el, mivel az átlagos oldalhossz kb. egy nagyságrenddel kisebb a bin oldalának méretnél. Ezért a hash kód számítást módosítom : a hash kódok számítása során mindig nyilvántartom a legutóbbi számított hash kódot és hash bint. Az aktuális oldal hash kód számítása előtt ellenőrzöm, hogy az adott oldal a legutolsó számolt binre illeszkedik -e. Ha annak a belső területén van, akkor nem szükséges rekurzív módon újraszámolni a a hash kódot, ezáltal lényegesen felgyorsul a kezdeti modellalkotás. 2. Ugyanazon poligon oldallal való többszöri ütközésvizsgálat elkerülésének gyorsítása: az előző, Geometry bin hash módszer során minden vizsgált pont esetében a sugár ütközésvizsgálatához már figyelembe vett oldalak egyedi sorszámát (ID attribútumát) egy QHashSet-ben (hash halmaz) tároltam. Ennek a halmaznak az inicializálása, folymatos karbantartása, benne való keresés erőforrásigénye nem túl nagy, de elhagyásával mégis egy kis performanciajavítás elérhető. A QHashSet-ben való tárolás helyett minden oldalhoz új attribútomot veszek fel, amelyben tárolom, hogy melyik sugárral (annak azonosítóját ID-t eltárolva) történt utoljára

ütközésvizsgálat. Tekintettel

arra,

hogy

a

demo

alkalmazásban

az

ütközésvizsgálat (egyetlen) dedikált threaden történik, így biztos lehetek benne, hogy ezt az azonosítószámot másik thread nem módosítja. Ha egy poligon oldal esetében az utolsó sugár ID megegyezik az aktuális sugár ID -vel, akkor az oldalt már vizsgáltam az aktuális sugár esetében, így nem végzek vele

54

újra metszésvizsgálatot. A módszer többszálúsítása esetén is megoldható lenne így a többszörös ütközésvizsgálat elkerülése: ekkor azonban több utolsó vizsgált sugár ID-t lenne szükséges nyilvántartani a poligon oldalakhoz (thread ID -nként egyet-egyet). Eredmények a mintaadaton: 1. minta Metszésvizsgálatok száma Futási idő a mintapontokkal [mp]

2. minta

1 332 227

9 620 476

3.14

14.51

4.3.8 Geometry band hash módszer Ez a módszer az elterjedt

geometry bin módosított változata, a módszer

továbbfejlesztése saját ötlet alapján törént. A geometry band (magyarul: sáv) hash módszer esetében téglalapok helyett hash sávok segítségével, gyorsítom (választom ki) az ütközésvizsálathoz szükséges poligon oldalakat.

29. Ábra: A geometry band hash módszernél nem téglalapokra, hanem az egyik irányban határtól határig terjedő sávokra (egyik irányban lényegesen nagyobb kiterjedésű téglalapra) történik a hash egységek meghatározása.

55

Ez esetben fontos, hogy a „végtelenbe” húzott sugár ne az összes poligont magában foglaló MBR befoglaló téglalap legközelebbi oldala felé, hanem mindig a sávok irányával megegyező (x vagy y koordinátatengellyel párhuzamos) irányú legyen. A hash kódok ilyen módon való számításának előnye a bin hash módszerhez képest: •

a hash kód számolása lényegesen egyszerűbb: az egyik koordinátának konstassal osztása, majd a hányados egészrésze megadja a hash kódot,

•

a sugárhoz (megfelelő irány választása esetén) egyetlen hash kód fog tartozni (hash kód halmaz helyett) így többszöri hash kód egyezés nem lehetséges. Ezért biztos, hogy minden poligon oldalt csak egyszer vizsgálunk, a metszéspontok megszámlálásakor tehát nem szükséges nyilvántartani a már vizsgált poligon oldalakat.

A módszer a leggyorsabb a bemutatottak közül, mind a modellalkotás, mind a lekérdezés ideje ebben az esetben a legkevesebb. 1. minta Metszésvizsgálatok száma

2. minta

151 207

973 239

0.44

2.32

Futási idő a mintapontokkal [mp]

4.4 A módszerek összehasonlítása A módszerek hatékonyságának, összehasonlításának áttekintésére nézzük a következő összefoglaló táblázatot. Módszer

Futási idő az 1. mintán

Futási idő a 2. mintán

Brute force [ó:p:mp]

0:15:54

1:12:22

Keep model [ó:p:mp]

0:06:51

0:15:15

0:20

8:41

MBR [p:mp] Qt contain [mp]

18.38

97.71

Geometry bin hash [mp]

17.62

82.30

Gyorsított geom. bin hash [mp]

3.14

14.51

Geometry band hash [mp]

0.44

2.32

A táblázatban a hatékonyság (futási idő) szerint rendezve láthatóak az egyes 56

módszerek. Megjegyzés: a módszerek elnevezése saját (kivéve az MBR kifejezést, amely térinformatikai alkalmazásoknál elterjedt fogaom). Jól látható, hogy az általános módszer jelentősen gyorsítható egyedi, speciális megoldással. Az általam ismert régebbi térinformatikai rendszereknél az MBR -en alapuló, újabbak esetében pedig az általam „Geometry bin hash” -ként elnevezetthez hasonló elven működő módszereket alkalmaznak, jellemzően geometry index, spatial index elnevezéssel. Bővebb információt a piaci szoftverekben alkalmazott módszerekre lásd például: MS SQL Server dokumentáció [9], illetve Oracle adatbázis-kezelő dokumentációban [10]. Különösen figyelemre méltónak tartom az alapesethez képesti 4.1 milliárd metszéspontvizsgálat szükségességének 1 millióra csökkentését az elvvel. Párhuzamos programozással (pld. videokártya programozással) a hashelést nem használó módszerek lényegesen gyorsíthatóak lehetnek. A leghatékonyabb, hash band módszer hagyományos programozásos megvalósítása azonban már önmagában is olyan óriási hatékonyságjavulást jelent, amelyet a munka kezdetekor nem is feltételeztem. A szakdolgozat „folytatására” a Geometry band hash módszer eredményének további vizsgálatára, továbbfejlesztésére legcélszerűbbnek annak vizsgálatát tartom, hogy a Geometry band hashelés elve milyen módon, sikerességgel használható más felhasználási területen pld.: térinformatikán belül szakaszok metszésvizsgálatához, poligonok, síkidomok uniójának, metszetének, különbségének meghatározásához. Használata felmerülhet azonban a térinformatikától eltérő területen is (pld.: 2, 3 dimenziós modellezés, grafikus gyorsítás).

57

5 Tesztelési terv 5.1 Felhasználói felület funkcionális tesztelése A felhasználói felületet blackbox módszerrel teszteljük, azaz a teszteset szerinti elvárt eredményt ellenőrizzük, a pontos algoritmus részletes vizsgálata nélkül. Teszteset megnevezése

Tesztelés lépései

Elvárt eredmény

MIF fájl megnyitása 1. Az alkalmazás indítása után a grafikus felületen az A fájl betöltődik, a poligonok a Open ikonra kattintás térképen megjelennek. 2. A megjelenő dialógusablakban MIF fájl kiválasztása MIF fájl megnyitásának megszakítása újabb fájl kiválasztásával

1. Az alkalmazás indítása után a grafikus felületen az Az első fájl betöltése megszakad, a Open ikonra kattintás másodikhoz tartozó poligonok a 2. A megjelenő dialógusablakban MIF fájl kiválasztása térképen megjelennek. 3. A kiválasztott MIF fájl betöltése alatt ismételt kattintás az Open ikonra 4. Az újabb dialógusablakban másik MIF fájl kiválasztása

MIF fájl megnyitásának megszakítása kilépéssel

1. Az alkalmazás indítása után a grafikus felületen az A fájl betöltése megszakad, az Open ikonra kattintás alkalmazás ablaka bezáródik. 2. A megjelenő dialógusablakban MIF fájl kiválasztása 3. A kiválasztott MIF fájl betöltése alatt az ablak bezárása az (x) ablakkezelő ikonra kattintva

Térképi navigáció alapesetben

MIF fájl betöltése után a térkép nézeten: 1. Nézet közelítése (zoom in) 2. Nézet távolítása (zoom out) 3. Nézet mozgatása (pan)

A nézet a kiválasztott navigációnak megfelelően változik

Térképi navigáció illeszkedésvizsgálat közben

MIF fájl betöltése után, illeszkedésvizsgálat folyamata közben a térkép nézeten: 1. Nézet közelítése (zoom in) 2. Nézet távolítása (zoom out) 3. Nézet mozgatása (pan)

A nézet a kiválasztott navigációnak megfelelően változik, az illeszkedésvizsgálat folyamatban marad, új pontok kerülnek fel a térképre

Illeszkedésvizsgálat kiválasztása

Az illeszkedésvizsgálat kiválasztására szolgáló nyomógombok kiválasztása egyesével, egymás után, majd véletlenszerű sorrendben

A kattintásnak megfelelő nyomógomb kiválasztott (bekeretezett) lesz

Illeszkedésvizsgálat elindítása

Az illeszkedésvizsgálat kiválasztására szolgáló nyomógombok: 1. Brute force 2. Keep model 3. MBR check 4. Qt contain 5. Geo. bin hash 6. Quick geo. bin hash 7. Geo. band hash közül az egyik kiválasztása, majd a Start check ikonra kattintás. A teszt eset ismétlése (véletlenszerű sorrendben), hogy mindegyik módszer sorra kerüljön.

A kiválasztásnak megfelelő módszer elindul: a térképre felkerülnek a vizsgált pontok, a standard outputon olvasható a módszer megnevezése, és a futásra vonatkozó statisztikai értékek

58

Illeszkedésvizsgálat újraindítása

Az illeszkedésvizsgálat egyszeri elindítása után egy másik módszer kiválasztása , majd ismét a Start check ikonra kattintás. A teszt eset ismétlése (véletlenszerű sorrendben), hogy mindegyik módszer sorra kerüljön (másodikként).

Az első módszer futása megszakad, a térképről törlődnek az első futtatásra vonatkozó pontok. Ezután a térképre ismét elkezdenek felkerülni a második elindítás által a pontok, a standard outputon olvasható a második módszer megnevezése, és a futásra vonatkozó statisztikai értékek

5.2 Illeszkedésvizsgálat módszerek tesztelése 5.2.1 Az illeszkedésvizsgálat blackbox teszt esetei Először nézzük itt is a blackbox teszt eseteket, azaz az algoritmus részletes vizsgálata nélküli teszteket. Teszteset megnevezése


Elvárt eredmény

Brute force módszer 1. Az alkalmazás indítása után a grafikus felületen a tesztelése Brute force módszer kiválasztása 2. Legalább 10000 csúcspontból álló poligonokat tartalmazó MIF fájl megnyitása 3. Illeszkedésvizsgálat elindítása 4. A teszteset megismétlése legalább 3, különböző poligonokat tartalmazó MIF fájlon.

A vizsgált pontok (szemrevételezés alapján) az illeszkedésnek megfelelő színnel kiszínezve jelennek meg.

Keep model módszer 1. Új PolygondDemo alkalmazás példány indítása tesztelése után a grafikus felületen az Keep model módszer kiválasztása 2. Legalább 10000 csúcspontból álló poligonokat tartalmazó MIF fájl megnyitása 3. Illeszkedésvizsgálat elindítása 4. A teszteset megismétlése legalább 3, különböző poligonokat tartalmazó MIF fájlon.

A vizsgált pontok (szemrevételezés alapján) az illeszkedésnek megfelelő színnel kiszínezve, és a korábbi alkalmazáspéldányban, a Brute force módszerrel megegyezően jelennek meg.

MBR check módszer 1. Új PolygondDemo alkalmazás példány indítása tesztelése után a grafikus felületen az MBR check módszer kiválasztása 2. Legalább 10000 csúcspontból álló poligonokat tartalmazó MIF fájl megnyitása 3. Illeszkedésvizsgálat elindítása 4. A teszteset megismétlése legalább 3, különböző poligonokat tartalmazó MIF fájlon.

A vizsgált pontok (szemrevételezés alapján) az illeszkedésnek megfelelő színnel kiszínezve, és a korábbi alkalmazáspéldányban látható módszerrel megegyezően jelennek meg.

Qt contain módszer tesztelése


1. Új PolygondDemo alkalmazás példány indítása után a grafikus felületen a Qt contain módszer kiválasztása 2. Legalább 10000 csúcspontból álló poligonokat tartalmazó MIF fájl megnyitása 3. Illeszkedésvizsgálat elindítása 4. A teszteset megismétlése legalább 3, különböző poligonokat tartalmazó MIF fájlon.

59

Geo. bin hash módszer tesztelése

1. Új PolygondDemo alkalmazás példány indítása után a grafikus felületen a Geo. bin hash módszer kiválasztása 2. Legalább 10000 csúcspontból álló poligonokat tartalmazó MIF fájl megnyitása 3. Illeszkedésvizsgálat elindítása 4. A teszteset megismétlése legalább 3, különböző poligonokat tartalmazó MIF fájlon.


Quick geo. bin hash módszer tesztelése

1. Új PolygondDemo alkalmazás példány indítása után a grafikus felületen a Quick geo. bin hash módszer kiválasztása 2. Legalább 10000 csúcspontból álló poligonokat tartalmazó MIF fájl megnyitása 3. Illeszkedésvizsgálat elindítása 4. A teszteset megismétlése legalább 3, különböző poligonokat tartalmazó MIF fájlon.


Geo. band hash módszer tesztelése

1. Új PolygondDemo alkalmazás példány indítása után a grafikus felületen a Geo. band hash módszer kiválasztása 2. Legalább 10000 csúcspontból álló poligonokat tartalmazó MIF fájl megnyitása 3. Illeszkedésvizsgálat elindítása 4. A teszteset megismétlése legalább 3, különböző poligonokat tartalmazó MIF fájlon.


5.2.2 Az illeszkedésvizsgálat whitebox teszt esetei. A whitebox tesztelés során a felmerült geometriai általános és speciális eseteket pontosan előállítva teszteljük, hogy az algoritmusok az vázolt általános és speciális esetekben is az elvárt eredményt adják. Teszteset megnevezése


Elvárt eredmény

Egyszerű poligonra illeszkedés

Egy különálló négyzetet és háromszöget tartalmazó MIF fájl készítése úgy, hogy legyen tesztpont: - a poligonokon kívül, attól mind a négy irányban (lásd. 5. ábra), - a poligonokon belül (lásd 5. ábra), - a poligonok oldalaira illeszkedve (lásd 11. ábra), - a poligonok csúcsaira illeszkedve (konkáv és konvex esetben is, lásd 12. ábra).

A vizsgált pontok az illeszkedésnek megfelelő színnel kiszínezve jelennek meg valamennyi: 1. Brute force 2. Keep model 3. MBR check 4. Qt contain 5. Geo. bin hash 6. Quick geo. bin hash 7. Geo. band hash módszer esetében

Összetett poligonra illeszkedés

Egy négyzetet és azon belül egy háromszög alakú lyukat tartalmazó MIF fájl készítése úgy, hogy legyen tesztpont: - a poligonokon kívül, attól mind a négy irányban (lásd. 13. ábra), - a poligon területén, - a belső poligon (lyuk) területén, - a poligonok oldalaira (külső és belső is) illeszkedve, - a poligonok csúcsaira illeszkedve (külső és belső is).


60

Csúcsra illeszkedő félegyenes tesztelése

Egy konkáv poligont tartalmazó MIF fájl készítése úgy, hogy legyen tesztpont: - a konkáv csúcs szomszédos csúcsával egyező y koordinátán (lásd 6. ábra), - a konkáv csúcs szomszédos csúcsára illeszkedve (lásd 6. ábra)


Oldalra illeszkedő félegyenes tesztelése

Egy x tengellyel párhuzamos oldallal rendelkező poligont tartalmazó MIF fájl készítése úgy, hogy legyen tesztpont: - az x tengellyel párhuzamos oldal minden irányában (lásd 7. ábra), - az x tengellyel párhuzamos oldalon (lásd 7. ábra).


Oldal végpontjára illeszkedő félegyenes tesztelése I.

Két darab, az x tengellyel párhuzamos közös oldallal rendelkező poligont tartalmazó MIF fájl készítése a 8. ábra szerinti elrendezésben úgy, hogy legyen tesztpont: - az x tengellyel párhuzamos oldal minden irányában. Ezen tesztpontok között legyen olyan, amely az egyik poligonon belül, a másikon kívül helyezkedik el, - az x tengellyel párhuzamos közös oldalon.


Oldal végpontjára illeszkedő félegyenes tesztelése II.

Két darab, közös oldallal rendelkező poligont tartalmazó MIF fájl készítése a 9. ábra szerinti elrendezésben úgy, hogy legyen tesztpont: - a közös csúcs x koordinátájával egyezően az x tengellyel párhuzamosan minden irányában, - a közös csúcs y koordinátájával egyezően az y tengellyel párhuzamosan minden irányában, - a közös csúcson.


Oldal végpontjára illeszkedő félegyenes tesztelése III.

Három darab, közös y koordinátájú csúccsal rendelkező poligont tartalmazó MIF fájl készítése a 10. ábra szerinti elrendezésben úgy, hogy legyen tesztpont: - a közös y koordinátájú csúccsal megegyező y koordinátán, az S1 poligonon belül, valamint az S1 poligon y koordinátájú csúcsán, - a közös y koordinátájú csúccsal megegyező y koordinátán, az S1 poligonon kívül, mindkét irányban, - az S2 és S3 poligonok közös y koordinátájú csúcsain, illetve tőlük mindkét irányban.


A fenti összes teszt eseteket a demo alkalmazásra vonatkozóan elvégeztem, és mindegyik teszt során az elvárt eredményt tapasztaltam. 61

6 Melléklet: forráskódok A szakdolgozathoz mellékelt CD -n a teljes demo alkalmazás forráskódja elérhető. A szakdoglozat

dokumentációjába

a

forráskód

jól

tagoltsága,

következetessége,

kommentezettségét demonstrálandó a leghatékonyabb és saját ötletet tartalmazó Geometry band hash módszert megvalósításához közvetlenül kapcsolódó osztályok forráskódjait illesztem példaként (a többi forráskód hasonlóan, egységesen tagolt, kommentezett).

Fájl: model.hashbandlinef.h // HashBandLineF osztály // A GeoLineF (szakasz) osztály // kiegészítése a HashBand módszer szerinti // geometriai hash kód számítással #ifndef HASHBANDLINEF_H #define HASHBANDLINEF_H #include #include #include "model.geolinef.h" class HashBandLineF : public GeoLineF { public: HashBandLineF(QPointF point1, QPointF point2, GeoRectF fullMapBounds); inline QList getHashCodes() {return hashCodes;} private: QList hashCodes; void calculateHashCodes(GeoRectF fullMapBounds); static const qreal hashResolution = 8192; }; #endif // HASHBANDLINEF_H

62

Fájl: model.hashbandlinef.cpp #include "model.hashbandlinef.h" HashBandLineF::HashBandLineF(QPointF point1, QPointF point2, GeoRectF fullMapBounds) : GeoLineF(point1, point2) { calculateHashCodes(fullMapBounds); } void HashBandLineF::calculateHashCodes(GeoRectF fullMapBounds) { // A hash band line hash kódja a poligonok teljes // kiterjedési területének hosszabbik oldalának // sávokra osztásával kerül liszámításra if (fullMapBounds.width() > fullMapBounds.height()){ uint hashCodePoint1 = (uint)(p1().x() - fullMapBounds.left()) * hashResolution / fullMapBounds.width(); uint hashCodePoint2 = (uint)(p2().x() - fullMapBounds.left()) * hashResolution / fullMapBounds.width(); for (uint i = qMin(hashCodePoint1, hashCodePoint2); i <= qMax(hashCodePoint1, hashCodePoint2); ++i) { hashCodes.append(i); } } else { uint hashCodePoint1 = (uint)(p1().y() - fullMapBounds.top()) * hashResolution / fullMapBounds.height(); uint hashCodePoint2 = (uint)(p2().y() - fullMapBounds.top()) * hashResolution / fullMapBounds.height(); for (uint i = qMin(hashCodePoint1, hashCodePoint2); i <= qMax(hashCodePoint1, hashCodePoint2); ++i) { hashCodes.append(i); } } }

63

Fájl: model.geometryhashbandcalculate.h // GeometryHashBandCalculate osztály // Pont-a-poligonban meghatározási módszert // megvalósító osztály #ifndef MODEL_GEOMETRYHASHBANDCALCUATE_H #define MODEL_GEOMETRYHASHBANDCALCUATE_H #include #include #include #include #include #include

"model.hashbandlinef.h" "model.georectf.h" "model.abstractcontaincalculate.h"

class GeometryHashBandCalculate : public AbstractContainCalculate { Q_OBJECT public: GeometryHashBandCalculate(QList > *polygons, QList *points); ~GeometryHashBandCalculate(); void run(); private: GeoRectF fullMapArea; QHash hashBandLines; QList hashBandLinesDistinct; void calculateHashBandLines(); }; #endif // MODEL_GEOMETRYHASHBANDCALCUATE_H

64

Fájl: model.geometryhashbandcalculate.cpp #include #include #include #include #include

"model.geometryhashbandcalculate.h" "model.raylinef.h"

GeometryHashBandCalculate::GeometryHashBandCalculate(QList > *polygons, QList *points) : AbstractContainCalculate(polygons, points) { } GeometryHashBandCalculate::~GeometryHashBandCalculate(){ // A destruktorban töröljük a memóráiban a létrehozott hash band lineokat QListIterator hashBandLineIterator(hashBandLinesDistinct); while (hashBandLineIterator.hasNext()) { delete (hashBandLineIterator.next()); } } void GeometryHashBandCalculate::calculateHashBandLines() { // Inicializáljuk a hash táblát hashBandLines.reserve(8179); // Végigiterálunk az összetett poligont alkotó // részpoligonokon (szigetek, lyukak) QListIterator > polygonIterator(*polygons); while (!stopRequested && polygonIterator.hasNext()) { QList points = polygonIterator.next(); QListIterator pointIterator(points); const QPointF *previousPoint = NULL; const QPointF *currentPoint = NULL; // Az aktuális poligon csúcsain végigiterálunk while (!stopRequested && pointIterator.hasNext()) { currentPoint = &pointIterator.next(); if (NULL != previousPoint) { // A poligon csucsainak sorozatabol felepitjük a hash oldalak sorozatát HashBandLineF* hashBandLineF = new HashBandLineF(*previousPoint, *currentPoint, getFullMapArea()); hashBandLinesDistinct.append(hashBandLineF); // Mivel több hash kód tartozhat egy poligon oldalhoz, // az összes kóddal bejegyezzük a hash táblába QListIterator hashCodeIterator(hashBandLineF->getHashCodes());

65

while (!stopRequested && hashCodeIterator.hasNext()){ uint currentHashCode = hashCodeIterator.next(); hashBandLines.insertMulti(currentHashCode, hashBandLineF); } } previousPoint = currentPoint; } } } void GeometryHashBandCalculate::run(){ bool isFirstPoint = true; int vizsg = 0; bool emptyMapPolygon = (getFullMapArea().width() == 0 && getFullMapArea().height() == 0); // Feltöltjük a Hash táblát a megfelelő hash Line -okkal calculateHashBandLines(); // Végigiterálunk az illeszkedésre vizsgálandó input pontokon QListIterator pointIterator(*points); QPointF *intersectionPoint = new QPointF(); qDebug() << "CHECKSTART " << QTime::currentTime().toString("hh:mm:ss.zzz"); while (!stopRequested && pointIterator.hasNext()) { QPointF pointToCheck = pointIterator.next(); // Ha a térkép üres (nincs egyetlen poligon sem betöltve) // vagy az összes poligont magában foglaló négyzeten kívül esik // a vizsgálandó pont, akkor biztos nem illeszkedik if (emptyMapPolygon || !getFullMapArea().contains(pointToCheck)) { emit sendCheckedPoint(pointToCheck, false, !pointIterator.hasNext(), isFirstPoint); isFirstPoint = false; continue; } QPointF endPoint; // A "végtelenbe" húzott félegyenes készítése if (getFullMapArea().width() > getFullMapArea().height()) endPoint = QPointF(pointToCheck.x(), getFullMapArea().top()); else endPoint = QPointF(getFullMapArea().right(), pointToCheck.y()); RayLineF rayLine = RayLineF(pointToCheck, endPoint); // Meghatározzuk a sugár hash kódját HashBandLineF hashBandRayLine = HashBandLineF(rayLine.p1(), rayLine.p2(), getFullMapArea()); // A metszéspontok számának meghatározásához // végigiterálunk a sugár hash kódnak megfelelő hash kódú oldalakon

66

int numIntersects = 0; bool isWithin = false; uint rayLineHashCode = hashBandRayLine.getHashCodes().at(0); QHash::iterator lineToCheckIterator = hashBandLines.find(rayLineHashCode); while (!stopRequested && !isWithin && lineToCheckIterator != hashBandLines.end() && lineToCheckIterator.key() == rayLineHashCode) { HashBandLineF* currentGeoLine = lineToCheckIterator.value(); // Ha illeszkedik a poligon valamely oldalara a vizsgált pont, // akkor poligonra illeszkedőnek tekintem if (currentGeoLine->contains(pointToCheck)) { isWithin = true; break; } ++vizsg; if (rayLine.intersected(*currentGeoLine)){ // Az aktuális oldalt metszi a sugár, növelem // a metszéspontok számát ++numIntersects; } ++lineToCheckIterator; } if (!stopRequested) { isWithin = isWithin || (numIntersects % 2 == 1); emit sendCheckedPoint(pointToCheck, isWithin, !pointIterator.hasNext(), isFirstPoint); isFirstPoint = false; } } delete intersectionPoint; qDebug() << "END " << QTime::currentTime().toString("hh:mm:ss.zzz"); qDebug() << "Intersection calculation = " << vizsg; }

67

7 Irodalomjegyzék [1] John A. Magliacane : http://www.qsl.net/kd2bd/splat.html - 2014.12.03. [2] Wikimedia Commons : http://commons.wikimedia.org/wiki/File:YagiUda_antenna.JPG - 2014.12.03. [3] Dr. Sárközi Ferenc : Alapműveletek vektoros és raszteres térbeli adatokkal II, Budapesti Műszaki Egyetem, http://www.agt.bme.hu/tutor_h/terinfor/t26.htm 2014.12.03. [4] Dr. Hajder Levente : Számítógépes Grafika előadásjegyzet, Eötvös Lóránd Tudományegyetem, Informatikai Kar http://cg.elte.hu/~hajder/nappali_eloadas/BSc_EA_02.pdf - 2014.12.03. [5] Dr. Hajder Levente : Számítógépes Grafika előadásjegyzet, Eötvös Lóránd Tudományegyetem, Informatikai Kar http://cg.elte.hu/~hajder/nappali_eloadas/BSc_EA_05.pdf – 2014.12.03. [6] Wikipedia : Többrétegű architechtúra http://hu.wikipedia.org/wiki/T%C3%B6bbr %C3%A9teg%C5%B1_architecht%C3%BAra – 2014.12.03. [7] Digia plc. : Qt Project, Signals & Slots http://qt-project.org/doc/qt5/signalsandslots.html - 2014.12.03. [8] Digia plc. : Qt Project, Threads and QObjects http://qt-project.org/doc/qt-5/threadsqobject.html#signals-and-slots-across-threads - 2014.12.03. [9] Microsoft Corporation: MS SQL Server, Spatial Indexing Overview http://technet.microsoft.com/en-us/library/bb964712%28v=sql.105%29.aspx 2014.12.03. [10] Oracle Corporation: Oracle Spatial User's Guide and Reference, Indexing and Querying Spatial Data https://docs.oracle.com/cd/B10501_01/appdev.920/a96630/sdo_index_query.htm – 2014.12.03. [11] Digia plc. : Qt Project, Getting Started with Qt http://qt-project.org/doc/qt5/gettingstarted.html – 2014.12.03. [12] Pitney Bowes Software Inc. : MapInfo Professional User’s Guide, Appendix J: MapInfo Data Interchange Format

http://resource.mapinfo.com/static/files/document/1074660800077/interchange_file.pdf - 2014.12.03. [13] Dr. Varga József : Geodéziai vetületek jegyzet, Budapesti Műszaki Egyetem http://www.agt.bme.hu/staff_h/varga/vetulettan/katvet.html#eov - 2014.12.03.

68

Gyors térinformatikai algoritmusok mobiltelefon lefedettség vizsgálatához

Recommend Documents