Univerzita Karlova v Praze. Matematicko-fyzikální fakulta BAKALÁŘSKÁ PRÁCE. Adam Lutka. Testování viditelnosti na reliéfu mapy

Univerzita Karlova v Praze Matematicko-fyzikální fakulta

BAKALÁŘSKÁ PRÁCE

Adam Lutka

Testování viditelnosti na reliéfu mapy Katedra softwarového inženýrství Vedoucí bakalářské práce: doc. RNDr. Tomáš Skopal, Ph.D.

Studijní program: Informatika Studijní obor: IP Praha 2014

Poděkování Chtěl bych poděkovat panu doc. RNDr. Tomáši Skopalovi, Ph.D. za vedení mé bakalářské práce. Děkuji také panu Pavlu Uhliarovi technickému řediteli WIA spol s r. o. za námět tématu bakalářské práce a následnou trpělivou spolupráci při jeho přetváření na reálný produkt.

Prohlašuji, že jsem tuto bakalářskou práci vypracoval samostatně a výhradně s použitím citovaných pramenů, literatury a dalších odborných zdrojů. Beru na vědomí, že se na moji práci vztahují práva a povinnosti vyplývající ze zákona č. 121/2000 Sb., autorského zákona v platném znění, zejména skutečnost, že Univerzita Karlova v Praze má právo na uzavření licenční smlouvy o užití této práce jako školního díla podle § 60 odst. 1 autorského zákona.

V ................... dne ...................

podpis

Název práce: Testování viditelnosti na reliéfu mapy

Autor: Adam Lutka

Katedra / Ústav: Katedra softwarového inženýrství

Vedoucí bakalářské práce: doc. RNDr. Tomáš Skopal, Ph.D., Katedra softwarového inženýrství

Abstrakt: Provádět měření v terénu pro každý potenciální bezdrátový datový spoj je zbytečně nákladné. Aplikace, která by dokázala předem určit kvalitu podmínek pro vybudování takového spoje, by značně náklady omezila. Cílem práce je takovou aplikaci poskytnout a zprostředkovat tak uživateli informace potřebné pro rozhodnutí, zda má měření vůbec smysl.

Klíčová slova: prostorová data, Fresnelova zóna, 3D grafika ve webovém prohlížeči

Title: Line of sight testing

Author: Adam Lutka

Department: Department of Software Engineering

Supervisor: doc. RNDr. Tomáš Skopal, Ph.D., Department of Software Engineering

Abstract: A measurement done for every possible wireless data connection is expensive. It would be useful to reduce the cost. An application which could determine a quality of circumstances influencing possibility of a connection would help to do such a cost reduction. The thesis provides such an application which gives user information about meaningfulness of a real measurement in specific situation.

Keywords: spatial data, Fresnel zone, 3D graphics in a web browser

Obsah 1. Úvod / Předmluva................................................................................................................1 1.1. Požadavky na aplikaci.................................................................................................2 1.2. Podobná řešení............................................................................................................2 1.3. Struktura práce............................................................................................................3 2. Analýza problémů................................................................................................................4 2.1. Architektura aplikace...................................................................................................4 2.2. Použité technologie.....................................................................................................4 2.2.1. Uživatelské rozhraní............................................................................................4 2.2.2. Mezivrstva...........................................................................................................5 2.2.3. Datové úložiště....................................................................................................6 2.3. Reprezentace dat - souřadnicové systémy...................................................................6 2.4. Kontrola příslušnosti do Fresnelovy zóny...................................................................7 2.5. Organizace a vyhledávání v datech..............................................................................8 2.5.1. Konstrukce statického stromu indexu................................................................10 2.5.2. Dotazování s využitím indexu...........................................................................10 2.5.3. Postup pro výběr dat z databáze........................................................................12 3. Testování datového úložiště...............................................................................................13 3.1. Vytvoření databáze....................................................................................................14 3.2. Rozložení indexu.......................................................................................................14 3.3. Závislost času na vzdálenosti.....................................................................................15 3.4. Testování běžného provozu.......................................................................................15 3.4.1. Jeden dotazující se, bez vizualizace...................................................................16 3.4.2. Jeden dotazující se, s vizualizací.......................................................................17 3.4.3. Pět najednou dotazujících se, bez vizualizace....................................................18 3.4.4. Pět najednou dotazujících se, s vizualizací........................................................19 4. Uživatelská dokumentace..................................................................................................20 4.1. Uživatelské rozhraní..................................................................................................20 4.1.1. Zadání - levá část obrazovky.............................................................................20 4.1.2. Výsledek - pravá část obrazovky.......................................................................22 4.1.3. Postup pro zjištění realizovatelnosti datového spoje..........................................23 4.2. Mezivrsva..................................................................................................................23 4.3. Datové úložiště..........................................................................................................24 4.3.1. Generátor databáze............................................................................................24 4.3.2. Databázový server.............................................................................................25 5. Programátorská dokumentace............................................................................................26 5.1. Uživatelské rozhraní..................................................................................................26 5.2. Mezivrstva.................................................................................................................27 5.2.1. Implementované příkazy a formát jejich výstupu..............................................28 5.3. Datové úložiště..........................................................................................................28 5.3.1. Logické celky....................................................................................................29 5.3.2. Uložení dat........................................................................................................31 5.3.3. Komunikační protokol.......................................................................................32 6. Závěr.................................................................................................................................34 7. Reference...........................................................................................................................35

1. Úvod / Předmluva Pro poskytovatele bezdrátového Internetu je denním chlebem odpovídání si na otázku, zda lze mezi dvěma místy vytvořit bezdrátový datový spoj. Jde-li o území, které daný zaměstnanec nebo některý z kolegů, zná a z předchozích projektů má informace o realizovatelnosti spojů, může si na tuto otázku předběžně odpovědět na základě zkušeností a pak teprve, pokud má spoj dobrou šanci na to být realizován, případně poslat do terénu techniky, aby provedli měření. Nemá-li však dostatek informací, nezbývá než techniky poslat do terénu bez ohledu na to, zda je spoj reálný. Proto je logickým důsledkem snaha o co největší eliminaci zbytečných výjezdů, které jsou relativně drahé. Příkladem takové snahy zvýšit míru dostupných informací pro odpovědného zaměstnance mohou být fotografie pořizované do všech světových stran směrem od přípojného bodu. Ani při vysokém rozlišení ale neposkytují úplně nezkreslenou informaci o přímé viditelnosti a uvážení Fresnelovy zóny [1] (prostor, který signál potřebuje v okolí úsečky spojující koncové body pro šíření v plné kvalitě) zůstává zcela na zkušenostech toho, kdo se na ně dívá. Fotografie se nedají vůbec použít, když není zatím realizován ani jeden z bodů, protože v takovém případě neexistují a náklady na jejich pořízení se prakticky rovnají provedení měření. Protože podmínky pro signál se dají přesně popsat pomocí již zmiňované Fresnelovy zóny, mohla by se možnost vytvoření spoje kontrolovat programově. To by vyžadovalo popis prostředí, tedy terénu, zástavby a porostu. Takové datové sady existují, poskytují je zpravidla komerční firmy za úplatu. Digitální model povrchu České republiky také v současnosti vytváří Český úřad zeměměřičský a katastrální (dále ČÚZK) a měl by být hotový do konce roku 2015. I tato datová sada není k dispozici zdarma, ale již v současnosti úřad nabízí ukázková data [2], které lze využít pro vývoj a testování. Tato data mají dostatečnou kvalitu, protože jak ČÚZK píše, jsou přímo pro podobné účely sbírána (např. analýza viditelnosti, modelování šíření radiových vln, apod.). Nutné podmínky pro programovou kontrolu jsou splněny, ale je třeba si uvědomit, že stále nemůže plně nahradit samotné měření signálu. To už jen proto, že data s ohledem na způsob jejich sběru nemohou zohledňovat veškeré možnosti, jakými

-1-

jsou například dráty elektrického nebo jiného vedení, které tlumí signál, ale v digitálním modelu nejsou zaznamenány. Dalším příkladem jsou mosty a objekty podobného typu, které sice neomezují signál prochází-li pod nimi, ale v modelu je nelze odlišit od jiného terénu, tudíž jejich průchodnost nelze brát v úvahu. Proto si aplikace ani nemůže za cíl brát nahrazení měření. Jejím primárním účelem je poskytnout uživateli co nejvíce informací, aby se mohl kvalifikovaně, snadno a rychle rozhodnout, jakou šanci má spoj na realizaci, a případně přistoupit k měření.

1.1. Požadavky na aplikaci Z výše uvedeného vyplývají požadavky, které by měla aplikace splňovat: •

Uživatelské rozhraní realizované pomocí webového prohlížeče – zvýšení dostupnosti a snížení požadavků na jednotlivé stanice. Prohlížeč je dnes již standardem.

•

Koncové body zadávat do mapy – zlepšení orientace a zasazení do kontextu.

•

Prezentovat výsledek uživateli jako 3D vizualizaci terénu s Fresnelovou zónou – pomůže určit charakter případných překážek, a tím zjednoduší navrhování alternativních postupů.

•

Obsahovat matematický model pro určovaní příslušnosti bodů do Fresnelovy zóny – bude použit pro určení kolize zóny s terénem.

•

Efektivně pracovat s objemnými daty – dle velikosti území, pro které má aplikace být schopná odpovídat na dotazy, může mít báze dat velikost v řádu až desítek gigabytů. To si žádá efektivní způsob uložení a vyhledávání v nich. Také jejich centrální uložení, což koresponduje s požadavkem pro uživatelské rozhraní v prohlížeči.

•

Pracovat s daty pro Českou republiku

1.2. Podobná řešení Existují programy, které slouží k 3D vizualizaci modelů povrchu a řada z nich je i dostupná zdarma (např. DG Terrain Viewer [3]), ale disponuje-li program navíc nástroji

pro

testování

viditelnosti,

stává

se

zpravidla

placeným

(např.

DG Advanced [4]). Navíc se jedná o „těžké“ desktopové aplikace. Nepodařilo se nalézt žádnou aplikaci s podobnými vlastnostmi, jaké byly popsány výše.

-2-

1.3. Struktura práce Před samotným započetím implementace je třeba vyřešit některé otázky a navrhnout vhodná řešení problémů plynoucích z cílů aplikace, jakými jsou vhodná architektura aplikace či struktura dat a způsob práce s nimi. Tímto se zabývá první kapitola „Analýza problémů“. Druhá kapitola „Testování datového úložiště“ zkoumá, jaké výsledky vykazují navržená řešení po jejich implementování. Třetí kapitola „Uživatelská dokumentace“ řeší způsob používání aplikace. V návaznosti na to v další kapitole „Programátorská dokumentace“ lze získat hlubší znalosti o způsobu implementace. „Závěr“ přináší shrnutí úspěšnosti naplnění cílů práce a poskytuje návrhy na další vývoj.

-3-

2. Analýza problémů Před samotným zahájením implementace je třeba vyřešit otázky týkající se základních stavebních kamenů aplikace.

2.1. Architektura aplikace Aplikace se skládá ze tří hlavních částí a myšlenkově kopíruje klasickou trojici HTML + PHP + SQL: 1. uživatelské rozhraní 2. mezivrstva 3. datové úložiště Takto lze uživatelské rozhraní přesunout do prohlížeče, ty již v posledních verzích disponují podporou potřebných technologií pro práci s 3D grafikou, stejně jako je dostatečný výběr API pro práci s mapami. Avšak komunikace prohlížeče přímo se serverem pomocí vlastního protokolu není ještě uspokojivě implementována a plně využívána (zatím pouze koncept WebSocketu [5]). Na druhou stranu vlastní implementace HTTP na straně serveru by byla zbytečně náročná, proto se jeví dobrým řešením použití mezivrstvy využívající pro svůj běh již existujících řešení. Datové úložiště může být plnohodnotnou „těžkou“ aplikací, která se bude starat o práci s daty na požadované úrovni efektivity. Jak je vidět, uvedená architektura splňuje všechny vytyčené požadavky na aplikaci.

2.2. Použité technologie 2.2.1. Uživatelské rozhraní Má-li uživatelské rozhraní být uvnitř prohlížeče, jsou pro jeho realizaci přirozené technologie HTML5, CSS a Javascript. Pro tvorbu 3D grafiky zpracovávané grafickou kartou poslouží Javascriptové API WebGL [6], které již podporují poslední verze všech majoritních webových prohlížečů na trhu a nevyžaduje žádné zásuvné moduly či něco podobného, nanejvýše povolení v nastavení, jako je tomu například u prohlížeče Safari. -4-

Kvůli většímu programátorskému komfortu a snadnějšímu udržování zdrojového kódu je lepší pracovat na abstraktnější rovině a využít knihovnu, která sama používá WebGL. Takovýchto je k dispozici více, ale vzhledem k tomu, že knihovna Three.js [7] je distribuována pod licencí MIT, přímo počítá s vykreslováním systému bodů v prostoru (vhodné pro terén, který je tvořen množinou bodů) a jinak nevykazuje žádné nezanedbatelné nevýhody, nebylo nutné uvažovat o další konkurenci. To samé platí i pro jazyk Javascript. Problémy s odlišností jednotlivých prohlížečů, vyšší míru abstrakce, jednoduchost a snadnější udržitelnost kódu pomáhá docílit Javascriptový framework. I těch je relativně mnoho, ale svou popularitou a velikostí komunity získává navrch jQuery [8]. V České republice poskytují vhodné Javascriptové API pro práci s mapami společnosti Google a Seznam.cz a.s. Obě služby jsou srovnatelné, první jmenovaná může navíc nabídnout další informační hodnotu v podobě technologie StreetView (nasnímané okolí cest pomocí kamery), která již v současnosti pokrývá celou Českou republiku. Druhá disponuje kvalitnější databází objektů umístěných na mapu uživateli (např. obchody, apod.). Možnost prohlédnout si v některých případech reálnou scenérii je v našem případě přínosnější, proto byla zvolena služba Google Maps API [9].

2.2.2. Mezivrstva Hlavním úkolem mezivrstvy je realizovat překlad mezi protokolem databázového úložiště a HTTP, které se snadno používá Javascriptem. Vyplatí se zde využít již existujících implementací HTTP části a komunikaci s databázovým úložištěm realizovat v některém ze skriptovacích jazyků interpretovaných webovým serverem. Jazyk PHP je možné použít v drtivé většině prostředí a také poskytuje nástroje pro komunikaci přímo přes BSD socket, tedy neklade překážky pro implementaci libovolného komunikačního protokolu. Webový server, na kterém mezivrstva poběží, může zároveň zpřístupňovat uživatelské rozhraní přes Internet a dále tak usnadnit dostupnost celého řešení.

-5-

2.2.3. Datové úložiště Datové úložiště je stěžejní částí práce. Potřeba rychlé práce s velkými objemy dat a celkové možnosti mít kód co nejvíce pod kontrolou ukazuje na výhodnost použití jazyka C++. Nová norma C++11 [10] dělá z tohoto jazyka plně konkurenceschopný nástroj a není proto nutné vyměňovat rychlost za programátorský diskomfort. Uvážíme-li navíc, že se podpora překladačů v čase stále zlepšuje a již v současnosti je na dostatečné úrovni, aby se nejstěžejnější vlastnosti mohli bezproblémově využívat. Ač se předpokládá spíše nasazování na Unix-like systémech, úplné svázání zdrojových kódů s těmito systémy by nebylo žádoucí a hlavně zbytečné, když existují alternativy, jakou je například knihovna Boost [11], která je multiplatformní a proto se dá použít pro ty části kódu, které by jinak bylo nutné psát dané platformě na míru, jako je například mapování souborů do paměti.

2.3. Reprezentace dat - souřadnicové systémy Služba Google Maps API využívaná pro práci s mapami používá souřadnicový systém definovaný ve World Geodetic System 1984 (dále WGS84) [12]. Jedná se o kartézskou soustavu souřadnic se středem v těžišti Země a souřadnice se udávají pomocí zeměpisné šířky a délky, tedy jako sférické souřadnice. Pro určení třetí koordináty bodů se místo vzdálenosti od těžiště užívá nadmořská výška. S takto zadanými body by bylo značně komplikované pracovat, jednak kvůli sférické povaze souřadnic a také by bylo nutné brát v úvahu zakřivení Země. Řešením je podívat se na body více ploše, jako by byly zanesené do mapy, tedy do roviny a měly jen navíc informaci o své výšce. Úlohu, zda bod náleží do Fresnelovy zóny, tak bude možné řešit v klasickém eukleidovském prostoru s třemi dimenzemi bez nutnosti uvažovat zakřivení, a tím se výpočty zjednoduší a urychlí. Problém zobrazení bodů na povrchu Země do roviny již byl vyřešen jinými, nám proto pouze stačí vybrat vhodné zobrazení. Vzhledem k potřebě operovat pouze s daty na území České republiky nabízí se jako vhodný cílový systém souřadnic Jednotná trigonometrická síť katastrální (dále JTSK) [13]. Jak název napovídá, jedná se o souřadnicovou síť, která se používá v České republice v geodézii (např. pro katastrální mapy). Veškeré body v této síti mají obě souřadnice kladné, což dále -6-

zjednodušuje výpočty, a také mají jasně definované rozsahy hodnot, což umožní efektivnější ukládání dat. I data popisující reliéf poskytovaná ČÚZK využívají JTSK. Aplikace potřebuje jak převod z WGS84 do JTSK pro zpracování bodů, které uživatel zadal do mapy, tak obrácený převod pro vizualizaci výsledků na mapě. Na první z nich poskytuje návod, včetně zdrojových kódů v jazyce Pascal, Zdeněk Hrdina [14]. Tyto kódy pouze přepíšeme do jazyka C++, aby mohly být integrovány do datového úložiště. Dozvídáme se zde také, že transformace má pro naše účely dostatečnou přesnost, chybu maximálně 60 cm. Pro opačný převod poskytuje přímo zdrojové kódy v jazyce PHP Josef Zamrzla [15], ty využijeme jako knihovnu v mezivrstvě. Shrnutí

Aplikace s uživatelem komunikuje v souřadnicovém systému WGS84, vnitřní interpretace dat je v JTSK a převody mezi nimi jsou realizovány na základě již existujících zdrojových kódů.

2.4. Kontrola příslušnosti do Fresnelovy zóny Při určování příslušnosti bodu do Fresnelovy zóny vyjdeme ze vztahu pro výpočet jejího

poloměru

v určité

vzdálenosti

od

koncových

bodů,

jak

uvádí

SoftWrite LLC [16]. Označme určovaný bod jako P a koncové body Fresnelovy zóny jako S a T. Definujme bod A jako průsečík úsečky ST a přímky na ni kolmé procházející bodem P. Označme d1 vzdálenost A od S a d2 vzdálenost A od T. Poloměr 1. Fresnelovy zóny v bodě A (schématicky znázorňuje Ilustrace 1) vyjádříme z vlnové délky signálu (λ) vztahem (všechny jednotky jsou metry):

S

d1

A

√

λ⋅d 1⋅d 2 d 1+ d 2

d2 r P

Ilustrace 1: Fresnelova zóna (zdroj: upraveno http://en.wikipedia.org/wiki/File:FresnelSVG1.svg) -7-

T

Najdeme-li bod A, je určení příslušnosti bodu P do Fresnelovy zóny triviální porovnání jejich vzdáleností a jejího poloměru v A. Degenerované případy, kdy by bod A vůbec neležel mezi S a T, ošetříme kontrolou, zda jeho souřadnice náleží do příslušných intervalů daných koncovými body. Body S, T a P tvoří trojúhelník. Vypočítáme výšku PA, z Pythagorovi věty pak snadno d1 a d2. Bod A získáme posunutím bodu S podle směrnice úsečky ST o vzdálenost d1. Označme jako o polovinu obvodu trojúhelníku STP, pak výšku PA 2 √ o⋅( o−∣SP∣)⋅(o−∣PT∣)⋅(o−∣TS∣) ∣ST∣

vypočítáme pomocí Heronova vzorce:

2.5. Organizace a vyhledávání v datech Aplikace pro svůj běh potřebuje přístup k datům představujícím reliéf. Z charakteru těchto dat vyplývá, že se za běžného provozu nebudou vůbec měnit a případné aktualizace budou probíhat v relativně dlouhých cyklech, řádově měsíce či roky, dle schopnosti poskytovatele je dodávat. To znamená, že aplikace může jednorázově vybudovat statickou databázi s co možná nejoptimálnějšími vlastnostmi, protože všechna data má již k dispozici, a nadále z ní pouze rychle číst. Takové množství dat si pro efektivní vyhledávání v nich vyžaduje využití indexu. Avšak zde nevystačíme s indexy používanými v běžných databázových systémech, protože ty jsou zpravidla jednorozměrné, zatímco tato data jsou prostorová, tedy vícerozměrná. Jednotlivé záznamy jsou sice body v eukleidovském prostoru o třech dimenzích, ale nadmořská výška při vyhledávání nehraje roli. Nepředpokládá se, že by existovaly dva body se stejnými souřadnicemi X, Y a různou nadmořskou výškou. To vyplývá

ze

způsobu,

kterým se

data

pořizují.

Proto

lze

pracovat

s dvourozměrnými indexy. Data také mohou pokrývat velkou oblast, proto pro další zefektivnění vyhledávání by index měl být hierarchický. Z výše uvedeného nám vyvstávají jako vhodné stromové struktury pro realizaci indexu quadtree [17] a R-tree [18]. Quadtree má nesporně navrch co se jednoduchosti samotné struktury týče, ale pro nepravidelná data může vykazovat paměťovou neefektivitu, protože mnoho uzlů může zůstávat bez dat. Naproti tomu R-tree vyžaduje komplexnější logiku pro svou správu, nicméně existuje i statická verze, kde se strom z dat postaví a nadále slouží pouze k vyhledávání. V takovém případě komplikovanost aktualizace stromu odpadá, stavění je relativně jednoduché -8-

a těžiště problému se přesouvá do správného uskupení dat tak, aby byl strom co nejefektivnější. V závislosti na členitosti terénu obsahují data na některých místech velkou hustotu bodů a jinde mnohem menší. Také můžeme chtít některé části mapy do databáze neukládat, a tím bychom dále ještě více data činili nepravidelnými. Abychom v důsledku toho zbytečně neplýtvali místem, dosáhli větší obecnosti datového úložiště a vezmeme-li v úvahu statickou povahu databáze, zvolme jako strukturu pro index R-tree. Hlavním aspektem pro výkon indexu je uskupení dat uvnitř stromu. Volba křivky pokrývající prostor určuje, jak budou body ve stromě rozloženy. Příkladem takových křivek jsou Z-order [19], Hilbertova křivka [20], Peanova křivka [21] a další. Grafické vyjádření zmíněných prostor pokrývajících křivek ukazuje Ilustrace 2. Nelze určit, která z nich vykazuje nejlepší vlastnosti, protože je to vždy svázané s konkrétními daty. Všechny ale pro aplikaci, která není určená pro extrémní provoz, představují dostatečné zrychlení pro bezproblémový chod. Nicméně je vhodné využít v tomto případě modularitu a nesvázat návrh aplikace pouze s jednou z křivek.

Z-order

Hilbertova křivka

Peanova křivka

Ilustrace 2: Grafické vyjádření prostor pokrývajících křivek pro rovinu

-9-

2.5.1. Konstrukce statického stromu indexu Zvolme C počet prvků uzlu stromu. Postup při tvorbě R- tree pro index se pak skládá z následujících kroků: 1. Pro každý bod prostoru, který chceme uložit, vypočítáme jeho pořadí dle zvolené prostor pokrývající křivky. 2. Setřídíme body vzestupně podle tohoto pořadí. 3. Dokud zbývají nějaké body: 1. Vytvoříme nový uzel stromu. 2. Přiřadíme mu C bodů. 3. Modifikujeme obdélník, který uzel představuje, aby obsahoval projekce do roviny všech jemu přiřazených bodů. 4. Vložíme uzel do fronty pro úroveň 0. 4. Nastavíme l = 0. 5. Dokud ve frontě úrovně l je více než jeden uzel: 1. Dokud ve frontě úrovně l zbývají uzly: 1. Vytvoříme nový uzel stromu. 2. Přiřadíme mu C uzlů z úrovně l. 3. Modifikujeme obdélník, který uzel představuje, aby obsahoval obdélníky všech k němu přiřazených uzlů. 4. Vložíme uzel do fronty úrovně l+1. 2. Zvýšíme l o jedna.

2.5.2. Dotazování s využitím indexu Jak určit, zda bod náleží do Fresnelovy zóny, jsme rozebrali výše. Avšak provádět takto složitý výpočet pro veškerá data databáze by bylo časově neúnosné, proto zavádíme index, který nám pomůže vybrat pouze smysluplnou podmnožinu, na kterou již je postup aplikovatelný. Každý uzel stromu indexu je představován obdélníkem, který má dvě strany rovnoběžné s osou x a dvě s osou y. Tento obdélník omezuje oblast plochy, kde mohou ležet data v podstromu příslušného uzlu. Proto má smysl pokračovat v hledání jen u těch uzlů, jejichž obdélník a hledaná oblast (v našem případě typicky Fresnelova zóna) mají neprázdný průnik.

- 10 -

Kdybychom projekci Fresnelovy zóny obalili obdélníkem, aby určení průniku bylo co nejjednodušší a tím co nejrychlejší, mohlo by docházet k případům, kdy díky charakteru Fresnelovy zóny, kde její šířka je oproti délce relativně malá, by pokrývala jen malou část obdélníku a výhoda indexu v eliminaci nerelevantních dat bez jejich zdlouhavého procházení by tím byla potlačena. Vzhledem k tomu, že Fresnelova zóna je elipsoid, její projekcí do roviny získáme elipsu, kterou pak můžeme využívat pro určování neprázdnosti průniku. Takovouto elipsu získáme, vezmeme-li za její hlavní osu úsečku mezi projekcemi koncových bodů Fresnelovy zóny do roviny a její vedlejší poloosa bude mít délku rovnající se poloměru Fresnelovy zóny v jejím středu (výpočet poloměru viz kapitola 2.4). Ohniska definující elipsu získáme posunutím středu hlavní osy elipsy po a proti směrnici osy o vzdálenost d, danou vztahem (nechť a je délka hlavní poloosy a b je délka vedlejší poloosy): d =√ a 2−b 2 Průnik obdélníku a elipsy nastává, právě když platí některá z následujících podmínek: •

Obdélník obsahuje střed elipsy

•

Elipsa obsahuje některý z vrcholů obdélníku (nastává vždy, když nastává následující podmínka, ale lze využít k optimalizaci, díky jednoduššímu výpočtu)

•

Některá ze stran obdélníku protíná elipsu (můžeme zanedbat případ, kdy je strana tečnou, protože takový bod nehraje pro šíření signálu roli)

Bod leží uvnitř obdélníku, je-li jeho x-ová souřadnice větší nebo rovna než minimum z x-ových souřadnic vrcholů obdélníku a menší nebo rovna než maximum z těchto souřadnic. A zároveň to samé platí analogicky pro souřadnici y-ovou. Bod leží uvnitř elipsy, je-li součet jeho vzdáleností od ohnisek elipsy menší nebo roven délce hlavní osy elipsy. Úsečka s koncovými body E a F protíná elipsu s délkou hlavní poloosy a, délkou vedlejší poloosy b, jejíž střed je v počátku souřadnic a osy jsou rovnoběžné s osami souřadnic, leží-li alespoň jeden z vypočtených průsečíků na úsečce. To můžeme ověřit kontrolou příslušnosti jednotlivých souřadnic do daných intervalů. Označme v směrnici úsečky a nechť dolní indexy představují označení souřadnic vektorů či bodů. Pak se kandidáti na průsečíky, jejichž souřadnicemi jsou x1, y1 a x2, y2, - 11 -

vypočítají dle následujících vztahů, které vycházejí z rovnic elipsy a přímky: m=

vy vx

c=E y − E x⋅m

−a 2⋅m⋅c±a⋅b⋅√ a 2⋅m2+ b2−c 2 x 1,2= a 2⋅m2 +b 2

y 1=m⋅x 1 +c

y 2=m⋅x 2+ c

Protože elipsa v našem případě bude typicky otočena a také její střed nebude umístěn v počátku souřadnic, provedeme nejdříve posunutí a otočení koncových bodů úsečky, protože platí, že posunutá a otočená úsečka se protíná s elipsou se středem v počátku a osami rovnoběžnými s osami souřadnic, právě když se protíná původní úsečka s elipsou představující projekci Fresnelovy zóny (schématicky ukazuje Ilustrace 3). Posunutí realizujeme odečtením souřadnic středu elipsy od souřadnic bodu a otočením bodu A o úhel α, který se rovná otočení elipsy, vznikne bod B podle následujících vztahů: B x = Ax⋅cos (α)−A y⋅sin(α)

B y = A x⋅sin (α )+ A y⋅cos( α)

Ilustrace 3: Zachování průniku při otočení

2.5.3. Postup pro výběr dat z databáze 1. Přidáme kořen stromu indexu do zásobníku. 2. Dokud není zásobník prázdný: 1. Vyjmeme uzel ze zásobníku. 2. Je-li průnik obdélníku uzlu a elipsy Fresnelovy zóny pokračujeme rovnou na krok 1 bez provádění kroků 3 a 4.

prázdný

3. Není-li uzel list, přidáme jeho potomky do zásobníku. 4. Je-li uzel list, pro každý bod k němu patřící: 1. Neleží-li bod v elipse pokračujeme k dalšímu bodu bez provádění kroku 2. 2. Leží-li bod ve Fresnelově zóně vložíme jej mezi výsledky dotazu.

- 12 -

3. Testování datového úložiště Klíčovou a nejpodstatnější částí celé aplikace je datové úložiště, a proto je testování zaměřeno právě sem. Jeho fungování je přímo spjato s daty, která jsou ovšem zároveň cennější než aplikace samotná. Jsou však k dispozici zdarma vzorky dat, které například poskytuje ČÚZK. Tato data pokrývají území dvaceti kilometrů čtverečních a obsahují přibližně 2.7 miliónu bodů představujících reliéf povrchu. Protože má být aplikace schopna se potýkat s řádově větším množstvím záznamů, testovací data bylo nutné vygenerovat. Aby byl dodržen charakter dat, vycházeli jsme z dostupných dat, které jsme uvažovali jako základní jednotku a provedli 400 krát příslušnou transformaci, aby vznikl čtverec o straně 20 základních jednotek. Takto vygenerovaná data tedy pokrývají 8000 kilometrů čtverečních a obsahují více než 1.1 miliardy bodů, což je přibližně desetina území České republiky a představuje relevantní množství dat, protože v reálném provozu nebude třeba, aby databáze obsahovala data z území, kde není pravděpodobné či reálné vybudování datového spoje (např. rozsáhlé lesy apod.). Veškeré testy i generování databáze probíhalo ve virtuálním stroji s operačním systémem Ubuntu 12.04 LTS emulovaném pomocí programu Oracle VirtualBox 4.3.10. Virtuální stroj měl k dispozici 1 GB operační paměti a jedno jádro procesoru bez umělého omezení. VirtualBox byl spuštěný na skutečném stroji s operačním systémem Windows 7 Home Premium, procesorem Intel Core 2 Duo CPU 2.2 GHz, 3 GB operační paměti. Virtuální stroj na svých pevných discích využíval systém souborů Ext3 a skutečný stroj NTFS. Je-li datové úložiště přeloženo s direktivou preprocesoru DEBUG, ukládá si každý vykonaný příkaz společně s časem k tomu spotřebovaným do souboru timelog. Čas je zaznamenán v milisekundách a je měřen od dokončení rozdělení přijatého příkazu na jednotlivé části do předání všech výsledků ke zpracování. Čas potřebný na odeslání výsledku není započítán, protože se může značně lišit podle množství nalezených bodů. Pro testování byla jako maximální vzdálenost mezi koncovými body Fresnelovy zóny zvolena hodnota 20 km, protože delší bezdrátové datové spoje bývají velmi ojedinělé. - 13 -

3.1. Vytvoření databáze Databáze byla vytvořena z dat, vygenerovaných na základě vzorku poskytovaného zdarma ČÚZK, uložených ve 400 textových souborech, kde každý soubor měl velikost 88.9 MB a obsahoval 2772407 řádků, přičemž na každém řádku byly souřadnice bodu v souřadnicovém systému JTSK. Vytvořená databáze má velikost 8.4 GB a spotřebovaný čas na její vytvoření ukazuje výstup generátoru níže. Parsing Marking Sorting Building Summary

– – – – –

02:06:09 01:19:36 02:35:00 00:24:04 06:24:49

3.2. Rozložení indexu Jak ukazuje Ilustrace 4 vygenerovaná pomocí PHP skriptu utils/rects.php mezivrstvy, generátor databáze obdélníky, pokrývající povrch, a tím rozdělující data do uzlů stromu indexu, rozvrství tak, že většina uzlů, v jejichž podstromě se již data nacházet nemohou, je vyřazeno z hledání co nejdříve. I další úrovně stromu zachovávají podobné pokrytí (skriptu lze předat GET parametr level označující hladinu stromu, na kterou se omezí uvažované uzly stromu).

Ilustrace 4: Obdélníky představující potomky kořenového uzlu stromu indexu

- 14 -

3.3. Závislost času na vzdálenosti Závislost času vyhodnocení příkazu na vzdálenosti mezi koncovými body Fresnelovy zóny byla měřena pomocí skriptu utils/distancescan.php mezivrstvy, který naváže spojení s datovým úložištěm a pro každou vzdálenost z množiny {x ∈ [200,20000] | 200 dělí x} provede 100 krát dotaz pro náhodně zvolené body z oblasti, kterou databáze pokrývá, s danou vzdáleností.

3000 2500 2000 1500 1000 500 0

Median

Maximum

Minimum

Graf 1: Závislost času vyhodnocení dotazu [ms] na vzdálenosti koncových bodů [m] Záznamy v souboru timelog ukazují na jasnou závislost mezi vzdáleností a časem vyhodnocování, jak ukazuje Graf 1. Také je zde patrná velká závislost na rozložení indexu databáze potažmo hustotě bodů v oblasti, protože v ojedinělých případech může vyhodnocování trvat značně dlouho, řádově až sekundy a pro stejnou vzdálenost také velmi krátce, řádově desítky milisekund. V průměrném případě a daném prostředí se jeví úložiště plně vyhovující, protože čas potřebný na vyhodnocení příkazů se pohybuje řádově ve stovkách milisekund.

3.4. Testování běžného provozu Pro simulaci běžného provozu byl použit nástroj Apache HTTP server benchmarking

tool [22],

který

generoval

zprostředkovaně na datové úložiště.

- 15 -

požadavky

na

mezivrstvu

a ta

Byly modelovány čtyři situace, kde každá se skládala z 1000 požadavků na skript mezivrstvy

utils/randomfresnel.php,

v případě

dotazů

s vizualizací

s GET

parametrem visualize. Tento skript pokládá požadavek do datového úložiště pro Fresnelovu zónu mezi náhodnými body o maximální vzdálenosti 20 km.

3.4.1. Jeden dotazující se, bez vizualizace 2500 2000 1500 1000 500 0

Graf 2: Závislost času [ms] na vzdálenosti [m] – jeden dotazující se, bez vizualizace Graf 2 ukazuje data stejného charakteru, jaká byla v předchozí kapitole. Opět se zde projevuje závislost na vzdálenosti koncových bodů Fresnelovy zóny i význam struktury indexu a hustoty dat, protože se objevují lokální extrémy. Můžeme také odvodit, že volba jednotlivých spojení namísto mnoha příkazů v jednom spojení neovlivňuje dobu potřebnou pro zpracování příkazu. Connection Times (ms) min mean[+/-sd] median Total: 87 482 253.3 465

max 2399

Jak je vidět z výřezu z výstupu testovacího nástroje, doba zpracování na straně klienta prakticky kopíruje časy zpracování příkazů v datovém úložišti jen s malým navýšením.

- 16 -

3.4.2. Jeden dotazující se, s vizualizací 1600 1400 1200 1000 800 600 400 200 0

Graf 3: Závislost času [ms] na vzdálenosti [m] – jeden dotazující se, s vizualizací Graf 3 dokládá mírný nárůst potřebného času při vyžadování vizualizace, který můžeme vysvětlit jednak vyššími režijními náklady pro zařazení bodů do fronty k odeslání a také celkovým vyšším nárokem na výkon v důsledku potřeby odesílání nemalého množství dat do sítě. Connection Times (ms) min mean[+/-sd] median max Total: 90 4560 3383.9 4022 15778

Na straně klienta se však čas potřebný pro kompletní dokončení dotazu s vizualizací výrazně prodlouží, protože je nutné přenést mnohdy až několik stovek tisíc bodů. Může se jednat až o desítky sekund.

- 17 -

3.4.3. Pět najednou dotazujících se, bez vizualizace 4500 4000 3500 3000 2500 2000 1500 1000 500 0

Graf 4: Závislost času [ms] na vzdálenosti [m] – pět dotazujících se, bez vizualizace Jsou-li požadavky na datové úložiště kladeny paralelně, dojde k znatelnému zvýšení časů. To je způsobeno jednoduchou implementací synchronizace vláken datového úložiště, ke kterému se využívá pouze jednoho obřího zámku nad stromem dat. Connection Times (ms) min mean[+/-sd] median Total: 662 2149 595.3 2117

max 5423

Při 3. situaci se nejen komplikuje paralelními dotazy samotné vykonávání příkazů v rámci sdílení datových struktur datového úložiště, ale také komunikace a odesílání odpovědí, i když relativně krátkých. Časy tím znatelně narůstají.

- 18 -

3.4.4. Pět najednou dotazujících se, s vizualizací 6000 5000 4000 3000 2000 1000 0

Graf 5: Závislost času [ms] na vzdálenosti [m] – pět dotazujících se, s vizualizací Je-li

při

paralelním

dotazování

navíc

vyžadována

vizualizace,

dochází

k zvýrazňování extrémů, a to ve značné míře. Příčinnou je kombinace důvodů zmíněných ve výše popsaných situacích. Connection Times (ms) min mean[+/-sd] median Total: 396 27667 22912.3 22621

max 155335

V některých dotazech se mohou časy stávat prakticky nepoužitelné. Mimo jiné také překračují výchozí nastavení pro maximální dobu běhu PHP skriptu, a to může naznačovat nevhodnost takového používání datového úložiště.

- 19 -

4. Uživatelská dokumentace Uživatelská dokumentace může být určena až třem druhům uživatelů. V pořadí v jakém jdou podkapitoly: 1. Běžnému uživateli, který se setkává s uživatelským rozhraním a využívá jej k určení pravděpodobnosti realizovatelnosti spoje. 2. Pokročilému uživateli, který je schopen umístit mezivrstvu na vhodný hosting, a tím také zpřístupnit uživatelské rozhraní. 3. Administrátorovi, který uvede na serveru do chodu datové úložiště.

4.1. Uživatelské rozhraní S nejnovějšími verzemi webových prohlížečů Internet Explorer, Google Chrome a Mozilla Firefox aplikace pracuje zcela bezproblémově. Prohlížeč Safari na platformě Mac vyžaduje povolení WebGL v nastavení a prohlížeč Opera nedokáže zcela korektně vykreslit terén s Fresnelovou zónou. Jediným úkolem, který uživatel chce prostřednictvím uživatelského rozhraní řešit, je získání informaci o možnosti vybudovat bezdrátový datový spoj mezi dvěma místy. Toto má být maximálně jednoduché, takže vše probíhá pouze na jedné obrazovce, která je rozdělená logicky na levou část (Ilustrace 5) pro zadání parametrů spoje a pravou část (Ilustrace 6) pro prezentaci výsledků.

4.1.1. Zadání - levá část obrazovky Vstupem úlohy jsou čtyři parametry: 1. a 2. koncový bod Fresnelovy zóny, frekvence signálu a charakter dotazu. Koncové body se zadávají kliknutím do mapy, které vyvolá zobrazení panelu s předvyplněnou

polohou

bodu,

pomocí

zeměpisných

souřadnic

v podobě

desetinných čísel představujících stupně a nadmořské výšky v metrech, která je získaná jako funkce nadmořské výšky okolních bodů a dále zaokrouhlená nahoru a zvýšena o půl metru. Panel také obsahuje volbu Posunout do nejvyššího bodu v okolí, která způsobí, že se panel zavře a aplikace se pokusí přesunout bod na vhodnější místo (např. na hřeben střechy domu). Další možnosti, jak zavřít panel a potvrdit tak v něm obsažené hodnoty, jsou kliknutí na křížek v pravém horním rohu nebo stisk klávesy ENTER v poli pro zadávání nadmořské výšky. - 20 -

Ilustrace 5: Levá část uživatelského rozhraní - zadání parametrů spoje Teprve po zavření obou panelů se tlačítko Zjistit LoS, které slouží k provedení výpočtů a zobrazení výsledku, stane aktivním. Vedle tohoto tlačítka se nachází pole pro zadání frekvence signálu jako desetinné číslo v gigahertzech a zaškrtávací políčko Vizualizovat, které určuje, zda je požadována 3D vizualizace výsledku. Vizualizace poskytne uživateli více informací, ale také může značně prodloužit dobu načítání v závislosti na délce Fresnelovy zóny a počtu bodů v oblasti. Pohyb po mapě usnadní textové pole vedle tlačítka Hledat, do kterého lze zadávat adresy i klíčová slova (např. „hlavni nadrazi praha“). Chybně zadané body lze opravit jejich označením pomocí kliknutí na ukazatel jejich polohy (žlutá či fialová ikona) a následným udáním nové polohy pomocí kliknutí na nové místo na mapě. Označený bod je zvýrazněn pomocí modrého kroužku pod jeho ukazatelem. Pomocí dvojitého kliknutí na ukazatel, lze znovu otevřít panel vlastností příslušného bodu.

- 21 -

4.1.2. Výsledek - pravá část obrazovky

Ilustrace 6: Pravá část uživatelského rozhraní - prezentace výsledků dotazu Část obrazovky prezentující výsledky se dělí na dvě podčásti. Horní obsahující textové vyjádření dat s nejdůležitějším údajem Oblast průchozí bez překážek. Je to číslo vyjadřující kolik procent svého nynějšího objemu by musela Fresnelova zóna mít, aby se v ní nenacházel žádný z nalezených bodů. Přičemž body představují povrch, proto předpokládáme, že se pod nimi nachází hmota (až na výjimky např. mosty, ale takové musíme zanedbat), což je zohledněno v kolizním modelu. Také se zde nachází volba Navrhnout korekci vedoucí na panel, kde může aplikace navrhnout zvýšení koncových bodů tak, aby byla Fresnelova zóna plně průchodná, což má simulovat připevnění antén na delší tyč. To nelze dělat libovolně, proto je korekce shora omezená výškou 5 metrů.

- 22 -

Dolní podčást, je-li zaškrtnuta volba Vizualizovat, vizualizuje Fresnelovu zónu (modře), koncové body (žlutě a fialově, analogicky k ukazatelům na mapě), body mimo zónu (zeleně) a body uvnitř zóny nebo ji protínající (červeně). Tyto prvky tvoří 3D model, kterým jde manipulovat tažením myši nebo pomocí čtyř tlačítek se šipkami v krajích vizualizační oblasti, přičemž horní a dolní tlačítko posouvají s modelem po ose představující výšku bodů a levé a pravé tlačítko po směrnici úsečky mezi koncovými body. V levém horním rohu vizualizační oblasti se nachází volba reset, která vrátí 3D model do výchozího zobrazení.

4.1.3. Postup pro zjištění realizovatelnosti datového spoje 1. Pomocí zadání adresy do vyhledávacího pole mapy najdeme první bod. 2. Klikneme na příslušné místo na střeše stavby, objeví se panel s vlastnostmi bodu. 3. Případně upravíme výšku bodu nebo necháme aplikaci jej posunout do nejvyššího bodu v okolí. 4. Zavřeme panel s vlastnostmi bodu. 5. Postup opakujeme pro druhý koncový bod. 6. Pomocí zaškrtávacího políčka určíme, zda máme zájem o vizualizaci výsledku. 7. Zadáme frekvenci signálu. 8. Necháme aplikaci spoj vyhodnotit kliknutím na tlačítko Zjistit LoS. 9. Po vyhodnocení v pravé části zjistíme průchodnost Fresnelovy zóny, případně můžeme v 3D modelu získat bližší představu o charakteru překážek.

4.2. Mezivrsva Mezivrstvu stačí umístit na webový server podporující skriptovací jazyk PHP alespoň verze 5.3 s povolenými běžnými funkcemi pro práci s řetězci, poli a s funkcemi fread, fwrite a fsockopen. Služba poskytující mapové rozhraní pro svůj chod vyžaduje vygenerování klíče svázaného s doménou, na které bude webová stránka využívající toto rozhraní umístěna. Klíč lze vygenerovat pomocí Google APIs Console [23] a následně je nutné jej vložit do souboru index.hml do URL adresy v atributu src elementu script označeného komentářem „GOOGLE MAPS API“ jako hodnotu GET parametru key.

- 23 -

4.3. Datové úložiště Datové úložiště je realizováno jako program napsaný v jazyce C++ a využívá vlastnosti jazyka, které přinesla norma C++11, jakými jsou rvalue reference nebo lambda funkce. S tímto je třeba při překladu počítat, protože překladače stále ještě nezvládají celou normu. Nicméně s běžnými překladači v aktuální verzi jde kód přeložit bez problémů. Protože se předpokládá nasazení na Unix-like systémech, je přiložen Makefile, který překlad zajistí. Nastaví-li se při překladu direktiva preprocesoru DEBUG, bude datové úložiště ukládat každý obdržený dotaz společně s množstvím času spotřebovaným na jeho vykonání do souboru timelog nacházejícím se v témže adresáři jako spustitelný soubor datového úložiště (obsah souboru je při každém spuštění smazán). Direktiva RTREE_STATS způsobí, že datové úložiště po každém příkazu vypíše na standardní výstup počty navštívených uzlů indexu a uvažovaných bodů. Výsledkem překladu je jediný spustitelný soubor, který může pracovat ve dvou režimech dle předložených argumentů:

4.3.1. Generátor databáze usage: ...

Po zadání dvou a více argumentů pracuje úložiště v režimu generování databáze, kde první argument udává jméno a cestu k hlavnímu souboru tvořené databáze a bude také sloužit jako prefix všech dalších vytvořených souborů, kterými jsou soubory s daty a indexem. Proto dává smysl zadávat tuto cestu jako název souboru v prázdném adresáři, který pak bude logicky ohraničovat celou databázi. Ostatní argumenty jsou cesty k souborům obsahujícím data, z kterých bude databáze budována. Vstupní data musí být ve formátu -y, -x, z, kde jednotlivé položky jsou odděleny bílými znaky a představují souřadnice v systému JTSK. Po spuštění se program dotáže na maximální velikost datového souboru, protože množství dat může být značné a nemuselo by být možné je všechny uložit do jediného souboru. Při zadávání velikosti lze na konci vstupu využít znaku g (gigabyty), m (megabyty) nebo k (kilobyty) pro vyjádření násobných jednotek, přičemž není brána v úvahu velikost písmena. - 24 -

Následně již program buduje databázi bez nutnosti zásahu uživatele a o svém stavu informuje hláškami v důležitých bodech tvorby. Pro svou činnost vyžaduje generátor místo na pevném disku přibližně rovné šestnáctinásobku počtu budoucích záznamů databáze plus maximum z 0.5 GB a maximální velikosti datového souboru.

4.3.2. Databázový server usage:

Při uvedení jediného argumentu pracuje program v režimu databázového serveru a argumentem je cesta k hlavnímu souboru databáze (cesta zadaná při generování databáze). Okamžitě po spuštění se zablokuje a poslouchá na portu 50000. Pro spuštění na pozadí je nutné využít prostředků systému, jakým je například pro Unix-like systémy program nohup [24] v kombinaci se spuštěním úlohy na pozadí. # nohup ./pdb &

- 25 -

5. Programátorská dokumentace Kapitola popisuje hlavní myšlenky aplikace, které se nedají přímo vyčíst z kódu nebo jen zbytečně obtížně. Toto lze dělat pro jednotlivé části aplikace zvlášť, protože jsou teoreticky nezávislé. A také rozebírá princip komunikace mezi nimi.

5.1. Uživatelské rozhraní Celé uživatelské rozhraní je realizováno pomocí jediné obrazovky, která je obsažena v HTML souboru, který obsahuje pouze běžné prvky HTML dokumentu. Veškerá funkčnost je ukryta v souborech js/main.js a js/visual.js, kde první obstarává celkovou interakci s uživatelem, zejména pak práci s mapou a komunikaci se serverem prostřednictvím technologie AJAX, a druhý zprostředkovává objekt sloužící k vizualizaci reliéfu. Uživatelské rozhraní posílá požadavky na mezivrstvu metodou POST, což je realizováno jednoduchým voláním metody frameworku jQuery. Odpověď očekává v textové podobě ve formátu JSON [25], kde celá odpověď je jediný objekt, který má povinné datové položky status, který je v případě úspěchu akce prázdný řetězec, chybová hláška jinak, a result nesoucí samotná data. Vizualizaci reliéfu a Fresnelovy zóny zajišťuje objekt Visual, který pro vykreslování využívá knihovnu Three.js a pro ovládání manipulace s 3D modelem již hotové řešení umístěné v souboru js/orbitcontrols.js, čímž knihovnu logicky odděluje a stává se rozhraním, které využívá uživatelské rozhraní. Zároveň představuje kontejner bodů reliéfu, kde každý bod je uložen spolu s jeho barvou. Následně jsou body touto barvou vykresleny pomocí komponenty ParticleSystem knihovny Three.js. Objektu Visual je také možné nastavit koncové body Fresnelovy zóny, ta je poté vykreslena po jednotlivých částech pomocí CylinderGeometry (komolých kuželů). Počet částí a tím přesnost vizualizace

Fresnelovy zóny udává konstanta

Visual.FRESNEL_RESOLUTION. Další funkčností objektu je kontrola průchodnosti Fresnelovy zóny, tedy zda přidané body leží mimo ni. Toho se využívá u návrhu korekce výšky koncových bodů zóny, která je prováděna iterativně (koncové body se postupně zvyšují a kontroluje se - 26 -

průchodnost). Vezmeme-li v úvahu, že se celý proces provádí na klientské straně v prohlížeči, tedy výkonu je dostatek, a že posun je omezen shora poměrně malou konstantou, je iterativní přístup kvůli jednoduchosti implementace lepší než složitější implementace přesného výpočtu.

5.2. Mezivrstva Mezivrstva je současně klientem (pro datové úložiště) i serverem (pro uživatelské rozhraní). Pro komunikaci s datovým úložištěm obsahuje mezivrstva sadu tříd uložených v adresáři classes, které představují komunikační rozhraní a dají se využít v libovolném PHP projektu. Stačí pomocí funkce include nebo jí podobné nahrát soubor classes/pointsdatabase.php, který obsahuje třídu PointsDatabase ve jmenném prostoru PointsDB. Zbylé soubory s třídami jsou nahrány dle potřeby automaticky. Objekt PointsDatabase ve svém konstruktoru přijímá hostitelské jméno a port datového úložiště, které se využijí pro navázání spojení, až bude třeba. Dále metodu disconnect pro ukončení spojení a metody fresnel a sphere, které představují dotazy do úložiště na body v dané oblasti a vracejí některého z potomků třídy QueryResult, který nese informace o daném dotazu, jakými můžou například být koncové body Fresnelovy zóny. Jednotlivé výsledky dotazu jsou dostupné jako návratová hodnota metody fetch, která vrací vždy následující výsledek a nakonec vrátí boolovské false. Objekt také obsahuje variantu bez vizualizace nopointsFresnel, která vrací instanci třídy NopointsFresnelResult, v které jsou agregovány výsledky. Mezivrstva pracuje s konceptem příkazů. Klient posílá požadavky na URL query.php?cmd=PRIKAZ, kde PRIKAZ je jméno některého ze souborů uložených v adresáři cmds bez koncového .php složený jen z malých a velkých písmen anglické abecedy. Mezivrstva připraví prostředí, nahraje třídy pro komunikaci s datovým úložištěm, případně ošetří vzniklé výjimky a zašle je ve správném formátu klientovi. V samotných souborech příkazů už probíhá jen požadovaná činnost a očekává se, že její výsledek bude odeslán klientovi prostřednictvím třídy Output, která připraví požadovaný formát a umožní výsledky odesílat průběžně, a tím se odbourá potřeba velkého množství paměti na udržování všech výsledků.

- 27 -

5.2.1. Implementované příkazy a formát jejich výstupu •

altitude: Očekává POST parametry lat a lng udávající souřadnice bodu ve WGS84 a výstupem je desetinné číslo představující nadmořskou výšku daného bodu v metrech. Pro zjištění výšky je využita Metoda vážené inverzní vzdálenosti [26].

•

fresnel: Očekává POST parametry p1-lat, p1-lng a p1-alt udávající po řadě zeměpisnou šířku, zeměpisnou délku a nadmořskou výšku v metrech prvního koncového bodu. Analogicky také p2-lat, p2-lng a p2-alt pro druhý koncový bod. Výstupem je pole obsahující na první pozici pole výsledků, na druhé první koncový bod Fresnelovy zóny a na třetí druhý koncový bod Fresnelovy zóny. Výsledky mají tvar pole s bodem na první pozici a procentuálním vyjádřením průchodnosti Fresnelovy zóny na druhé. Body mají formát pole, v kterém jsou prvky po řadě x-ová souřadnice, y-ová souřadnice a nadmořská výška, vše v JTSK.

•

localmax: Očekává POST parametry lat a lng udávající souřadnice bodu ve WGS84 a výstupem je pole, v kterém jsou prvky po řadě zeměpisná šířka, zeměpisná délka a nadmořská výška v metrech také ve WGS84. Příkaz se snaží prohledáváním do hloubky nalézt lokální maximum. Nemusí dávat nejlepší výsledky, ale pro například posunutí koncového bodu na hřeben střechy je zcela postačující.

5.3. Datové úložiště Zdrojový kód datového úložiště psaný v jazyce C++ maximálně využívá objektově orientované programování a k dosažení ještě větší rozšiřitelnosti napomáhají také šablony. Tedy zdrojové kódy jsou sadou tříd, které se případně vzájemně využívají a veškerý mimo třídy ležící kód je soustředěn pouze do souboru main.cpp, kde se také nachází metoda main. Zde se pouze objekty přímočaře používají. Jednotlivé třídy jsou logicky rozděleny do jmenných prostorů: •

geom – třídy mající vztah k entitám geometrické povahy (např. místo, bod, ale i třída pro převod souřadnicových systémů)

•

index – třídy představující r-tree, sloužící k vyhledávání dat

•

net – třídy pro komunikaci s klientem

•

storage – třídy zprostředkovávající přístup k datům

- 28 -

V těchto jmenných prostorech některé třídy pouze slouží k realizaci cílů jiných a vznikají tak funkční bloky, které jsou postupně sestavovány do větších (to již i mezi jmennými prostory) až po ty, které realizují přímo požadované rysy aplikace.

5.3.1. Logické celky •

výsledek dotazu pro bod – jde o bod v prostoru doplněný o informace týkající se jeho polohy ve vztahu k určité dotazované oblasti. Je realizován třídou index::area_result, která využívá třídu geom::point.

•

dotazovaná oblast – entita poskytující metody pro určení, zda k ní bod přísluší. Reprezentována abstraktní třídou geom::area a jejími potomky geom::fresnel_zone a geom::sphere. Využívá třídu geom::rectangle jako vstupní parametr metody určující, zda průsečík obdélníku s oblastí je neprázdný, a výsledek dotazu pro bod jako vstupně/výstupní parametr.

•

rovinu pokrývající křivky – třídy implementující metodu get_index, která vrací pořadí daného místa v určitém obdélníku. Tedy využívá jako parametrů třídy geom::place a geom::rectangle. Jsou umístěny ve jmenném prostoru storage::linearizers.

•

parsery – třídy implementující metodu parse_point, která dokáže ze vstupního proudu přečíst bod. Tedy využívá jako výstupní parametr třídu geom::point. Jsou umístěny ve jmenném prostoru storage::parsers.

•

úložiště – představuje zdroj dat. Stará se o správné mapování souborů apod. Reprezentuje jej třída storage::storage. Poskytuje datové a indexové bloky, které představují kontejner záznamů pouze pro čtení a jsou reprezentovány třídou storage::block.

•

soubor souborů – virtuální soubor dovolující ukládání záznamů bez nutnosti starat se o skutečné uložení do fyzických souborů. Je realizován třídou storage::multifile.

•

generátor úložiště – jeho úkolem je vybudovat úložiště a index na základě poskytnutých cest k souborům s daty. Je realizován třídou storage::storage_creater, která na základě poskytnuté rovinu pokrývající křivky, parseru a s využitím souboru souborů úložiště vytvoří.

•

strom indexu – představuje index dat. Zprostředkovává jej třída index::rtree, která poskytuje metodu jejíž vstupní parametry jsou dotazovaná oblast a reference na některého z potomků třídy index::query_result, která metodou push přijímá jednotlivé výsledky dotazu pro bod. Ke čtení dat využívá úložiště. Pro realizaci stromu používá tříd index::inner_node (vnitřní uzly), index::leaf_node (listy) a index::null_node (neexistující uzly, v indexu pouze zajišťují pevnou velikost bloku). - 29 -

•

konvertor do binární podoby – třída implementující metodu convert, která pro instanci datového typu vrátí jeho interpretaci v podobě pole bytů. Nutně podporované typy jsou double, char, std::uint32_t, geom::place, geom::point, std::string, geom::rectangle a index::area_result. Je realizován pomocí třídy net::binary_converter.

•

zprostředkovatel výsledku – třída implementující metodu write, která vstupní parametr s využitím konvertoru do binární podoby zařadí do fronty pro odeslání přes daný socket klientovi. Stará se o veškerou komunikaci směrem ke klientovi po přijetí dotazu od něj. Je realizován pomocí třídy net::socket_writer.

•

vykonavatel příkazů – třída implementující metodu call, která vyhodnotí příkaz s danými argumenty a výsledek s využitím poskytnutého zprostředkovatele výsledku odešle klientovi. Je realizován pomocí třídy net::command_provider, která vyhodnocuje příkazy dotazující se na data s využitím stromu indexu.

•

server – zprostředkovává navázání komunikace a obsluhu klientů prostřednictvím vykonavatele příkazů. Zajišťuje také paralelní obsluhování klientů. Je realizován pomocí třídy net::server.

Pro dosažení požadovaných rysů datového úložiště pak pouze na základě argumentů předaných

z operačního

systému

přímočaře

využijeme

generátor úložiště

(argumenty obsahují cesty souborů s daty) nebo server (je-li argumentem umístění dat). Vztahy mezi celky z výše uvedeného seznamu schématicky zachycuje Ilustrace 7.

server

Využívající

generátor úložiště

vykonavatel příkazů

zprostředkovatel výsledku

Využívaný

strom indexu

soubor souborů

parsery

rovinu pokrývající křivky konvertor do binární podoby

dotazovaná oblast

úložiště

výsledek dotazu pro bod

Ilustrace 7: Vztahy mezi logickými celky zdrojového kódu datového úložiště

- 30 -

5.3.2. Uložení dat Úložiště využívá pro perzistentní skladování dat následující soubory: •

hlavní soubor – textový soubor jednoznačně identifikující databázi (cesta ke každému souboru databáze obsahuje cestu k hlavnímu souboru jako předponu) obsahující na každém řádku informace o uložených datech. Po řadě: počet souborů s daty, počet datových bloků v souboru, počet záznamů v datovém bloku a počet záznamů v bloku indexu.

•

soubor indexu – binární soubor s příponou .index obsahující strom indexu, tedy sérii uložených tříd node_data.

•

datové soubory – binární soubory s příponou .N, kde N je nezáporné celé číslo, obsahující samotná data, tedy sérii uložených tříd point_data.

Třída place_data

Třída place_data má za své datové položky pouze pole šesti bytů. V bytech s indexy 0, 1 a 2 je uloženo číslo představující x-ovou souřadnici a v bytech s indexy 3, 4 a 5 číslo představující y-ovou souřadnici. Obě čísla jsou ve formátu little-endian a protože představují souřadnice v systému JTSK, mají předem známou doménu hodnot, která se vejde do 3 bytů, ale je nutné provést posun a snížit přesnost na jediné desetinné místo. Transformace pro x-ovou složku je tedy (x – 900000) * 10 a pro y-ovou složku (y – 400000) * 10. Takto transformovaná čísla se zaokrouhlí a jsou vložena do těla třídy, kterou pak lze uložit na disk. Třída point_data

Třída point_data využívá třídu place_data a přidává další dva byty představující nadmořskou výšku. Ta je uložena opět ve formátu little-endian, vynásobena deseti pro zahrnutí jednoho desetinného místa a zaokrouhlena. Třída node_data

Třída node_data obsahuje 4 bytové číslo, v jehož nejvyšším bitu je jednička nejedná-li se o list stromu. Zbylé bity představují ID buď datového nebo indexového bloku. Toto číslo je v paměti uloženo závisle na platformě, což zjednodušuje načítání, ale činí soubor indexu svázaný s platformou, na které byl vytvořen. Dále třída obsahuje dvě instance třídy place_data. První představuje levý horní roh obdélníku, v kterém jsou umístěny veškeré body v podstromu, a druhá představuje pravý dolní roh. - 31 -

5.3.3. Komunikační protokol Server po přijetí příchozího spojení odešle zpět řetězec „HI“ a čeká na dotaz od klienta, který je textovým řetězcem ukončeným znakem '\n'. Tento řetězec je rozdělen na části (oddělovačem částí jsou bílé znaky), kde první představuje název příkazu a další jsou jeho argumenty. Po vyhodnocení příkazu server odpoví daty v binární podobě a čeká na další příkaz. Komunikace končí odpojením klienta nebo pokud je neaktivní po dobu překračující 60 sekund. Formát dat odpovědi záleží na konkrétním příkazu, ale skládá se z níže popsaných datových primitiv. Data jsou vždy ukončena posloupností 48 jedniček. Formát datových primitiv:

•

místo v rovině – stejně jako u uložení dat se využívá třída place_data.

•

bod v prostoru – stejně jako u uložení dat se využívá třída point_data.

•

desetinné číslo – předpokládá nezáporné číslo. 2 bytové číslo představující 4 místa desetinné části čísla + 4 bytové číslo představující celou část. Čísla jsou ukládána jako little-endian.

•

obdélník – místo v rovině představující levý horní roh + místo v rovině představující pravý dolní roh

•

výsledek dotazu oblasti – 1 byte jehož nejvyšší bit určuje, zda bod leží přímo v tělese dotazu a ostatní představují číslo, udávající procentuální vyjádření, jak moc bod zasahuje do tělesa. Pro bod mimo těleso má vždy hodnotu 100. Plus bod v prostoru.

- 32 -

Implementované příkazy a jejich argumenty:

•

fresnel formát x1 y1 z1 x2 y2 z2 frekvence[ typ] Vrací koncové body (2× bod v prostoru) následované, v případě nepřítomnosti typu, množinou bodů v oblasti Fresnelovy zóny (n× výsledek dotazu oblasti). V případě, že argument typ je „nopoints“, následuje místo jednotlivých výsledků jeden byte představující procentuálně vyjádřenou průchodnost a dvě 4 bytové čísla ve formátu little-endien. První číslo představuje počet bodů uvnitř a druhé představuje počet bodů mimo. formát – řetězec „jtsk“ nebo „wgs84“. Určuje souřadnicový systém následujících souřadnic. x1, y1, z1, x2, y2, z2 – desetinná čísla s tečkou jako oddělovačem. Souřadnice koncových bodů Fresnelovy zóny. frekvence – desetinné číslo s tečkou jako oddělovačem. Frekvence signálu v GHz. typ – může nabývat pouze hodnotu „nopoints“ nebo být nepřítomen.

•

sphere formát x y z r[ typ] Vrací střed koule (bod v prostoru) a její poloměr (desetinné číslo) následované, v případě nepřítomnosti typu, množinou bodů v oblasti koule (n× výsledek dotazu oblasti). V případě, že argument typ je „nopoints“, následuje místo jednotlivých výsledků jeden byte představující procentuálně vyjádřenou průchodnost a dvě 4 bytové čísla ve formátu little-endien. První představující počet bodů uvnitř a druhé představující počet bodů mimo. formát – řetězec „jtsk“ nebo „wgs84“. Určuje souřadnicový systém následujících souřadnic. x, y, z – desetinná čísla s tečkou jako oddělovačem. Souřadnice středu koule. r – desetinné číslo s tečkou jako oddělovačem. Poloměr koule. typ – může nabývat pouze hodnotu „nopoints“ nebo být nepřítomen.

•

echo … Přijímá libovolné parametry a vrací je na výstup oddělené mezerou. Pro testovací účely.

•

rects[ hloubka] Vrací množinu obdélníků (n× obdélník), které tvoří jednotlivé uzly indexu dat. hloubka – nepovinný parametr určující s uzly z jaké hloubky stromu se pracuje. Není-li přítomen, berou se všechny.

- 33 -

6. Závěr Výsledkem práce je funkční aplikace splňující vytyčené cíle otestovaná na datech vygenerovaných

z dat

poskytovaných

ČÚZK.

Porovnáním

vizualizace

dat

s leteckými snímky, které jsou součástí map, se jeví odpovědi na dotazy korektní a smysluplné. Aplikace při testech vykázala dobrou průměrnou rychlost v prostředí bez konkurenčních dotazů a dostatečnou v prostředí konkurenčním bez potřeby vizualizovat reliéf, avšak s potřebou vizualizace kombinovanou s paralelními dotazy se již časy zpracování stávají v praxi nepoužitelné. Vzhledem k zamýšlenému použití pro omezený okruh zaměstnanců, kde by ke konkurenčním dotazům mělo docházet jen zřídka a v malé míře konkurence, splňuje aplikace požadavky. V současnosti začíná běžet její testování přímo uživateli, pro které je určena. Místo pro další vylepšení použitelnosti je v rozšíření datového úložiště o konfiguraci generování databáze (např. volba parseru či prostor vyplňující křivky), ale také serveru (např. volba portu, na kterém poslouchá). Tyto vlastnosti se nyní dají měnit triviální úpravou kódu, ale vyžadují nový překlad. Slabinou může být relativně velká svázanost kódu datového úložiště s požadavkem na obsluhu dat představujících reliéf pouze České republiky. Díky modularitě je možné jednoduše vyextrahovat z aplikace potřebné části a začlenit je například do již existujícího informačního systému. Také samotné datové úložiště skrývá potenciál, který se dá dále rozvíjet pouhým rozšířením baterie tříd pro dotazování na jiné oblasti a rozšíření příkazů, které je server schopen obsloužit.

- 34 -

7. Reference [1] Fresnel zone. [online]. [cit. 2014-03-31]. Dostupné z: http://www.its.bldrdoc.gov/fs-1037/dir-016/_2398.htm [2] Digitální model povrchu České republiky 1. generace (DMP 1G). [online]. [cit. 2014-03-31]. Dostupné z: http://geoportal.cuzk.cz/%28S %28ldlujhiexwqgyobh5m04qjb2%29%29/Default.aspx? lng=CZ&mode=TextMeta&side=vyskopis&metadataID=CZ-CUZK-DMP1GV&mapid=8&menu=303 [3] DG Terrain Viewer. [online]. [cit. 2014-03-31]. Dostupné z: http://www.dgadv.com/dgtv/ [4] DG Advanced. [online]. [cit. 2014-03-31]. Dostupné z: http://www.dgadv.com/dgtvlos/ [5] WebSocket. [online]. [cit. 2014-03-31]. Dostupné z: http://www.websocket.org/ [6] WebGL. [online]. [cit. 2014-03-31]. Dostupné z: http://www.khronos.org/registry/webgl/specs/1.0/ [7] Three.js. [online]. [cit. 2014-03-31]. Dostupné z: http://threejs.org/ [8] jQuery. [online]. [cit. 2014-03-31]. Dostupné z: http://jquery.com/ [9] Google Maps Javascript API v3. [online]. [cit. 2014-03-31]. Dostupné z: https://developers.google.com/maps/documentation/javascript/ [10] ISO/IEC 14882:2011. [online]. [cit. 2014-03-31]. Dostupné z: http://www.iso.org/iso/iso_catalogue/catalogue_ics/catalogue_detail_ics.htm? ics1=35&ics2=60&ics3=&csnumber=50372 [11] Boost C++ Libraries. [online]. [cit. 2014-03-31]. Dostupné z: http://www.boost.org/ [12] World Geodetic System 1984. [online]. [cit. 2014-03-31]. Dostupné z: http://earth-info.nga.mil/GandG/publications/tr8350.2/tr8350_2.html [13] ČADA, Václav. Souřadnicové výpočty v rovině [online]. Plzeň: Západočeská univerzita, [cit. 2013-04-02]. Kapitola Základní vlastnosti. Dostupné z: http://gis.zcu.cz/studium/gen1/html/ch07.html [14] HRDINA, Zdeněk. Transformace souřadnic ze systému WGS-84 do systému S-JTSK. Praha, 1997. České vysoké učení technické v Praze. [15] ZAMRZLA, Josef. JTSK_CONVERTER. [online]. [cit. 2014-03-31]. Dostupné z: https://github.com/josefzamrzla/JTSK_Converter [16] Fresnel Zone Clearance. [online]. [cit. 2014-03-31]. Dostupné z: http://www.softwright.com/faq/engineering/Fresnel%20Zone %20Clearance.html - 35 -

[17] Raphael Finkel and J.L. Bentley (1974). "Quad Trees: A Data Structure for Retrieval on Composite Keys". Acta Informatica 4 (1): 1–9. doi:10.1007/BF00288933. [18] Guttman, A. (1984). "R-Trees: A Dynamic Index Structure for Spatial Searching". Proceedings of the 1984 ACM SIGMOD international conference on Management of data - SIGMOD '84. p. 47. doi:10.1145/602259.602266. ISBN 0897911288. [19] Morton, G. M. (1966), A computer Oriented Geodetic Data Base; and a New Technique in File Sequencing, Technical Report, Ottawa, Canada: IBM Ltd. [20] D. Hilbert: Über die stetige Abbildung einer Linie auf ein Flächenstück. Mathematische Annalen 38 (1891), 459–460. [21] Peano, G. (1890), "Sur une courbe, qui remplit toute une aire plane", Mathematische Annalen 36 (1): 157–160, doi:10.1007/BF01199438. [22] ab - Apache HTTP server benchmarking tool. [online]. [cit. 2014-05-01]. Dostupné z: http://httpd.apache.org/docs/2.2/programs/ab.html [23] Google APIs Console. [online]. [cit. 2014-06-09]. Dostupné z: https://code.google.com/apis/console [24] Man Page for nohup. [online]. [cit. 2014-04-01]. Dostupné z: http://www.unix.com/man-page/POSIX/1posix/nohup/ [25] ECMA-404 The JSON Data Interchange Standard. [online]. [cit. 2014-04-01]. Dostupné z: http://www.ecma-international.org/publications/files/ECMAST/ECMA-404.pdf [26] Shepard, Donald (1968). "A two-dimensional interpolation function for irregularly-spaced data". Proceedings of the 1968 ACM National Conference. pp. 517–524. doi:10.1145/800186.810616.

- 36 -

Seznam ilustrací Ilustrace 1: Fresnelova zóna (zdroj: upraveno http://en.wikipedia.org/wiki/File:FresnelSVG1.svg)........................7 Ilustrace 2: Grafické vyjádření prostor pokrývajících křivek pro rovinu.....................9 Ilustrace 3: Zachování průniku při otočení.................................................................12 Ilustrace 4: Obdélníky představující potomky kořenového uzlu stromu indexu........14 Ilustrace 5: Levá část uživatelského rozhraní - zadání parametrů spoje.....................21 Ilustrace 6: Pravá část uživatelského rozhraní - prezentace výsledků dotazu ...........22 Ilustrace 7: Vztahy mezi logickými celky zdrojového kódu datového úložiště.........30

Seznam grafů Graf 1: Závislost času vyhodnocení dotazu [ms] na vzdálenosti koncových bodů [m]..........15 Graf 2: Závislost času [ms] na vzdálenosti [m] – jeden dotazující se, bez vizualizace..........16 Graf 3: Závislost času [ms] na vzdálenosti [m] – jeden dotazující se, s vizualizací...............17 Graf 4: Závislost času [ms] na vzdálenosti [m] – pět dotazujících se, bez vizualizace..........18 Graf 5: Závislost času [ms] na vzdálenosti [m] – pět dotazujících se, s vizualizací...............19

- 37 -