UNIVERZITA KARLOVA V PRAZE

UNIVERZITA KARLOVA V PRAZE Pˇ r´ırodovˇ edeck´ a fakulta Katedra aplikované geoinformatiky a kartografie

Studijn´ı program: Geografie (navazuj´ıc´ı magisterské studium) Studijn´ı obor: Kartografie a geoinformatika

´ Bc. Jana SVOBODOVA

ALGORITMUS PRO AUTOMATIZOVANOU ˚ BUDOV KARTOGRAFICKOU GENERALIZACI SHLUKU METODOU AGREGACE ALGORITHM FOR AUTOMATED BUILDING SIMPLIFICATION USING AGGREGATION

Diplomová práce

Vedouc´ı diplomové práce: Ing. Tomáˇs Bayer, Ph.D.

Praha 2012

Prohlaˇsuji, ˇze jsem z´ avˇereˇcnou práci zpracovala samostatnˇe a ˇze jsem uvedla vˇsechny pouˇzité informaˇcn´ı zdroje a literaturu. Tato práce ani jej´ı podstatná ˇcást nebyla pˇredloˇzena k z´ısk´ an´ı jiného nebo stejného akademického titulu.

V Brnˇe dne 15. 8. 2012

................................ Jana Svobodová

Na tomto m´ıstˇe bych chtˇela podˇekovat pˇredevˇs´ım vedouc´ımu diplomové práce Ing. Tom´ aˇsi Bayerovi, Ph.D. za cenné rady, pˇripom´ınky a ˇcas vˇenovan´ y konzultac´ım. Dále dˇekuji rodiˇc˚ um za podporu v pr˚ ubˇehu celého studia.

Algoritmus pro automatizovanou kartografickou generalizaci shluk˚ u budov metodou agregace Abstrakt Diplomov´ a pr´ ace se vˇenuje tématu automatizované kartografické generalizace. Jej´ım hlavn´ım c´ılem je navrˇzen´ı nového generalizaˇcn´ıho algoritmu pro agregaci budov. V prvn´ı ˇc´ asti je provedena reˇserˇse algoritm˚ u dosud navrˇzen´ ych pro agregaci budov. Dále je pod´ an v´ yklad vlastn´ıho návrhu algoritmu - nejprve jsou podrobnˇe popsány pomocné datové struktury a algoritmy, které algoritmus vyuˇz´ıvá, dále jsou stanoveny kartografické a geometrické podm´ınky pro agregaci. Vlastn´ı algoritmus je zaloˇzen na principu konstrukce straight skeletonu. Ze straight skeletonu jsou odebr´ any vnˇejˇs´ı vrcholy, nad takto vznikl´ ymi strukturami je provedena agregace a agregovan´ y polygon je z´ısk´ an zpˇetnou rekonstrukc´ı ze své kostry. Druh´ a ˇc´ ast pr´ ace je zamˇeˇrena na implementaci a zhodnocen´ı v´ ysledk˚ u. Algoritmus je implemetov´ an pomoc´ı open-source knihoven CGAL, Boost a Shapelib. Dosaˇzené v´ ysledky a jejich struˇcné porovn´ an´ı se SW ArcGIS je diskutováno v závˇeru práce. Kl´ıˇ cov´ a slova: automatizovan´ a kartografická generalizace, aggregace budov, straight skeleton

Algorithm for automated building simplification using aggregation Abstract Diploma thesis deals with automated cartographic generalization. The main aim is to propose a new generalization algorithm for building aggregation. The first part brings summary of existing algorithms for building aggregation. Then the new algorithm is presented: at first, auxiliary data structures and algorithms are presented, then cartographic and geometric requirements are defined. New algorithm is based on the principle of straight skeleton construction. Outer vertices are removed from constructed straight skeletons and those structures are aggregated. The aggregated polygon is reconstructed from aggregated structures. The second part is focused on implementation and results evaluation. The algorithm is implemented using open-source libraries CGAL, Boost and Shapelib. The results and confrontation with SW ArcGIS are discussed in conclusion of the thesis. Key words: automated cartographic generalization, building aggregation, straight skeleton

Obsah ´ 1 UVOD

9

ˇ ˇ LITERATURY 2 RESER SE

11

´ GENERALIZACE SE 3 KARTOGRAFICKA ˇ REN ˇ ´ ZAME IM NA AGREGACI 3.1 Koncepˇcn´ı modely generalizace . . . . . . . . . . . . . . . . . . 3.2 Generalizaˇcn´ı oper´ atory . . . . . . . . . . . . . . . . . . . . . . 3.3 Algoritmy pro generalizaci skupin polygon˚ u metodami agregace 3.3.1 Boundary-based algoritmy . . . . . . . . . . . . . . . . . 3.3.2 Region-based algoritmy . . . . . . . . . . . . . . . . . . ´ DATOVE ´ STRUKTURY A ALGORITMY 4 POMOCNE 4.1 Voronoi diagram . . . . . . . . . . . . . . . . . . . . . . . . 4.2 Minim´ aln´ı vzd´ alenost dvou polygon˚ u . . . . . . . . . . . . . 4.3 Straight skeleton . . . . . . . . . . . . . . . . . . . . . . . . 4.4 Redukovan´ y straight skeleton . . . . . . . . . . . . . . . . . 4.5 Grafové algoritmy . . . . . . . . . . . . . . . . . . . . . . . 4.5.1 Minim´ aln´ı kostra grafu . . . . . . . . . . . . . . . . . 4.5.2 Prohled´ av´ an´ı grafu do hloubky (Depth First Search) 4.6 Douglas-Peucker algoritmus . . . . . . . . . . . . . . . . . .

14 . . . . . . . . 14 . . . . . . . . 15 a amalgamace 17 . . . . . . . . 17 . . . . . . . . 21

. . . . . . . .

23 23 27 29 34 35 35 39 40

. . . .

42 43 45 45 45

´ ˇ ´ 6 NAVRH GENERALIZACN IHO ALGORITMU 6.1 Urˇcen´ı budov vhodn´ ych pro agregaci . . . . . . . . . . . . . . . . . . . . . . . 6.2 Vlastn´ı agregace . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

46 46 50

. . . . . . . .

. . . . . . . .

. . . . . . . .

. . . . . . . .

. . . . . . . .

. . . . . . . .

. . . . . . . .

. . . . . . . .

. . . . . . . .

´ 5 STANOVEN´ I GEOMETRICKYCH ´ A KARTOGRAFICKYCH PODM´ INEK PRO AGREGACI 5.1 Kartograficky pˇrirozené v´ ystupy . . . . 5.2 Zachov´ an´ı plochy a tˇeˇziˇstˇe agregovan´ ych 5.3 R˚ uzné typy budov, zjednoduˇsen´ı tvaru . 5.4 Zmˇena datové reprezentace . . . . . . .

5

. . . . . oblast´ı . . . . . . . . . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

6.2.1 6.2.2 6.2.3

Tvorba a generalizace redukovaného straight skeletonu polygonu . . . . . . . . . . . . . . . . . . . . . . . . . Prvn´ı aproximace agregovaného polygonu . . . . . . . Zpˇetn´ a rekonstrukce polygonu . . . . . . . . . . . . . .

agregovaného . . . . . . . . . . . . . . . . . . . . . . . . . . .

52 55 58

7 IMPLEMENTACE ALGORITMU 7.1 Knihovny CGAL, Boost a ShapeLib . . . . . . . . . . . . . . . . . . . . . . . 7.2 Urˇcen´ı budov pro agregaci . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7.2.1 Naˇcten´ı shapefil˚ u . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7.2.2 Voronoi diagram a urˇcen´ı sousednosti polygon˚ u . . . . . . . . . . . . . 7.3 Vlastn´ı agregace . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7.3.1 Konstrukce straight skeletonu a nalezen´ı minimáln´ı kostry grafu . . . 7.3.2 Generalizace redukovaného skeletonu a tvorba prvn´ı aproximace polygonu 7.3.3 Zpˇetn´ a rekonstrukce polygonu . . . . . . . . . . . . . . . . . . . . . . . 7.4 Vytvoˇren´ y n´ astroj . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

64 64 65 65 66 68 68 70 70 73

ˇ ´ VYSLEDKY ´ 8 DOSAZEN E A JEJICH ZHODNOCEN´ I 8.1 Testovac´ı data . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8.2 Vybran´ a vzorov´ au ´zem´ı . . . . . . . . . . . . . . . . . . . . . . . . . . 8.3 Testov´ an´ı algoritmu na vzorov´ ych u ´zem´ıch a porovnán´ı se SW ArcGIS 8.4 Zhodnocen´ı navrˇzeného algoritmu a jeho implementace . . . . . . . . .

74 75 75 76 83

. . . .

. . . .

. . . .

. . . .

´ ER ˇ 9 ZAV

87

ˇ YCH ´ ˚ SEZNAM POUZIT ZDROJU

88

ˇ´ SEZNAM PR ILOH

92

6

Seznam obr´ azk˚ u 3.1 3.2 3.3 3.4 3.5 3.6 3.7 3.8 3.9 3.10 4.1 4.2 4.3 4.4 4.5 4.6 4.7 4.8 4.9 4.10 4.11 4.12 5.1 5.2 5.3

Vybrané generalizaˇcn´ı operátory (upraveno podle: LI, 2007, s. 23) . . . . . . 15 Konstrukce konvexn´ı obalky . . . . . . . . . . . . . . . . . . . . . . . . . . . 17 Agregace konvexn´ı ob´ alkou, REGNAULD, 1998 (pˇrevzato z: AGENT, DD3, 2001, s. 39) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 18 Agregace pˇrid´ an´ım plochy, WARE et al., 1995 (pˇrevzato z: AGENT, DD3, 2001, s. 39) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19 Agregace posunut´ım, WARE et al., 1995 (pˇrevzato z: AGENT, DD3, 2001, s. 38) 19 Agregace posunut´ım, REGNAULD, 1998 (pˇrevzato z: AGENT, DD3, 2001, s. 38) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 20 Agregace bufferem . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 20 Pˇr´ıklad agregace pravo´ uhl´ ych tvar˚ u (pˇrevzato z: SU et al., 1997, s. 242) . . . 22 Pˇr´ıklad agregace sloˇzitˇejˇs´ıch tvar˚ u (pˇrevzato z: SU et al., 1997, s. 243) . . . . 22 Agregace se zjednoduˇsen´ım (pˇrevzato z: SU et al., 1997, s. 241, 245) . . . . . 22 Voronoi diagram (upraveno podle: BAYER, 2008) . . . . . . . . . . . . . . . . 24 Konstrukce Voronoi diagramu (pˇrevzato z: BERG et al., 2008, s. 152) . . . . 25 Fortune algoritmus (pˇrevzato z: BERG et al., 2008, s. 153-154) . . . . . . . . 25 V´ ypoˇcet vzd´ alenosti dvou polygon˚ u . . . . . . . . . . . . . . . . . . . . . . . . 27 Princip tvorby straight skeletonu . . . . . . . . . . . . . . . . . . . . . . . . . 29 Ud´ alosti pˇri konstrukci straight skeletonu (upraveno podle: EPPSTEIN a ERICKSON, 1999, s. 8) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 30 ˇ ALEK, ´ Datov´ a struktura LAV (upraveno podle: FELKEL a OBDRZ 1998, s. 4) 32 Konstrukce straight skeletonu pro nekonvexn´ı polygony (upraveno podle: FELˇ ALEK, ´ KEL a OBDRZ 1998, s. 5) . . . . . . . . . . . . . . . . . . . . . . . . . 32 Redukovan´ y straight skeleton . . . . . . . . . . . . . . . . . . . . . . . . . . . 34 Grafové pojmy . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 36 ´ R, ˇ 2004, s. 102) . 38 Princip Bor˚ uvkova-Kruskalova algoritmu (pˇrevzato z: KOLA Princip Douglas-Peucker algoritmu . . . . . . . . . . . . . . . . . . . . . . . . 40 Omezen´ı liniov´ ymi prvky . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 43 Grafické limity (upraveno podle: AGENT, DA2, 2001, s. 32) . . . . . . . . . . 44 Omezuj´ıc´ı podm´ınky pro budovy (upraveno podle: STEINIGER a TAILLANDIER, s. 2) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 44

7

6.1 6.2 6.3 6.4 6.5 6.6 6.7 6.8 6.9 6.10 6.11 6.12 6.13 6.14 8.1 8.2 8.3 8.4 8.5 8.6 8.7 8.8 8.9 8.10 8.11

Voronoi diagram nad centroidy budov pro urˇcen´ı sousednosti polygon˚ u . . . . Testov´ an´ı vz´ ajemné polohy spojnic centroid˚ u a segment˚ u omezen´ı . . . . . . . Graf pˇredstavuj´ıc´ı skupiny budov pro agregaci . . . . . . . . . . . . . . . . . . Princip agregace polygon˚ u . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Schéma generalizaˇcn´ıho algoritmu . . . . . . . . . . . . . . . . . . . . . . . . . Generalizace redukovaného skeletonu agregovaného polygonu . . . . . . . . . Prvn´ı aproximace polygonu . . . . . . . . . . . . . . . . . . . . . . . . . . . . Vytvoˇren´ı prvn´ı aproximace polygonu . . . . . . . . . . . . . . . . . . . . . . Urˇcen´ı u ´hl˚ u pro spr´ avnou orientaci vrchol˚ u kostry . . . . . . . . . . . . . . . Odvozen´ı vztah˚ u pro posun vrchol˚ u po bisektorech . . . . . . . . . . . . . . . Topologické zmˇeny polygonu pˇri rekonstrukci polygonu . . . . . . . . . . . . Stˇret rovnobˇeˇzn´ ych hran . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Zapojen´ı vrcholu na m´ıstˇe pr˚ useˇc´ıku I do SLAV . . . . . . . . . . . . . . . . . Stanoven´ı hodnoty w . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . V´ yˇrezy vzorov´ ych u ´zem´ı (mˇeˇr´ıko je promˇenlivé v rozsahu 1:10 000 - 1:25 000) Ilustrace v´ ysledk˚ u funkce Area Aggregate. (pˇrevzato z: ESRI, 2000, s. 11) . . Ilustrace v´ ysledk˚ u pro u ´zem´ı 1 . . . . . . . . . . . . . . . . . . . . . . . . . . Ilustrace v´ ysledk˚ u pro u ´zem´ı 2 . . . . . . . . . . . . . . . . . . . . . . . . . . Ilustrace v´ ysledk˚ u pro u ´zem´ı 3 . . . . . . . . . . . . . . . . . . . . . . . . . . Ilustrace v´ ysledk˚ u pro u ´zem´ı 5 . . . . . . . . . . . . . . . . . . . . . . . . . . Ilustrace v´ ysledk˚ u pro u ´zem´ı 6 . . . . . . . . . . . . . . . . . . . . . . . . . . Ilustrace v´ ysledk˚ u pro u ´zem´ı 7 . . . . . . . . . . . . . . . . . . . . . . . . . . Ilustrace v´ ysledk˚ u pro u ´zem´ı 8 a 9 . . . . . . . . . . . . . . . . . . . . . . . . Generalizace vybran´ ych budov generalizaˇcn´ım algoritmem Area Aggregate . . Chyba implementace . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

8

46 47 49 50 51 52 55 56 56 57 59 61 61 63 75 77 78 79 79 79 81 81 82 83 85

1

´ UVOD

Kartografick´ a generalizace je v souˇcasné dobˇe stále ˇziv´ ym tématem kartografického v´ yzkumu. Podnˇety k dalˇs´ımu zkoumán´ı a zefektivˇ nován´ı kartografické generalizace jsou d´ av´ any jak rozvojem digit´ aln´ıch technologi´ı, tak i nov´ ych technik z´ıskáván´ı a zpracován´ı prostorov´ ych dat (napˇr. laser scanning). Kartografové se této problematice vˇenovali odjakˇziva, dˇr´ıve byla zamˇeˇrena pˇredevˇs´ım na tiˇstˇené mapy, s rozvojem poˇc´ıtaˇcové kartografie se stále v´ıce uplatˇ nuj´ı automatizované systémy pro generalizaci. Prvn´ı pokusy o návrh algoritm˚ u pro automatizovanou kartografickou generalizaci se objevuj´ı jiˇz v 60. letech 20. stolet´ı, nicménˇe d˚ ukladnˇejˇs´ı zkoum´ an´ı, spoleˇcnˇe s rozvojem poˇc´ıtaˇc˚ u, se váˇze sp´ıˇse aˇz k poˇcátku 70. let. Jako prvn´ı se zaˇcaly zkoumat algoritmy na generalizaci polylini´ı, coˇz je relativnˇe snadnˇejˇs´ı u ´kol neˇz napˇr. generalizace polygon˚ u. Pozdˇeji se pozornost pˇresunula i do dalˇs´ıch oblast´ı, bylo vytvoˇreno mnoˇzstv´ı koncepˇcn´ıch model˚ u a nov´ ych pˇr´ıstup˚ u k automatizované generalizaci. Generalizace budov je ˇreˇsena nejen národn´ımi mapovac´ımi agenturami pˇri tvorbˇe státn´ıch mapov´ ych dˇel, ale i v soukromém sektoru. Generalizace m˚ uˇze b´ yt provádˇena bud’ ruˇcnˇe, nebo poloautomatizovanˇe. C´ılem kartograf˚ u je dospˇet do stavu existuj´ıc´ıho plnˇe automatizovaného systému. Cesty k dosaˇzen´ı takového stavu jsou dvoj´ı: bud’ se navrhuj´ı nové algoritmy, nebo se optimalizuj´ı algoritmy st´ avaj´ıc´ı. Nˇekteré oblasti automatizované kartografické generalizace jsou jiˇz pomˇernˇe bohatˇe rozpracov´ any - napˇr. problematika zjednoduˇsován´ı tvar˚ u budov. Jiné oblasti, mezi nˇeˇz patˇr´ı i problematika agregace, jsou rozpracovány ménˇe. C´ılem pˇredkládané diplomové pr´ ace je tedy navrhnout nov´ y algoritmus, kter´ y ˇreˇs´ı problematiku kartografické generalizace budov metodou agregace. Novˇe navrhovan´ y algoritmus pracuje ve vektorovém prostˇred´ı. Jeho stˇeˇzejn´ı myˇslenkou je vyuˇzit´ı topologické kostry polygonu, konkrétnˇe straight skeletonu. Pˇri práci s kostrou polygonu jsou vyuˇz´ıv´ any grafové algoritmy, pˇredevˇs´ım prohledáván´ı do hloubky a nalezen´ı minimáln´ı kostry grafu. Z kostry agregovaného polygonu je rozˇsiˇrován´ım po bisektorech zrekonstruov´ an vlastn´ı v´ ysledn´ y polygon.

9

Navrhovan´ y algoritmus se snaˇz´ı vytvoˇrit alternativu k jiˇz existuj´ıc´ım ˇreˇsen´ım, která v´ıce ˇci ménˇe u ´spˇeˇsnˇe ˇreˇs´ı problematiku agregace. Hlavn´ı pˇr´ınos nového algoritmu vid´ım pˇredevˇs´ım v následuj´ıc´ıch oblastech: • v pokusu zahrnout agregaci do celkového kontextu kartografické generalizace, • ve snaze zjednoduˇsit novˇe vznikaj´ıc´ı polygon v závislosti na zadan´ ych parametrech (mˇeˇr´ıtku), • ve snaze zpracovat co nejˇsirˇs´ı spektrum budov, • v n´ avrhu pouze ve vektorovém prostˇred´ı. Konkrétn´ı poˇzadavky na algoritmus jsou dále stanoveny a rozvedeny v 5. kapitole, 6. kapitola se vˇenuje n´ avrhu algoritmu a 8. kapitola je zamˇeˇrena na jeho celkové zhodnocen´ı. Diplomov´ a pr´ ace je rozdˇelena do dvou hlavn´ıch ˇcást´ı - teoretické a praktické. Teoretick´ a ˇcást obsahuje ˇsest kapitol - u ´vod, literárn´ı reˇserˇsi, shrnut´ı poznatk˚ u v oblasti kartografické generalizace se zamˇeˇren´ım na agregaci a tˇri kapitoly vˇenuj´ıc´ı se návrhu nového algoritmu. Praktick´ a ˇc´ ast zahrnuje tˇri ˇc´ asti - implementaci navrˇzeného algoritmu, zhodnocen´ı v´ ysledk˚ u a efektivity vytvoˇreného n´ astroje a závˇer. Práce je uzavˇrena seznamem pouˇzit´ ych zdroj˚ u.

10

2

ˇ ˇ LITERATURY RESER SE

Reˇserˇsn´ı ˇc´ ast diplomové pr´ ace se vˇenuje pˇredevˇs´ım generalizaˇcn´ım algoritm˚ um v kartografii se zamˇeˇren´ım na automatické ˇreˇsen´ı agregace a také je zm´ınˇeno nˇekolik publikac´ı pojedn´ avaj´ıc´ıch obecnˇe o (automatizované) kartografické generalizaci. Aˇckoliv je problematika kartografické generalizace ˇreˇsena souvisle jiˇz témˇeˇr tˇri desetilet´ı, obsáhlejˇs´ıch publikac´ı zab´ yvaj´ıc´ıch se touto problematikou je pouze nˇekolik (existuje vˇsak pomˇernˇe rozs´ ahlé mnoˇzstv´ı publikac´ı kratˇs´ıho rozsahu). Problematika automatizované kartografické generalizace metodou agregace nebyla doposud v kartografické literatuˇre detailnˇeji ˇreˇsena, existuje k n´ı pouze velmi málo relevantn´ıch publikac´ı. V r´ amci reˇserˇse byly prostudovány dvˇe kniˇzn´ı publikace a nˇekolik ˇclánk˚ u a závˇereˇcn´ ych prac´ı t´ ykaj´ıc´ıch se problematiky kartografické generalizace, automatizované generalizace budov a automatizované generalizace metodou agregace. Pˇreváˇzná vˇetˇsina literatury je cizojazyˇcn´ a, zejména anglick´ a, ˇcesk´ a literatura je zm´ınˇena na závˇer kapitoly. Dobr´ y v´ ychoz´ı z´ aklad pro pochopen´ı v´ yvoje a problematiky kartografické generalizace nejen teoreticky, ale i s kapitolami o proveden´ ych v´ yzkumech, pˇredstavuje publikace Generalisation of Geograhic Information: Cartograhic Modelling and Applications (MACKANESS, RUAS, SARJAKOSKI, 2007). Tato publikace mimo jiné shrnuje dosavadn´ı teoretické pˇr´ıstupy ke kartografické generalizaci. Publikace Algorithmic Foundation of Multi-Scale Spatial Representation (LI, 2007) se zamˇeˇruje pˇredevˇs´ım na v´ yklad principu algoritm˚ u pouˇz´ıvan´ ych v digitáln´ı kartografii. V prvn´ı ˇc´ asti je srozumitelnˇe podán v´ yklad rámce pro tyto algoritmy a také matematickogeometrické z´ aklady (matematická morfologie, Delaunay triangulace, Voronoi diagramy, skeletonizace). Druh´ a ˇc´ ast publikace se pak zamˇeˇruje na jednotlivé algoritmy, klasifikované podle generalizaˇcn´ıch oper´ ator˚ u a podle dimenzionality prvk˚ u (bod, linie, polygon, 2,5-D). V této ˇcásti jsou vyloˇzeny i z´ akladn´ı generalizaˇcn´ı algoritmy pro agregaci. Tyto dvˇe knihy se staly v´ ychoz´ım materiálem pro studium, dále byly prostudovány ˇcl´ anky pro hlubˇs´ı pochopen´ı problematiky. Jedn´ım z prvn´ıch, kdo se zab´ yval generalizac´ı s´ıdel, byl nˇemeck´ y kartograf W. Staufenbiel (1973, Universit¨ at Hannover). Navrhl komplexn´ı algoritmus pro generalizaci s´ıdel, vˇcetnˇe vodstva, komunikac´ı, budov a vegetaˇcn´ıho pokryvu. V otázce generalizace budov se zamˇeˇruje pˇredevˇs´ım na zjednoduˇsen´ı tvaru budov, zaloˇzenému na odstranˇen´ı nebo upraven´ı krátk´ ych

11

stran. Ot´ azce agregace se vˇenuje jen v náznac´ıch a nenavrhuje ˇzádn´ y konkrétn´ı algoritmus. Dalˇs´ı nˇemeck´ y kartograf, U. Meyer (1989), hodnotil a testoval Staufenbiel˚ uv algoritmus a sám se pokouˇsel navrhnout algoritmy pro automatické rozeznán´ı zvláˇstnˇe tvarovan´ ych buˇ dov, které Staufenbiel˚ uv algoritmus nedokáˇze dobˇre ˇreˇsit (podle STAMAPACH, 2006). Konkrétn´ı n´ avrh algoritmu t´ ykaj´ıc´ıho se agregace polygon˚ u vytvoˇrili SU et al, 1997. Tento algoritmus je zaloˇzen na matematické morfologii a je provádˇen v rastrovém prostˇred´ı. V letech 1997-2000 byl pod hlaviˇckou Evropské komise veden projekt AGENT (Automated GEneralisation New Technology) za u ´ˇcelem vyvinut´ı nov´ ych generalizaˇcn´ıch technik. ´ Uˇcastn´ıky projektu byli francouzská NMA (IGN), firma LaserScan a univerzity v Curychu, Edinburgu a Grenoblu. V´ ysledkem je model hierarchicky pracuj´ıc´ı, zaloˇzen´ y na agentech ve tˇrech u ´rovn´ıch (mikro-, meso- a makro- mˇeˇr´ıtko), a t´ım je usmˇerˇ nována generalizace v ˇsirokém kontextu. O projektu bylo publikováno mnoˇzstv´ı ˇclánk˚ u, napˇr. AGENT, DD2, 2001 (pˇrehled z´ akladn´ıch algoritm˚ u), nebo LAMY et al. (princip fungován´ı). Zpr´ ava AGENT, DD3, 2001 uvád´ı pˇrehled algoritm˚ u pro nˇekteré operace (mezi nimi i agregaci) a doporuˇcen´ı pro pouˇzit´ı tˇechto algoritm˚ u v rámci generalizace. Z algoritm˚ u pro agregaci jmenujme algoritmy WARE et al., 1995. Jeden je zaloˇzen´ y na Delaunay triangulaci a n´ asledné rotaci a posunut´ı objekt˚ u, druh´ y také vyuˇz´ıvá triangulaci a následné vyplnˇen´ı prostor˚ u mezi objekty. REGNAULD, 1998, navrhl algoritmus zaloˇzen´ y na posunut´ı objekt˚ u a v témˇze roce i algoritmus zaloˇzen´ y na konvexn´ı obálce. ORMSBY, 1999 navrhl podobnˇe jako SU algoritmus zaloˇzen´ y na matematické morfologii. Dalˇs´ı zpr´ ava AGENT, DA2, 2001, definuje omezuj´ıc´ı podm´ınky (constraints) pro generalizaci jednotliv´ ych témat (vˇcetnˇe zástavby) a to na vˇsech tˇrech u ´rovn´ıch (mikro, mezo, makro). Nˇekteré z tˇechto omezen´ı vyuˇz´ıvaj´ı STEINIGER a TAILLANDIER, 2005 pˇri generalizaci budov se snahou o zlepˇsen´ı této generalizace. Pˇridávaj´ı pravidla pro rozdˇelen´ı zástavby do pˇeti typ˚ u. Praktick´ y pˇr´ıklad ukázali na generalizaci z mˇeˇr´ıtka 1:10 000 do mˇeˇr´ıtka 1:25 000 na ˇsv´ ycarsk´ ych a francouzsk´ ych mapách. Projekt AGENT poskytuje dobré v´ ysledky zejména v urbánn´ıch oblastech. Vylepˇsen´ı pˇrináˇs´ı model CartACom (DUCHENE, 2004), kter´ y se zamˇeˇruje na slabosti pˇredchoz´ıho modelu v rur´ aln´ıch oblastech. V roce 2007 byly tyto dva modely doplnˇeny jeˇstˇe dalˇs´ım, kter´ y lépe pracuje pro podkladov´ a témata, kter´ a souvisle pokr´ yvaj´ı plochu (napˇr. landcover, vrstevnice). Tento model se naz´ yv´ a GAEL a byl vytvoˇren Gaffurim. Moˇzné zp˚ usoby kombinace tˇechto tˇr´ı model˚ u navrhuj´ı DUCHENE a GAFFURI, 2008. Otázce agregace se vˇenuje ve své disertaˇcn´ı pr´ aci HAUNERT, 2008. Zamˇeˇruje se na optimizaci agregace ploˇsn´ ych prvk˚ u (landcover, administrativn´ı ˇclenˇen´ı...). Jeho ˇreˇsen´ı pˇrináˇs´ı lepˇs´ı v´ ysledky zejména v otázce sémantické pˇresnosti, jedná se o deterministickou metodu a umoˇzn ˇuje lepˇs´ı zpracován´ı omezuj´ıc´ıch podm´ınek (constraints). QI a LI, 2008 v u ´vodn´ı ˇc´ asti svého ˇclánku provád´ı krátké shrnut´ı dosavadn´ıch algoritm˚ u pro generalizaci budov, napˇr. Ruas, 1998, která se zab´ yvala metodou odsunu budov, Regnauld 2001, kter´ y zkoumal typifikaci budov nebo Christophe a Ruas, 2002 (detekce linie budov (building alignment)). Oni sami se vˇenuj´ı otázce shlukován´ı budov zaloˇzenému na hierarchick´ ych omezen´ıch, jak´ ymi jsou napˇr´ıklad bl´ızkost, podobnost nebo orientace. 12

Kartografickou generalizac´ı, zejména jej´ı algoritmizac´ı, se také dlouhodobˇe zab´ yv´ a BAYER. Pˇr´ıkladem jeho pr´ ace je publikace z roku 2009, kde navrhuje algoritmus na zjednoduˇsen´ı budov s vyuˇzit´ım rekurze. Tento algoritmus se snaˇz´ı zlepˇsovat v´ ysledky pˇredevˇs´ım samostatnˇe stoj´ıc´ıch pravo´ uhl´ ych budov komplexn´ıch geometrick´ ych tvar˚ u. Z ˇcesky psan´ ych publikac´ı se problému generalizace budov vˇenuje ve své diplomové pr´ aci ˇ STAMPACH, 2006, kter´ y implementuje Staufenbiel˚ uv algoritmus. Testuje jeho u ´spˇeˇsnost na pˇr´ıpadu mˇesta Brna. Nav´ıc také podává struˇcn´ y pˇrehled algoritm˚ u t´ ykaj´ıc´ıch se generalizace budov (zjednoduˇsov´ an´ı tvaru, posuny objekt˚ u, typifikace). ´ ´ Diplomov´ a pr´ ace POPELINSKEHO, 2011 se vˇenuje generalizaci ˇr´ıˇcn´ıch s´ıt´ı, implementuje a porovn´ av´ a v´ ysledek generalizace na základˇe r˚ uzn´ ych klasifikac´ı ˇr´ıˇcn´ıch tok˚ u a dalˇs´ıch parametr˚ u. Nem´ a tedy pˇr´ımou souvislost s generalizac´ı budov, v u ´vodn´ım pˇrehledu je vˇsak provedena kr´ atk´ a reˇserˇse pˇr´ıstup˚ u ke generalizaci. Uveden´ y pˇrehled nen´ı ani nem˚ uˇze b´ yt vyˇcerpávaj´ıc´ı. Vˇetˇsina publikac´ı t´ ykaj´ıc´ıch se kartografické generalizace je ve formˇe ˇclánk˚ u a r˚ uzn´ ych pˇr´ıspˇevk˚ u v odborn´ ych ˇcasopisech a na konferenc´ıch. Jsou navrhov´ any nové algoritmy pro r˚ uzné generalizaˇcn´ı operátory, nicménˇe problematika agregace nen´ı pˇr´ıliˇs ˇcasto v zájmu v´ yzkumn´ık˚ u.

13

3

´ GENERALIZACE SE KARTOGRAFICKA ˇ REN ˇ ÍM NA AGREGACI ZAME

V této ˇc´ asti je podrobnˇeji vysvˇetlena problematika kartografické generalizace a pˇr´ıstupy k jej´ımu ˇreˇsen´ı, je definov´ ana a popsána operace agregace a kapitolu uzav´ırá pˇrehled existuj´ıc´ıch algoritm˚ u prov´ adˇej´ıc´ıch agregaci.

3.1

Koncepˇ cn´ı modely generalizace

V pr˚ ubˇehu ˇcasu bylo kartografy vytvoˇreno velké mnoˇzstv´ı koncepˇcn´ıch model˚ u generalizace. Koncepˇcn´ı model je teoretick´ y podklad pro ˇreˇsen´ı dané problematiky. Nastiˇ nuje pohled autor˚ u na vˇec a navrhuje zp˚ usob ˇreˇsen´ı nebo zpracován´ı problému. Jedn´ım z prvn´ıch byl model Robinsona et al. (1978), kteˇr´ı rozdˇelili proces generalizace na dva kroky: selekce (pˇredzpracován´ı) a samotná generalizace zahrnuj´ıc´ı geometrickou a statistickou manipulaci s objekty, která je dosaˇzena skrz operátory simplifikace, klasifikace a symbolizace. I v dneˇsn´ı dobˇe je ˇcasto citovan´ y model McMASTER a SHEA, 1989. Stanovuje tˇri d˚ uleˇzité aspekty: proˇc generalizovat, kdy generalizovat a jak generalizovat. Prvn´ı ˇcást pˇredstavuje teoretické ot´ azky (stanoven´ı c´ıl˚ u generalizace), druhá ˇcást anal´ yzu prostˇredk˚ u, které jsou k dispozici (kartometrické anal´ yzy a dostupné algoritmy) a tˇret´ı generalizaˇcn´ı operátory, pomoc´ı kter´ ych je generalizace prov´ adˇena. Tento model slouˇz´ı ke zhodnocen´ı, zda je generalizace nutná a pokud ano, tak jak´ ymi prostˇredky v dané situaci j´ı nejlépe dosáhnout. Tyto modely jsou st´ ale pouˇz´ıvané, i kdyˇz jsou kritizované z d˚ uvodu, ˇze pˇristupuj´ı ke generalizaci sekvenˇcnˇe a nikoliv komplexnˇe. Sekvenˇcn´ı pˇr´ıstup je charakteristick´ y t´ım, ˇze jednotlivé kroky generalizace jsou ˇreˇseny postupnˇe, napˇr. postupnou aplikac´ı jednotliv´ ych generalizaˇcn´ıch oper´ ator˚ u na jednotlivé sloˇzky databáze (body, linie, polygony; vodstvo, terén, komunikace, z´ astavba...). Problém nastává v tom, ˇze jednotlivé prvky se navzájem ovlivˇ nuj´ı a v toku generalizace je nelze editovat samostatnˇe. Komplexnˇejˇs´ı ˇreˇsen´ı se tak snaˇz´ı navrhnout postup, kter´ y zohledˇ nuje právˇe tyto vazby. Byly proto vytvoˇreny i dalˇs´ı modely, zaloˇzené na znalostn´ıch systémech a umˇelé inteligenci (napˇr. Muller, 1990, 1991, Buttenfield a McMaster, 1991), modely zaloˇzené na komunikuj´ıc´ıch agentech (projekt AGENT) nebo modely s omezen´ımi (constraint-based modelling) - napˇr. Sarjakoski a Kilpeläinen, 1999 nebo Sester, 2005. Modely se r˚ uznˇe vyv´ıjej´ı, ale v pozad´ı stále z˚ ustává geometrick´ y základ jednotliv´ ych operátor˚ u, které generalizaci charakterizuj´ı. 14

3.2

Generalizaˇ cn´ı oper´ atory

Generalizaˇcn´ı oper´ atory reprezentuj´ı zp˚ usob transformace prvk˚ u mapy v pr˚ ubˇehu generalizace, resp. transformace, ke kter´ ym v d˚ usledku generalizace docház´ı. Tˇechto zmˇen je pak v pr˚ ubˇehu generalizace prakticky dosaˇzeno implementac´ı vhodn´ ych algoritm˚ u. Oper´ atory mohou b´ yt klasifikovány r˚ uzn´ ymi zp˚ usoby. Podle LI, 2007 provedli Rieger a Coulson v roce 1993 pr˚ uzkum mezi uznávan´ ymi kartografy, a mnoz´ı z nich se neshodli na definici jednotliv´ ych oper´ ator˚ u nebo nˇekteré ani definovat nedokázali. Neexistuje konsensus pro klasifikaci nebo definici oper´ ator˚ u. Zde budeme vycházet z klasifikace pouˇzité LI, 2007, která rozdˇeluje oper´ atory podle dimenzionality prvk˚ u, na kter´ ych jsou generalizaˇcn´ı algoritmy provádˇeny. Náˇs z´ ajem leˇz´ı pˇredevˇs´ım na generalizaci polygon˚ u, konkrétnˇe budov. Bylo vytvoˇreno mnoˇzstv´ı algoritm˚ u pro oper´ atory pracuj´ıc´ı jak s jednotliv´ ymi polygony, tak i se skupinou polygon˚ u. Téma pr´ ace je zamˇeˇreno na problematiku agregace, která dosud nen´ı uspokojivˇe ˇreˇsena, a proto se v n´ asleduj´ıc´ı ˇcásti budeme vˇenovat algoritm˚ um zamˇeˇren´ ym na agregaci a amalgamaci. S oper´ atory agregace a amalgamace bude v této ˇcásti struˇcnˇe porovn´ an i operátor typifikace a proto uvedeme také jeho definici. Definice operátor˚ u jsou následuj´ıc´ı. agregace: spojen´ı v´ıce prvk˚ u oddˇelen´ ych prázdn´ ym prostorem v jeden zjednoduˇsen´ y amalgamace: spojen´ı v´ıce prvk˚ u oddˇelen´ ych jin´ ym prvkem v jeden zjednoduˇsen´ y typifikace: zachov´ an´ı typického vzoru v´ıce prvk˚ u se souˇcasn´ ym zjednoduˇsen´ım struktury, v´ ysledkem je opˇet v´ıce prvk˚ u

Obr. 3.1: Vybrané generalizaˇcn´ı operátory (upraveno podle: LI, 2007, s. 23) LI v klasifikaci tyto oper´ atory oddˇeluje, nicménˇe v ˇcásti vˇenované algoritm˚ um jsou agregace a amalgamace vykl´ ad´ any spoleˇcnˇe. Tento princip je pouˇzit i v diplomové práci. Z´ avislost na mˇ eˇ r´ıtku mapy. Generalizaˇcn´ı operátor, kter´ y rozsahem své pouˇzitelnosti a vhodnosti pouˇzit´ı nejv´ıce soupeˇr´ı s agregac´ı, je typifikace. Podle LI, 2007, se mˇen´ı typ pouˇzit´ ych oper´ ator˚ u pˇri generalizaci v závislosti na mˇeˇr´ıtku. Pˇri generalizaci z mˇeˇr´ıtka 1:10 000 do 1:25 000 je hlavn´ı operac´ı typifikace. Pˇri transformaci do 1:50 000 uˇz se zaˇc´ıná v´ıce uplatˇ novat agregace a amalgamace. Pˇri dalˇs´ım oddálen´ı (1:100 000) uˇz jsou pˇrevaˇzuj´ıc´ımi operacemi pr´ avˇe tyto dvˇe. 15

Ve zpr´ avˇe AGENT (DD3, 2001) m˚ uˇzeme nalézt jin´ y pˇr´ıklad. Zde je agregace pojata jako souhrn´ y n´ azev pro amalgamaci a typifikaci. Agregace v naˇsem pojet´ı je zde naz´ yv´ ana amalgamac´ı, resp. amalgamac´ı, kdy se jedná o slouˇcen´ı v´ıce prvk˚ u v jeden vˇetˇs´ı stejné vrstvy. C´ılem této operace je pak zachovat co nejv´ıce p˚ udorys, plochu i strukturu agregovan´ ych prvk˚ u. Zachov´ an´ı struktury je i c´ılem typifikace. Kritériem, kdy vybrat mezi agregac´ı a typifikac´ı, je pak geografick´ y kontext. Ve zprávˇe je uveden pˇr´ıklad rozˇclenˇen´ı mˇesta do tˇr´ı typ˚ u zástavby, resp. hustoty z´ astavby: centrum mˇesta, okrajové oblasti a pˇrechodné oblasti. V centru je z´ astavba zn´ azornˇena pln´ ymi bloky budov, v pˇrechodné oblasti se uplatˇ nuje agregace pro spojen´ı jednotliv´ ych budov v komplexnˇejˇs´ı budovy a v okrajov´ ych ˇcástech se uplatˇ nuje hlavnˇe typifikace pro zachov´ an´ı rozvolnˇené zástavby. ˇ Cesk´ e mapov´ e sady. Tyto skuteˇcnosti jsou platné i pro ˇceské sady mapov´ ych dˇel. Prostuˇ r˚ dován´ım Z´ akladn´ıch a Topografick´ ych map CR uzn´ ych mˇeˇr´ıtek (od 1:10 000 do 1:100 000) m˚ uˇzeme zhodnotit zn´ azornˇen´ı budov jako samostatnˇe stoj´ıc´ıch objekt˚ u následovnˇe: • v mˇeˇr´ıtku 1:10 000 jsou zn´ azornˇeny témˇeˇr vˇsechny budovy (pˇri porovnán´ı ZABAGED s ortofoto), i kdyˇz uˇz tvarovˇe zjednoduˇsené, • v mˇeˇr´ıtku 1:25 000 (topografická mapa) docház´ı k ˇcásteˇcné agregaci budov, pˇrevaˇzuj´ı vˇsak sp´ıˇse jiné oper´ atory (pˇredevˇs´ım typifikace a to pˇredevˇs´ım v m´ıstech suburbánn´ıho a rur´ aln´ıho charakteru), • v mˇeˇr´ıtku1:50 000 (Z´ akladn´ı i topografická mapa) jsou témˇeˇr bez v´ yjimky hustˇe zastavˇen´ au ´zem´ı (urb´ ann´ı oblasti) znázornˇena jako bloky budov, m´ısta s niˇzˇs´ı hustotou staveb jsou zakreslena zjednoduˇsen´ ymi budovami, • v mˇeˇr´ıtku 1:100 000 jsou s´ıdla zobrazena bud’ ploˇsn´ ym nebo bodov´ ym znakem v závislosti na jejich velikosti a v´ yznamu.

16

3.3

Algoritmy pro generalizaci skupin polygon˚ u metodami agregace a amalgamace

Algoritmy pro agregaci a amalgamaci m˚ uˇzeme podle LI, 2007 rozdˇelit na dva typy: algoritmy pracuj´ıc´ı s hranic´ı polygonu (boundary-based ), nebo pracuj´ıc´ı s oblast´ı jako celkem (region-based ). Ve zpr´ avˇe AGENT, DD3, 2001 jsou algoritmy pro agregaci (resp. amalgamaci) rozdˇeleny podle techniky, kterou je agregace provedena. Prvn´ı skupina pracuje s posunut´ım prvk˚ u (displacement), druh´ a s vyplnˇen´ım m´ısta mezi objekty. K prvn´ımu typu algoritm˚ u (dle LI) patˇr´ı pˇredevˇs´ım algoritmy vyuˇz´ıvaj´ıc´ı konvexn´ı obálky. Mezi druh´ y typ algoritm˚ u m˚ uˇzeme zaˇradit algoritmus SU et al., 1997, kter´ y vyuˇz´ıvá morfologick´ ych oper´ ator˚ u. Ten byl navrˇzen pro rastrové prostˇred´ı, kdeˇzto pˇredchoz´ı pracuj´ı s vektorov´ ymi daty. Nicménˇe LI, 2007, se domn´ıvá, ˇze nen´ı pˇr´ıliˇs nutné rozliˇsovat mezi prostˇred´ım algoritm˚ u. Algoritmy jsou velmi ˇcasto aplikované tak, ˇze se vycház´ı z vektoru, kter´ y je pˇreveden na rastr, ve kterém se daj´ı sn´ aze definovat prostorové vazby, a jsou na nˇem aplikovány jednotlivé generalizaˇcn´ı kroky. V´ ysledek generalizace je pak konvertován na vektorová data. Tyto transformace jsou vˇsak v´ ypoˇcetnˇe velmi neefektivn´ı a informaˇcnˇe ztrátové. 3.3.1

Boundary-based algoritmy

V nejjednoduˇsˇs´ı formˇe je proces agregace pomoc´ı konvexn´ıch obálek vlastnˇe jen vytvoˇren´ım pˇr´ısluˇsné konvexn´ı ob´ alky. Algoritm˚ u na tvorbu konvexn´ıch obálek je velké mnoˇzstv´ı, zmiˇ nme napˇr´ıklad gift-wrapping algoritmus (Jarvis, 1973) a quick hull algoritmus (Gosper, 1998; O’Rourke, 1993) nebo Graham’s scan (Graham, 1972). V´ yklad principu jednotliv´ ych algoritm˚ u lze nalézt napˇr´ıklad v LI, 2007, jejich ilustrace je na obr. 3.2.

Obr. 3.2: (a) budovy vstupuj´ıc´ı do algoritmu pro konvexn´ı obálku, (b) gift-wrapping algoritmus, (c) quick hull algoritmus, (d) v´ ysledná konvexn´ı obálka 17

LI d´ ale uv´ ad´ı, ˇze ˇreˇsen´ı agregace t´ımto zp˚ usobem je v nˇekter´ ych pˇr´ıpadech velmi zjednoduˇsené. Uv´ ad´ı moˇznost pˇrid´ an´ı nˇejak´ ych omezen´ı pro tvorbu konvexn´ı obálky (napˇr. maximáln´ı délka strany), ale ani toto ˇreˇsen´ı nepˇrináˇs´ı pˇr´ıliˇs uspokojivé v´ ysledky. Jak je zˇrejmé z obr´ azku 3.2, tyto algoritmy maj´ı tu nev´ yhodu, ˇze nezachovávaj´ı pravé u ´hly, takˇze nejsou pˇr´ıliˇs pouˇzitelné pro budovy. To je d˚ usledkem definice konvexn´ı ob´ alky. Obálka vytv´ aˇr´ı polygon o nejmenˇs´ı ploˇse, kter´ y obsahuje vˇsechny body u ´tvaru, ale jej´ımi vertexy jsou pouze body p˚ uvodn´ıch prvk˚ u. T´ım nelze pˇresnˇeji vystihnout tvar agregovan´ ych prvk˚ u. Z´ aroveˇ n se také zvˇetˇsuje plocha agregovan´ ych oblast´ı. Dalˇs´ım problémem m˚ uˇze b´ yt vznik self-intersections. Existuje také redefinice konvexn´ı obálky zvaná rectangular convex hull, která dokáˇze zachovat pravé u ´hly. St´ ale vˇsak z˚ ustává problém vzniku topologicky nekorektn´ıch polygon˚ u. Zpr´ ava AGENT, DD3 uv´ ad´ı alogritmus REGNAULDA, 1998, kter´ y také pracuje s konvexn´ı ob´ alkou. Algoritmus funguje vˇzdy pro dvojici objekt˚ u, v pˇr´ıpadˇe nutnosti spojen´ı v´ıce prvk˚ u se agreguj´ı postupnˇe. Princip algoritmu uvád´ı obr. 3.3.

Obr. 3.3: Agregace konvexn´ı ob´ alkou, REGNAULD, 1998 (pˇrevzato z: AGENT, DD3, 2001, s. 39) Na u ´vod algoritmus vytv´ aˇr´ı konvexn´ı obálku, která je dále modifikována tak, aby lépe vystihovala p˚ uvodn´ı tvar budov. Jej´ı p˚ uvodn´ı hrana (a1 b1 ) m˚ uˇze b´ yt nahrazena bud’ hranami, které vzniknou prodlouˇzen´ım vnˇejˇs´ıch hran objekt˚ u (Ea1 , Eb1 ) a jejich protnut´ım (E1 na obr. 3.3b) nebo prodlouˇzen´ım a protnut´ım vnitˇrn´ıch hran Ia1 , Ib1 (I1 na obr. 3.3b). Obdobnˇe z´ıskáme dva nové body I2 a E2 pro nahrazen´ı hrany a2 b2 . Kombinac´ı tˇechto ˇctyˇr bod˚ u m˚ uˇzeme z´ıskat ˇctyˇri r˚ uzn´ a ˇreˇsen´ı (E1 ,E2 ; E1 , I2 ; I1 , E2 ; I1 , I2 ). Upˇrednostˇ novány jsou intern´ı body, ale v pˇr´ıpadˇe poruˇsen´ı topologie nebo minimáln´ı ˇs´ıˇrky agregované oblasti m˚ uˇze b´ yt vybr´ an extern´ı bod tak, aby minimalizoval zmˇenu plochy. WARE et al., 1995 navrhli algoritmus pro agregaci pomoc´ı Delaunay triangulace (obr. 3.4). Hrany vytvoˇrené triangulace rozdˇel´ı prostor mezi agregovan´ ymi prvky, kter´ y je následnˇe zaplnˇen.

18

Zpr´ ava d´ ale uv´ ad´ı dva algoritmy zaloˇzené na posunu prvk˚ u. Prvn´ı z nich navrhli v roce 1995 WARE et al., jeho princip je znázornˇen na obr. 3.5. Nejprve je zkonstruována Delaunay triangulace nad vrcholy agregovan´ ych prvk˚ u. Dále je urˇcena u ´seˇcka posunu, a to bud’ jako nejmenˇs´ı vzd´ alenost mezi prvky (obr. 3.5a) nebo jako nejkratˇs´ı hrana triangulace (obr. 3.5d). Podle hodnocen´ı zpr´ avy AGENT je z hlediska kartografické generalizace obecnˇe vhodnˇejˇs´ı pˇrisunut´ı objekt˚ u po u ´seˇcce urˇcené nejkratˇs´ı hranou triangulace. Na z´ akladˇe u ´ˇcelové funkce (cost function) je spoˇcteno, o kolik a jak se proporcion´ alnˇe objekty posunou (bud’ oba, nebo jen jeden). Následnˇe je provedeno vlastn´ı pˇrisunut´ı po u ´seˇcce tak, ˇze se objekty bud’ stˇretnou hranou a vertexem (obr. 3.5b) nebo vertexem a vertexem (obr. 3.5e). Na z´ avˇer je provedena rotace objekt˚ u a jejich spojen´ı (obr. 3.5c, 3.5f).

Obr. 3.4: Agregace pˇrid´ an´ım plochy, WARE et al., 1995 (pˇrevzato z: AGENT, DD3, 2001, s. 39) ˇ Také STAUFENBIEL, 1973 (podle STAMPACH, 2006) navrhoval podobn´ y pˇr´ıstup k agregaci budov. Po prostudov´ an´ı existuj´ıc´ıch map tvrdil, ˇze pˇrisunut´ı budov je nejˇcastˇejˇs´ım pˇr´ıpadem agregace, pokud je u ´hel natoˇcen´ı menˇs´ı neˇz 45◦ . Sám vˇsak nenavrhl ˇzádn´ y konkrétn´ı algoritmus, kter´ ym této agregace dosáhnout.

Obr. 3.5: Agregace posunut´ım, WARE et al., 1995 (pˇrevzato z: AGENT, DD3, 2001, s. 38) Druh´ y algoritmus zaloˇzen´ y na posunut´ı navrhl REGNAULD v roce 1998, jeho princip je na obr. 3.6. Agregace se dos´ ahne posouván´ım objekt˚ u, dokud se nepˇrekr´ yvaj´ı. K posunu docház´ı po vektoru nejkratˇs´ı vzdálenosti mezi objekty, která je urˇcena bud’ jako nejkratˇs´ı vzdálenost mezi vertexem a vertexem, vertexem a hranou nebo hranou a hranou. M´ıra posunu objekt˚ u je stejnˇe jako u pˇredchoz´ıho algoritmu urˇcena u ´ˇcelovou funkc´ı. Pˇrekr´ yván´ı objekt˚ u je zastaveno v okamˇziku, kdy je splnˇena podm´ınka nejmenˇs´ı ˇs´ıˇrky objektu (na obr. 3.6 spojnice AC). Oba tyto algoritmy v´ yraznˇe modifikuj´ı um´ıstˇen´ı a strukturu p˚ uvodn´ıch objekt˚ u a ani nedávaj´ı pˇr´ıliˇs dobré kartografické v´ ysledky. Dalˇs´ım problémem m˚ uˇze b´ yt sebeprot´ınán´ı (selfintersection). 19

Obr. 3.6: Agregace posunut´ım, REGNAULD, 1998 (pˇrevzato z: AGENT, DD3, 2001, s. 38) Problém agregace byl také ˇreˇsen s vyuˇzit´ım bufferu (napˇr. ESRI, 2000). Tento pˇr´ıstup vˇsak nen´ı kartograficky pˇr´ıliˇs pˇr´ızniv´ y. M˚ uˇze b´ yt pouˇzit pouze jeden buffer, kter´ y by zaplnil mezery mezi agregovan´ ymi objekty, nicménˇe t´ım se ne´ umˇernˇe zvyˇsuje plocha agregovan´ ych objekt˚ u. V manu´ alu ESRI je uveden pˇr´ıklad ˇreˇsen´ı jedn´ım vnˇejˇs´ım bufferem pro zaplnˇen´ı mezer a n´ asledné pouˇzit´ı vnitˇrn´ıho bufferu se stejn´ ym polomˇerem aplikovan´ ym na novˇe vznikl´ y objekt. Problémem je, ˇze opakovaná aplikace bufferu poskytuje nepˇrirozené kartografické v´ ysledky, viz obr. 3.7. Hlavn´ımi nev´ yhodami jsou: • pˇr´ıliˇsné zvˇetˇsen´ı plochy agregovan´ ych oblast´ı, • zaoblen´ı prav´ ych u ´hl˚ u, • vznik oblouˇck˚ u“ v m´ıstˇe spojen´ı p˚ uvodn´ıch polygon˚ u. ”

Obr. 3.7: (a, b) agregace jednoduch´ ym bufferem, (c, d, e) agregace vnˇejˇs´ım a vnitˇrn´ım bufferem (zpracov´ an´ı: ArcMap 9.3)

20

3.3.2

Region-based algoritmy

Algoritmus SU et al. vyuˇz´ıv´ a pro agregaci operátory matematické morfologie. Matematická morfologie vych´ az´ı z teorie mnoˇzin a je to vˇeda o tvaru a struktuˇre geometrick´ ych struktur, vytvoˇren´ a v 60. letech. Jej´ımi autory jsou francouzˇst´ı geostatistikové G. Matheron a J. Serra. Z´ akladn´ı morfologické operátory dilatace a eroze, jsou definovány následovnˇe: Dilatace: Eroze:

A ⊕ B = {a + b : a ∈ A, b ∈ B} = ∪b∈B Ab AΘB = {a : a + b ∈ A, b ∈ B} = ∩b∈B Ab

A je prvek, kter´ y chceme modifikovat a B je tzv. strukturn´ı element, kter´ y se po A pohybuje konvoluc´ı. V pˇr´ıpadˇe dilatace je oblast a rozˇs´ıˇrena a v pˇr´ıpadˇe eroze jsou zachovány pouze ty pixely, nad kter´ ymi je strukturn´ı element shodn´ y s A. Dalˇs´ımi dvˇema oper´ atory jsou otevˇren´ı a uzavˇren´ı, které jsou sloˇzitˇejˇs´ı, jedná se o kombinaci dilatace a eroze. Jsou definovány takto: Otevˇren´ı:

A ◦ B = (AΘB) ⊕ B

Uzavˇren´ı:

A • B = (A ⊕ B)ΘB

SU et al. v n´ avrhu svého algoritmu vyuˇzili právˇe kombinace dilatace a eroze. Pˇredkl´ adaj´ı jednoduch´ y algebraick´ y model: C = (A ⊕ B1 )ΘB2

Pokud jsou oba strukturn´ı elementy B1 a B2 shodné, jedná se o uzavˇren´ı. Velikost a tvar strukturn´ıch element˚ u jsou urˇceny pomˇerem p˚ uvodn´ıho a nového mˇeˇr´ıtka (velikost) a obecn´ ym tvarem generalizovan´ ych struktur (tvar – strukturn´ı element je pak ˇctverec, u ´hlopˇr´ıˇcka, koleˇcko atd). Uk´ azky funkˇcnosti pˇredloˇzeného algoritmu jsou na obr. 3.8 a 3.9. Proces agregace v ˇsirˇs´ım kontextu by mˇel b´ yt následován zjednoduˇsen´ım tvaru agregovan´ ych polygon˚ u (SU, 1997; LI, 2007). Po procesu agregace dojde ke spojen´ı bl´ızk´ ych nebo sousedn´ıch polygon˚ u, v´ ysledn´ y tvar vˇsak bude málokdy dostateˇcnˇe zjednoduˇsen´ y. Budou se na nˇem vyskytovat malé konkávn´ı nebo konvexn´ı tvary, které v daném mˇeˇr´ıtku nejsou d˚ uleˇzité. To ilustruje obr. 3.10. Funkcionalita algoritmu SU et al. z hlediska kartografické agregace na pˇredveden´ ych ukázkách je dobr´ a. Nicménˇe problémem tohoto algoritmu je komplikovaná zmˇena typu datové reprezentace (vektor-rastr-vektor). Konverze vektor-rastr nen´ı tolik sloˇzitá, je vˇsak ztrátov´ a. Pˇrevod z rastru na vektor je nav´ıc daleko sloˇzitˇejˇs´ı a v´ ypoˇcetnˇe nároˇcnˇejˇs´ı. Problematick´ ym se také m˚ uˇze jevit v´ ybˇer tvaru a velikosti strukturn´ıho elementu. Ide´ aln´ı by tak bylo navrhnout algoritmus, kter´ y by pracoval pouze s vektorov´ ymi daty bez nutnost´ı vz´ ajemn´ ych konverz´ı mezidatov´ ym reprezentacemi. 21

Obr. 3.8: Pˇr´ıklad agregace pravo´ uhl´ ych tvar˚ u (pˇrevzato z: SU et al., 1997, s. 242)

Obr. 3.9: Pˇr´ıklad agregace sloˇzitˇejˇs´ıch tvar˚ u (pˇrevzato z: SU et al., 1997, s. 243)

Obr. 3.10: Skupina polygon˚ u vstupuj´ıc´ıch do algoritmu (vlevo), po agregaci (pro mˇeˇr´ıtko 10x menˇs´ı, uprostˇred ) a n´ asledném zjednoduˇsen´ı tvaru (vpravo) (pˇrevzato z: SU et al., 1997, s. 241, 245)

22

4

´ DATOVE ´ STRUKTURY A ALGORITMY POMOCNE

Navrˇzen´ y algoritmus bude pouˇz´ıvat kombinaci v´ıce technik a postup˚ u. Uved’me zde struˇcnˇe funkcionalitu algoritmu, aby bylo zˇrejmé, k jakému u ´ˇcelu budou n´ıˇze uvedené struktury a algoritmy slouˇzit. Algoritmus na u ´vod vyhled´ avá budovy vhodné pro agregaci. V druhé fázi jsou budovy urˇcené pro agregaci nahrazeny topologickou kostrou zkonstruovanou metodou straight skeletonu. Straight skeleton je n´ aslednˇe redukován pouze na vnitˇrn´ı hrany a vrcholy, nazvˇeme tuto strukturu jako redukovan´ y straight skeleton. Nalezen´ım minimáln´ı kostry grafu, tvoˇreného d´ılˇc´ımi redukovan´ ymi straight skeletony, je urˇcen redukovan´ y skeleton polygonu reprezentuj´ıc´ıho agregovanou budovu. Tuto strukturu je vhodné jeˇstˇe generalizovat zjednoduˇsen´ım tvaru, napˇr. odstranˇen´ım nev´ yznamn´ ych vrchol˚ u. Posledn´ım krokem je zpˇetná rekonstrukce agregovaného polygonu z generalizovaného redukovaného skeletonu. Vlastn´ı n´ avrh algoritmu bude podrobnˇe rozebrán v kapitole 6, zde budou z formáln´ıho hlediska pops´ any pomocné struktury a algoritmy.

4.1

Voronoi diagram

Voronoi diagram bude vyuˇzit v prvn´ı ˇcásti algoritmu pro rychlé nalezen´ı navzájem bl´ızk´ ych budov. Na z´ akladˇe sousednosti Voronoi bunˇek budou definovány soused´ıc´ı polygony - ty budou podrobeny testov´ an´ı, jsou-li vhodné pro agregaci. Definice. Oznaˇcme euklidovskou vzdálenost mezi dvˇema body p, q jako dist(p, q). V rovinˇe pak plat´ı: dist(p, q) =

q (px − qx )2 + (py − qy )2

Necht’ P = {p1 , p2 , . . . , pn } je mnoˇzina bod˚ u v rovinˇe, tyto body jsou naz´ yvány gener´ atory. Voronoi diagram V (P ) mnoˇziny P je definován jako rozdˇelen´ı roviny do n bunˇek, jedna pro kaˇzd´ y gener´ ator p s takovou vlastnost´ı, ˇze bod q leˇz´ı v buˇ nce odpov´ıdaj´ıc´ı generátoru pi právˇe tehdy, plat´ı-li: dist(q, pi ) < dist(q, pj ) pro ∀pj ∈ P, j 6= i. (BERG et al., 2008, s. 148149)

23

Voronoi diagram tedy rozdˇeluje rovinu na Voronoi buˇ nky, pro které plat´ı, ˇze kaˇzd´ y bod v buˇ nce m´ a nejbl´ıˇze k centru (tj. ke generátoru) této buˇ nky, neˇz k centru jiné buˇ nky. Body leˇz´ıc´ı na hran´ ach maj´ı bl´ıˇze k v´ıce neˇz jednomu centru. Hrany jsou tvoˇreny u ´seˇckami, polopˇr´ımkami nebo pˇr´ımkami. Obecnˇe mohou b´ yt generátory Voronoi bunˇek i v´ıcerozmˇerné prvky (napˇr. linie, kruˇznice).

Obr. 4.1: Voronoi diagram (upraveno podle: BAYER, 2008) Konstrukce. V poˇc´ıtaˇcovém prostˇred´ı jsou Voronoi diagramy konstruovány v´ıce metodami, mezi nejˇcastˇeji pouˇz´ıvané patˇr´ı konstrukce Fortunov´ ym algoritmem a inkrementáln´ım vkládán´ım. Vytvoˇren´ a teselace b´ yvá ukládána v datové struktuˇre DCEL (Doubly Connected Edge List), kter´ a m´ a nav´ıc uloˇzen ukazatel na generátor buˇ nky. Inkrement´ aln´ı vkl´ ad´ an´ı. Algoritmus pracuje na principu postupného pˇridáván´ı bod˚ u do V (P ). Pˇredpokl´ adejme, ˇze jiˇz máme vytvoˇren´ y V (P ) pro prvn´ıch j−1 generátor˚ u a chceme vloˇzit gener´ ator pj (viz obr. 4.2). Jako prvn´ı je nutné naj´ıt generátor pi , v jehoˇz buˇ nce leˇz´ı pj . Pak je zkonstruov´ an bisektor w1 w2 mezi pi a pj kolm´ y na jejich spojnici tak, ˇze pj leˇz´ı od bisektoru vlevo. D´ ale se pokraˇcuje postupnou konstrukc´ı hran jako bisektor˚ u pj a kaˇzdého z m gener´ ator˚ u jeho sousedn´ıch bunˇek. Pak tato sekvence hran w1 w2 , w2 w3 , . . . , wm w1 tvoˇr´ı hranici Voroného polygonu generátoru pj . Na závˇer se smaˇzou vnitˇrn´ı hrany v novˇe vniklé buˇ nce. Problémem je vkl´ ad´ an´ı generátor˚ u, jejichˇz Voroného polygon má hrany konˇc´ıc´ı v nekoneˇcnu. Proto je na zaˇc´ atek celého algoritmu nav´ıc vytvoˇren simplex tvoˇren´ y tˇremi dalˇs´ımi generátory p1 , p2 , p3 , které leˇz´ı v dostateˇcné vzdálenosti od ostatn´ıch generátor˚ u. Jejich souˇradnice mohou b´ yt n´ asleduj´ıc´ı: √ 3 2 ] p1 = [xc , yc + 2h √ √ 3 6 3 2 p2 = [xc − , yc − ] 4h 4h √ √ 3 6 3 2 p3 = [xc + , yc + ] 4h 4h

24

odvozené ze souˇradnic min-max boxu h = max(xmax − xmin , ymax − ymin )

a tˇeˇziˇstˇe T [xc , yc ] mnoˇziny P . (OKABE et al., 2000)

Obr. 4.2: Konstrukce VD inkrementáln´ım vkládán´ım (vlevo), princip Fortunova algoritmu (vpravo) (pˇrevzato z: BERG et al., 2008, s. 152)

Obr. 4.3: site event (nahoˇre), circle event (dole) (pˇrevzato z: BERG et al., 2008, s. 153-154) Fortun˚ uv algoritmus. Tento algoritmus b´ yvá také oznaˇcován jako sweep line algoritmus (sweep line = zametac´ı pˇr´ımka). Základn´ım principem je posunován´ı zametac´ı pˇr´ımky l rovinou odshora dol˚ u a udrˇzov´ an´ı informace o Voronoi diagramu nad pˇr´ımkou l, kter´ y uˇz nem˚ uˇze + b´ yt zmˇenˇen gener´ atory pod pˇr´ımkou l. Oznaˇcme polorovinu nad l jako l , polorovinu pod l − jako l . Pro kaˇzd´ y bod q ∈ l+ a pro kaˇzd´ y generátor pi ∈ l− pak plat´ı: d(q, pi ) > d(q, l)

25

Nejbliˇzˇs´ı gener´ ator pi k bodu q pak leˇz´ı v polorovinˇe l+ , pokud plat´ı: d(q, pi ) ≤ d(q, l)

Mnoˇzina bod˚ u q, které splˇ nuj´ı tuto podm´ınku, tvoˇr´ı parabolu. Pro v´ıce generátor˚ u je tato mnoˇzina tvoˇrena parabolick´ ymi oblouky naz´ yvan´ ymi beach line, viz obr. 4.2. Zlomové body beach line pak kop´ıruj´ı hrany Voronoi diagramu. Vertexy a nové hrany Voronoi diagramu vznikaj´ı pohybem zametac´ı pˇr´ımky, kter´ y zp˚ usobuje zmˇenu topologie beach line. M˚ uˇze doj´ıt ke vzniku dvou ud´ alost´ı: • site event - zametac´ı pˇr´ımka doraz´ı k dalˇs´ımu generátoru, ˇc´ımˇz se vytváˇr´ı nov´ y parabolick´ y oblouk definuj´ıc´ı hranu Voronoi buˇ nky (obr. 4.3 nahoˇre) • circle event - doch´ az´ı k z´ aniku parabolického oblouku, ˇc´ımˇz vzniká bod q jako nov´ y vertex Voronoi diagramu (obr. 4.3 dole). Pro tento bod plat´ı d(q, pi ) = d(q, pj ) = d(q, pk ) = d(q, l)

je tedy stˇredem kruˇznice tvoˇrené body pi , pj , pk . (BERG et al., 2008) ˇ Casov´ a sloˇ zitost. Algoritmus inkrementáln´ım vkládán´ım má horn´ı ˇcasovou sloˇzitost O(n2 ), Fortun˚ uv algoritmus O(n log n). Struktura DCEL. Struktura DCEL slouˇz´ı k uloˇzen´ı geometrick´ ych, topologick´ ych a pˇr´ıpadn´ ych dalˇs´ıch informac´ı o rozdˇelen´ı roviny. Obsahuje tˇri kolekce záznam˚ u: jednu pro vrcholy, druhou pro hrany a tˇret´ı pro plochy. Kaˇzdá hrana je vpodstatˇe uloˇzena dvakrát ve formˇe tzv. half-edges (polohran). Jedn´ a se o navzájem opaˇcnˇe orientované u ´seˇcky ~e a T win(~e). M˚ uˇzeme tak mluvit o jejich poˇcáteˇcn´ım a koncovém vrcholu, kdy Origin(~e) = Destination(T win(~e)) a naopak. Jejich orientace je taková, ˇze vnitˇrek plochy (face), kterou ohraniˇcuj´ı, leˇz´ı vˇzdy vlevo od polohrany. D´ıry maj´ı orientaci opaˇcnou. Geometrické a topologické vlastnosti rozdˇelen´ı roviny jsou pak v DCEL uloˇzeny následovnˇe: • z´ aznam vrcholu v nese informace o sv´ ych souˇradnic´ıch a pointer na polohranu, j´ıˇz je poˇc´ ateˇcn´ım bodem, • z´ aznam plochy f nese pointer na nˇejakou svoji vnˇejˇs´ı polohranu, v pˇr´ıpadˇe neuzavˇrené plochy je hodnota pointeru NULL. Dále má uloˇzen seznam vnitˇrn´ıch komponent (dˇer), pro kaˇzdou d´ıru je udrˇzov´ an pointer na nˇejakou jej´ı polohranu, • z´ aznam polohrany ~e m´ a uloˇzen ukazatel k poˇcáteˇcn´ım bodu polohrany Origin(~e), ukazatel na opaˇcnou polohranu T win(~e) a pointer na inciduj´ıc´ı plochu. Dále jsou uloˇzeny ukazatele na pˇredchoz´ı a následuj´ıc´ı hrany leˇz´ıc´ı na hranici inciduj´ıc´ı plochy. (BERG et al., 2008) 26

Vyuˇ zit´ı Voronoi diagram˚ u. V kartografii a GIS jsou Voronoi diagramy (stejnˇe jako Delaunay triangulace, s nimiˇz maj´ı tˇesn´ y vztah) ˇcasto vyuˇz´ıvány jako pomocné geometrické struktury. V r´ amci GIS se jedná pˇredevˇs´ım o urˇcován´ı spádov´ ych oblast´ı, nalezen´ı vˇsech soused˚ u dané oblasti nebo o interpolaci metodou natural neighbour. V rámci kartografické generalizace jsou voronoi diagramy jedn´ım z moˇzn´ ych zp˚ usob˚ u urˇcen´ı geografického kontextu (napˇr. Basaraner a Selcuk, 2004) nebo urˇcen´ı sousednosti (napˇr. Steihauer et al., 2001, podle LI et al., 2004).

4.2

Minim´ aln´ı vzd´ alenost dvou polygon˚ u

Po urˇcen´ı dvou budov jako navzájem soused´ıc´ıch bude algoritmus testovat, má-li doj´ıt k jejich agregaci. Jedn´ım z hlavn´ıch kritéri´ı je minimáln´ı vzdálenost mezi nimi. Otázka v´ ypoˇctu vzdálenosti je ˇreˇsena vyuˇzit´ım analytické geometrie. Oznaˇcme oba analyzované polygony P , Q, viz obr. 4.4a. Problém vzájemné polohy je pˇreveden na v´ ypoˇcet minim´ aln´ı vzdálenosti dvou u ´seˇcek AB, EF , kde AB ∈ P a EF ∈ Q, které tvoˇr´ı hrany testovan´ ych polygon˚ u (obr. 4.4b).

Obr. 4.4: V´ ypoˇcet vzdálenosti dvou polygon˚ u −→ −−→ Urˇ cen´ı orientace vektor˚ u. Oznaˇcme vektor u = AC = (ux , uy ), vektor v = AB = (vx , vy ). Pokud je u ´hel mezi vektory ~u, ~v , mˇeˇren´ y proti smˇeru hodinov´ ych ruˇciˇcek, menˇs´ı neˇz π, pak je orientace vektor˚ u kladn´ a, pokud je vˇetˇs´ı neˇz π, je orientace vektor˚ u záporná. V´ ypoˇcet orientace dvou vektor˚ u lze vyuˇz´ıt pro anal´ yzu vzájemné polohy bodu a pˇr´ımky. Necht’ C pˇredstavuje bod, jehoˇz polohu analyzujeme vzhledem k pˇr´ımce urˇcené body AB, viz obr. 4.4c. Pak plat´ı u u x y t= vx vy

   

t<0

  

t>0

C leˇz´ı vlevo od AB

t = 0 C leˇz´ı na AB

27

C leˇz´ı vpravo od AB

Urˇ cen´ı vzd´ alenosti dvou u ´seˇ cek. Minimáln´ı vzdálenost dvou u ´seˇcek AB, EF (viz obr. 4.4b) lze urˇcit z n´ asleduj´ıc´ıho vztahu: dmin (AB, EF ) = min(d(A, EF ), d(B, EF ), d(E, AB), d(F, AB))

Pˇri v´ ypoˇctu vzd´ alenosti u ´seˇcek je tˇreba rozliˇsit, zda testovan´ y bod (vezmˇeme napˇr. pˇr´ıpad d(A, EF ) leˇz´ı v p´ asu vymezeném normálami u ´seˇcky EF , nebo v nˇekterém z obou krajn´ıch −→ −−→ −→ → pás˚ u. K tomu je vyuˇzit test orientace vektor˚ u− n− EF = (−uy , ux ), EA a nEF , F A. Pokud −→ −→ t(~n, EA) < 0 AND t(~n, F A) < 0, −→ −→ t(~n, EA) > 0 AND t(~n, F A) < 0, −→ −→ t(~n, EA) > 0 AND t(~n, F A) > 0,

A ∈ εL (lev´ y pás) A ∈ εS (stˇredn´ı pás) A ∈ εP (prav´ y pás)

Vzdálenost d(A, EF ), kde A = [xA , yA ] je pak vypoˇctena následovnˇe. Pokud −→ A ∈ εL : d(A, EF ) = |EA| |axa · bya · c| √ a2 + b2 −→ A ∈ εP : d(A, EF ) = |F A| A ∈ εS : d(A, EF ) =

kde a, b, c jsou koeficienty obecné rovnice pˇr´ımky urˇcené body EF . Urˇ cen´ı vzd´ alenosti dvou polygon˚ u. Minimáln´ı vzdálenost mezi polygony P , Q je pak urˇcena n´ asledovnˇe:   dmin (P, Q) = min  

min(dmin (p0 p1 , q0 q1 ), . . . , dmin (pi−1 p0 , q0 q1 )),



   min(dmin (p0 p1 , qj−1 q0 ), . . . , dmin (pi−1 p0 , qj−1 q0 )) ...

kde i je poˇcet vrchol˚ u polygonu P , j je poˇcet vrchol˚ u polygonu Q. ˇ ˇ Casov´ a sloˇ zitost. Casov´ a sloˇzitost algoritmu je O(m · n), kde m je poˇcet vrchol˚ u polygonu P , n je poˇcet vrchol˚ u polygonu Q.

28

4.3

Straight skeleton

Jak jiˇz bylo uvedeno v´ yˇse, straight skeleton bude vyuˇzit nejprve pro redukci polygon˚ u budov na jejich topologickou kostru. V této souvislosti definujeme novou datovou strukturu zvanou redukovan´ y straight skeleton (viz ˇcást 4.4). Závˇereˇcn´ ym krokem navrˇzeného algoritmu je zpˇetná rekonstrukce polygonu z redukovaného straight skeletonu. Jedn´ a se o inverzn´ı postup ke konstrukci straight skeletonu, kter´ y bude vyuˇz´ıvat datové struktury a funkc´ı algoritmu Felkela a Obdrˇzálka, 1998. Topologick´ a kostra. Definujme uzavˇren´ y ohraniˇcen´ y polygon P v R2 . Topologická kostra je v´ ysledkem procesu zvaného skeletonizace. Skeletonizace provád´ı dekompozici P na posloupnost jednoduˇsˇs´ıch 1D entit. Straight skeleton, pˇredstaven´ y O. AICHHOLZEREM a F. AURENHAMMEREM, 1996, je jednou z metod konstrukce topologické kostry polygonu. Topologická kostra je prostorovou redukc´ı prvku tvoˇrenou posloupnost´ı u ´seˇcek ˇci kˇrivek, u straight skeletonu pouze u ´seˇcek. Zachov´ av´ a tvarové a geometrické charakteristiky polygon˚ u, a je tak vhodnou strukturou pro automatizovanou kartografickou generalizaci (BAYER, 2008). Definice. Definujme tzv. smrˇst’ovac´ı proces. Jedná se o proces, kdy se posunuj´ı vrcholy polygonu P po os´ ach u ´hl˚ u (bisektorech) inciduj´ıc´ıch hran smˇerem dovnitˇr konstantn´ı rychlost´ı, dokud nen´ı plocha polygonu nulová. Straight skeleton S(P ) je pak definován jako sjednocen´ı ˇcást´ı os u ´hl˚ u (tj. bisektor˚ u), po kter´ ych se pohybuj´ı vrcholy P bˇehem smrˇst’ovac´ıho procesu. Tyto u ´seˇcky jsou oznaˇcov´ any jako segmenty (hrany) skeletonu, jejich koncové body, které nejsou vrcholy P , jsou uzly skeletonu. Kaˇzd´ y uzel odpov´ıdá události edge, split nebo vertex event. Oblasti vymezené hranic´ı polygonu a segmenty skeletonu jsou naz´ yvány ploˇskami (faces).

Obr. 4.5: Princip tvorby straight skeletonu

29

Konstrukce. Pˇri smrˇst’ovac´ım procesu docház´ı k r˚ uzn´ ym zmˇenám v topologii polygonu. Tyto zmˇeny mohou b´ yt troj´ıho typu, jejich ilustrace je na obr. 4.6: • z´ anik hrany (edge event) - délka hrany se smrˇst’ován´ım zmenˇs´ı na nulu (tj. bod) a zp˚ usob´ı, ˇze jej´ı inciduj´ıc´ı hrany se stanou navzájem soused´ıc´ımi, • rozdˇ elen´ı hrany (split event) - vnitˇrn´ı nekonvexn´ı u ´hel se stˇretne s posunuj´ıc´ı se protilehlou hranu polygonu a dojde tak k jej´ımu rozdˇelen´ı, • vertex event - ud´ alost definovaná aˇz v roce 1999 EPPSTEINEM a ERICKSONEM, pˇri n´ıˇz doch´ az´ı ke stˇretnut´ı dvou nebo v´ıce nekonvexn´ıch vrchol˚ u polygonu.

Obr. 4.6: (a) dva souˇcasné edge eventy, (b) split event, (c) vertex event, (d) degenerovan´ y straight skeleton (upraveno podle: EPPSTEIN a ERICKSON, 1999, s. 8) V pˇr´ıpadˇe edge event nebo split event vznikne jedna nebo v´ıce nov´ ych konvexn´ıch podoblast´ı. V pˇr´ıpadˇe vertex event dojde k rozpadu na dvˇe nebo v´ıce podoblast´ı, z nichˇz nˇekteré mohou b´ yt opˇet nekonvexn´ı. Podoblasti jsou zdrojem nov´ ych os u ´hl˚ u a jsou dále zpracováv´ any. V pˇr´ıpadˇe pravideln´ ych n-´ uheln´ık˚ u je skeleton degradován na jedin´ y uzel vysˇsˇs´ıho stupnˇe (obr. 4.6d). Poˇ rad´ı vzniku ud´ alost´ı. Kl´ıˇcov´ ym problémem správné konstrukce straight skeletonu je urˇcen´ı poˇrad´ı vzniku jednotliv´ ych událost´ı. Vznik událost´ı (a tedy i uzl˚ u skeletonu) je jednoznaˇcnˇe urˇcen délkou pohybu vrcholu po ose u ´hlu. Události jsou ukládány v prioritn´ı frontˇe, která zajiˇst’uje spr´ avné poˇrad´ı jejich zpracován´ı. Algoritmy, které ˇreˇs´ı konstrukci straight skeletonu, se pak liˇs´ı pˇredevˇs´ım zp˚ usobem detekce a udrˇzován´ım událost´ı. Implementace algoritmu. Algoritmus pro konstrukci straight skeletonu implementovali ˇ ALEK, ´ napˇr. AICHHOLZER a AURENHAMMER, 1996; FELKEL a OBDRZ 1998 nebo CACCIOLA, 2004. Aichholzer a Aurenhammer vyuˇz´ıvaj´ı triangulaci a prioritn´ı frontu. Pro vnitˇrek zmenˇsovaného polygonu je provedena triangulace. Zánik troj´ uheln´ıka vede ˇ ke zmˇenˇe topologie. Casy z´ aniku troj´ uheln´ık˚ u jsou uloˇzeny v prioritn´ı frontˇe, která je postupnˇe zpracov´ av´ ana. Felkel a Obdrˇzálek vyuˇz´ıvaj´ı datovou strukturu SLAV (set of circular lists of active vertices), kter´ a uchovává ukazatele (pointery) na hrany p˚ uvodn´ıho polygonu. Cacciola implementoval straight skeleton pro open source knihovnu CGAL (Computional Geometry Algorithms Library). Vycház´ı z algoritmu Felkela a Obdrˇzálka, je vˇsak obohacena o vertex event, kter´ y v p˚ uvodn´ı implementaci chyb´ı. Vyuˇz´ıvá datové struktury HDS (Halfedge Data Structure), kter´ a je souˇc´ ast´ı CGAL knihovny. 30

Algoritmus Felkela a Obdrˇ z´ alka Jak jiˇz bylo uvedeno, algoritmus vyuˇz´ıvá datové struktury SLAV (set of circular list of active vertices - sada kruhových seznam˚ u aktivn´ıch vrchol˚ u). Tato struktura je tvoˇren´ a kruhov´ ymi seznamy vrchol˚ u (LAV) pro kaˇzd´ y polygon, d´ıru polygonu a polygony vzniklé v pr˚ ubˇehu skeletonizace. Konvexn´ı polygon je tak pˇredstavován pouze jednou strukturou LAV, nekonvexn´ı polygon nebo polygon s d´ırami v´ıce strukturami. Kaˇzd´ y vrchol ve SLAV má pˇriˇrazeny ukazatele na oba soused´ıc´ı (tj. pˇredchoz´ı a následuj´ıc´ı) vrcholy v seznamu (LAV). Konstrukce se liˇs´ı pro konvexn´ı a nekonvexn´ı polygony. V pˇr´ıpadˇe konvexn´ıch polygon˚ u m˚ uˇze doj´ıt pouze k edge event, v pˇr´ıpadˇe nekonvexn´ıch i ke split event (jak bylo uvedeno, algoritmus nezahrnuje vertex event). Konstrukce pro konvexn´ı polygony Za pˇredpokladu, ˇze vrcholy a hrany polygonu jsou orientovány proti smˇeru hodinov´ ych ruˇciˇcek, prob´ıh´ a algoritmus n´ asledovnˇe. 1. Inicializace: (a) vloˇz vˇsechny vrcholy V1 , V2 , . . . , Vn do dvojitého kruhového seznamu (LAV) uloˇzeného ve SLAV. Vˇsechny vrcholy jsou oznaˇceny jako aktivn´ı - nezpracované. (b) pro kaˇzd´ y vrchol Vi v LAV pˇridej pointery (ukazatele) na jeho incidentn´ı hrany ei−1 = Vi−1 Vi a ei = Vi Vi+1 , a vypoˇcti osu u ´hlu bi tˇemito hranami sevˇreného. (c) pro kaˇzd´ y vrchol Vi vypoˇcti nejbliˇzˇs´ı pr˚ useˇc´ık jeho osy u ´hlu bi s osami u ´hl˚ u bi−1 , bi+1 pˇrilehl´ ych vrchol˚ u a pokud existuje, uloˇz ho do prioritn´ı fronty v závislosti na vzd´ alenosti od hrany ei . Pro kaˇzd´ y pr˚ useˇc´ık Ii uloˇz ukazatele na vrcholy Va , Vb , z nichˇz vych´ az´ı prot´ınaj´ıc´ı se osy u ´hl˚ u. 2. Dokud nen´ı prioritn´ı fronta s pr˚ useˇc´ıky I pr´ azdn´ a, prov´ adˇej n´ asleduj´ıc´ı: (a) vezmi pr˚ useˇc´ık I s nejvˇetˇs´ı prioritou, (b) pokud jsou vrcholy/uzly Va a Vb , na které ukazuje I, oznaˇcené jako zpracované, pokraˇcuj krokem 2, pokud ne, docház´ı k edge event a hrana zaniká: (c) pokud v LAV plat´ı, ˇze pˇredch˚ udce vrcholu pˇredcházej´ıc´ı Va odpov´ıdá vrcholu Vb , pˇridej do skeletonu tˇri segmenty Va I, Vb I, Vc I, kde Vc je pˇredch˚ udce Va a zároveˇ n n´ asledn´ık Vb (v LAV zb´ yvaj´ı posledn´ı tˇri vrcholy) a pokraˇcuj krokem 2. V opaˇcném pˇr´ıpadˇe pˇridej pouze hrany Va I, Vb I a modifikuj LAV následovnˇe: • oznaˇc vrcholy Va , Vb jako zpracované, • vytvoˇr nov´ y vrchol V na m´ıstˇe I, vloˇz ho do LAV a pˇridej ukazatele na pˇrilehlé hrany ea , eb , • spoˇcti osu u ´hlu b mezi ea , eb a vypoˇcti a uloˇz pr˚ useˇc´ık I stejnˇe jako v kroku 1c). 31

ˇ ALEK, ´ Obr. 4.7: Datov´ a struktura LAV (upraveno podle: FELKEL a OBDRZ 1998, s. 4) Konstrukce pro nekonvexn´ı polygony Princip konstrukce je podobn´ y konstrukci pro konvexn´ı polygony. Pro pr˚ useˇc´ıky I v prioritn´ı frontˇe je nav´ıc ukl´ ad´ ana informace o tom, zda se jedná o split event nebo edge event. Pˇr´ıtomnost nekonvexn´ıho vrcholu m˚ uˇze vést k rozdˇelen´ı hrany, ale nemus´ı. Na obr. 4.8a bod A pˇredstavuje edge event, kdeˇzto bod B split event. Hlavn´ım problémem je urˇcen´ı souˇradnic bodu B. Ten m´ a tu vlastnost, ˇze leˇz´ı ve stejné vzdálenosti od protilehlé hrany vrcholu V i od prodlouˇzen´ı hran, které inciduj´ı s vrcholem V (obr. 4.8a). Problém je, ˇze nezn´ ame protilehlou hranu e. Pro hrany se testuje existence pr˚ useˇc´ıku hrany ei , resp. pˇr´ımky, kter´ a hranu obsahuje, s bisektorem u ´hlu vrcholu V a zda potenciáln´ı bod Bi leˇz´ı v oblasti vymezené hranou ei a bisektory vych´ azej´ıc´ıch z inciduj´ıc´ıch vrchol˚ u (obr. 4.8b). Samotn´ y vrchol Bi je urˇcen jako pr˚ useˇc´ık os u ´hl˚ u troj´ uheln´ıka, kter´ y vznikne z hrany ei (resp. jej´ı pˇr´ımky) a prodlouˇzen´ı hran inciduj´ıc´ıch s vrcholem V (obr. 4.8c). V´ ysledn´ y bod B je pak vybr´ an z mnoˇziny bod˚ u Bi jako ten s nejmenˇs´ı vzdálenost´ı od V . Pokud je urˇceno, ˇze bod B odpov´ıdá události split event, je nutné provést zmˇenu v LAV, nebot’ dojde k rozdˇelen´ı polygonu na dvˇe ˇcásti. LAV se rozpadne na dvˇe nové struktury a do kaˇzdé jsou souˇradnice bodu B uloˇzeny jako nové uzly.

Obr. 4.8: Konstrukce straight skeletonu pro nekonvexn´ı polygony (upraveno podle: FELKEL ˇ ALEK, ´ a OBDRZ 1998, s. 5)

32

1. Inicializace: (a) proved’ stejné operace jako v pˇr´ıpadˇe konvexn´ıch polygon˚ u. Pro nekonvexn´ı vrcholy nav´ıc spoˇcti pr˚ useˇc´ıky s protilehl´ ymi hranami a do prioritn´ı fronty uloˇz pr˚ useˇc´ık I s informac´ı o typu události. 2. Dokud nen´ı prioritn´ı fronta pr´ azdn´ a, prov´ adˇej n´ asleduj´ıc´ı: (a) vezmi pr˚ useˇc´ık I z prioritn´ı fronty. Pokud se jedná o edge event, pokraˇcuj jako v pˇr´ıpadˇe konvexn´ıch polygon˚ u. V opaˇcném pˇr´ıpadˇe postupuj v tomto algoritmu. (b) pokud je vrchol/uzel V , na kter´ y ukazuje I, oznaˇcen´ y jako zpracovan´ y, pokraˇcuj krokem 2, v opaˇcném pˇr´ıpadˇe pˇridej ke kostˇre hranu V I a proved’ zmˇeny ve SLAV: • oznaˇc vrchol V jako zpracovan´ y, • LAV se rozpadne na dvˇe ˇcásti, do kaˇzdé vloˇz jeden vrchol (V1 , V2 ) se souˇradnicemi shodn´ ymi s bodem I. Vrchol V1 vloˇz mezi pˇredch˚ udce V a koncov´ y bod protilehlé hrany, vrchol V2 vloˇz mezi následn´ıka V a poˇcáteˇcn´ı bod protilehlé hrany, ˇc´ımˇz dojde k rozdˇelen´ı polygonu na dvˇe ˇcásti. Pro oba vrcholy uloˇz ukazatele na odpov´ıdaj´ıc´ı hrany, • pro vrcholy V1 , V2 spoˇc´ıtej bisektory a odpov´ıdaj´ıc´ı pr˚ useˇc´ıky a uloˇz je do prioritn´ı fronty jako v kroku 1c) spoleˇcnˇe s typem události. ˇ ˇ Casov´ a sloˇ zitost. Casov´ a sloˇzitost algoritmu je O(n · m + n log n), kde n je celkov´ y poˇcet vrchol˚ u polygonu a m je poˇcet nekonvexn´ıch vrchol˚ u. Vyuˇ zit´ı straight skeletonu. V oblasti kartografické generalizace lze skeleton vyuˇz´ıt napˇr. pˇri generalizaci prostorovou redukc´ı (napˇr. generalizace ˇr´ıˇcn´ıch tok˚ u nebo cestn´ıch s´ıt´ı, HAUˇÍP, 2007). NERT a SESTER, 2008) nebo rozdˇelen´ı polygonu polygon˚ um sousedn´ım (S Mezi dalˇs´ı aplikace patˇr´ı napˇr. n´ astroje pro umist’ován´ı popis˚ u nebo rekonstrukci tvar˚ u stˇrech.

33

4.4

Redukovan´ y straight skeleton

Redukovan´ y straight skeleton RS(P ) je novˇe definovanou strukturou, která je podmnoˇzinou straight skeletonu S(P ). V algoritmu bude vyuˇzit jako vstup pro nalezen´ı minimáln´ı kostry agregovaného polygonu. Nalezen´ a minimáln´ı kostra je pak redukovan´ ym straight skeletonem agregovaného polygonu. Z redukovaného skeletonu bude provedena zpˇetná rekonstrukce agregovaného polygonu. Definice. Necht’ S(P ) = v, e je straight skeleton polygonu P , kde v je mnoˇzina vrchol˚ u skeletonu, e je mnoˇzina hran skeletonu. Oznaˇcme vI podmnoˇzinu mnoˇziny v takovou, ˇze je tvoˇrena pouze vnitˇrn´ımi vrcholy skeletonu (uzly). Obdobnˇe oznaˇcme eI podmnoˇzinu mnoˇziny e takovou, ˇze je tvoˇrena pouze vnitˇrn´ımi hranami skeletonu. Redukovan´ y straight skeleton RS(P ) polygonu P pak definujme jako: RS(P ) = {vI , eI }

Obr. 4.9: (a) straight skeleton, (b) redukovan´ y straight skeleton Konstrukce. Z´ akladem konstrukce redukovaného straight skeletonu je konstrukce straight skeletonu (viz kap. 4.3). Pˇrid´ an´ım pomocného booleovského atributu (napˇr. inner ) uzl˚ um konstruovaného straight skeletonu m˚ uˇzeme odliˇsit jeho vnitˇrn´ı a vnˇejˇs´ı uzly:

pro vnitˇrn´ı uzly

inner = true

pro vnˇejˇs´ı uzly

inner = f alse

∀ uzly u s atributem inner == true a ∀ hrany e spojuj´ıc´ı uzly u tvoˇr´ı hledan´ y redukovan´ y straight skeleton.

34

4.5

Grafov´ e algoritmy

Grafové algoritmy, zejména algoritmy pro nalezen´ı minimáln´ı kostry grafu a prohled´ av´ an´ı do hloubky, budou v navrˇzeném algoritmu jednˇemi ze stˇeˇzejn´ıch technik. Minimáln´ı kostra grafu bude vyuˇzita pro konstrukci redukovaného skeletonu agregovaného polygonu z jednotliv´ ych redukovan´ ych skeleton˚ u agregovan´ ych budov. Prohledáván´ı do hloubky se uplatn´ı pˇri vˇetˇs´ım poˇctu d´ılˇc´ıch operac´ı. Mezi nˇe bude patˇrit pˇredevˇs´ım urˇcen´ı skupin polygon˚ u pro agregaci a urˇcen´ı spr´ avného ˇrazen´ı a orientace vrchol˚ u redukovaného skeletonu agregovaného polygonu. 4.5.1

Minim´ aln´ı kostra grafu

Z hlediska teorie graf˚ u m˚ uˇzeme na skeleton hledˇet jako na neorientovan´ y graf, nav´ıc strom. S grafy je sv´ az´ ano velké mnoˇzstv´ı pojm˚ u, zde uved’me ty, které maj´ı pˇr´ımou souvislost s ˇreˇsen´ım diplomové pr´ ace: neorientovan´ y graf, spojová reprezentace grafu, diskrétn´ı graf, podgraf, faktor grafu, souvislost, les, strom, kostra grafu, minimáln´ı kostra grafu. Nˇekteré ze struktur ilustruje obr. 4.10. Neorientovan´ y graf. Necht’ E, V jsou libovolné disjunktn´ı mnoˇziny a ε : E 7→ V ⊗ V zobrazen´ı. V ⊗ V je mnoˇzina vˇsech neuspoˇrádan´ ych dvojic [u, v]; u, v ∈ V . Neorientovan´ ym grafem naz´ yv´ ame uspoˇr´ adanou trojici G = (V, E, ε), prvky mnoˇziny E jsou hranami grafu G, prvky mnoˇziny V uzly grafu G a zobrazen´ı ε incidenc´ı grafu G. Incidence ε grafu pˇriˇrazuje ´ R, ˇ 2004, s. 18) kaˇzdé jeho hranˇe neuspoˇr´ adanou dvojici uzl˚ u. (KOLA Spojov´ a reprezentace grafu. Základn´ı forma spojové reprezentace neorientovaného grafu G = (V, E, ε) sest´ av´ a z pole Adj obsahuj´ıc´ı |V | odkaz˚ u na seznamy soused˚ u jednotliv´ ych uzl˚ u z mnoˇziny V . Pro kaˇzd´ y uzel v ∈ V obsahuje spojov´ y seznam Adj[v] jeden záznam pro kaˇzdou neorientovanou hranu e = [v, w] ∈ E s druh´ ym krajn´ım uzlem w. Záznam typicky obsahuje ´ R, ˇ 2004, s. 72) identifikaci (ˇc´ıslo) uzlu w. (KOLA Diskr´ etn´ı graf. Diskrétn´ı graf je takov´ y graf, jehoˇz mnoˇzina E je prázdná. Podgraf. Graf G0 je podgrafem grafu G, vznikne-li z grafu G vynechán´ım nˇejak´ ych (nebo ˇz´ adn´ ych) vrchol˚ u a hran. Podgraf mus´ı b´ yt také grafem: spolu s kaˇzdou hranou, kter´ a je v podgrafu, tam mus´ı b´ yt i jej´ı krajn´ı vrcholy. (DEMEL, 2002, s. 18) Faktor grafu. Faktor grafu G0 je speciáln´ım podgrafem grafu G, kter´ y vznikne vynech´ an´ım 0 nˇekter´ ych (nebo ˇz´ adn´ ych) jeho hran, tj. plat´ı-li V (G) = V (G ). (DEMEL, 2002, s. 18) Souvislost, komponenta souvislosti. Graf naz´ yváme souvisl´ ym, jestliˇze kaˇzdé jeho dva vrcholy jsou spojeny neorientovanou cestou. Komponenta souvislosti grafu G je kaˇzd´ y podgraf H grafu G, kter´ y je souvisl´ y a kter´ y je maximáln´ı s touto vlastnost´ı, tj. nen´ı ˇcást´ı vˇetˇs´ıho souvislého podgrafu. (DEMEL, 2002, s. 57) 35

Obr. 4.10: (a) Neorientovan´ y graf, (b) podgraf, (c) cesta grafu, (d) faktor grafu, (e) les tvoˇren´ y stromy (komponentami souvislosti), (f ) kostra grafu Les a strom. Les je graf, kter´ y neobsahuje kruˇznici. Kruˇznice je neorientovaná uzavˇren´ a cesta. Cesta je neorientovan´ y sled, v nˇemˇz se neopakuje ˇzádn´ y vrchol. Sled je posloupnost vrchol˚ u a hran v0 , e1 , v1 , e2 , v2 , . . . , ek , vk , kde kaˇzdá hrana ei spojuje vrcholy vi−1 , vi . Strom je graf, kter´ y neobsahuje kruˇznici a nav´ıc je souvisl´ y. (DEMEL, 2002, s. 19, s. 20, s. 58) Kostra grafu. Faktor grafu G, kter´ y je stromem, naz´ yváme kostrou grafu. Kaˇzd´ y souvisl´ y graf m´ a kostru. (DEMEL, 2002, s. 58) Minim´ aln´ı kostra grafu. Necht’ je dán souvisl´ y neorientovan´ y graf G = hE, V i + s nezáporn´ ym ohodnocen´ım hran ω : E 7→ R . Problém minimáln´ı kostry grafu G spoˇc´ıv´ a P v nalezen´ı takové jeho kostry T = hEu , V i, která splˇ nuje následuj´ıc´ı podm´ınku: e∈Eu ω(e) ´ ˇ je minim´ aln´ı. (KOLAR, 2004, s. 98) Hledat minim´ aln´ı kostru grafu má smysl pouze tehdy, jsou-li hrany grafu ohodnocené. Vˇsechny kostry daného grafu totiˇz obsahuj´ı stejn´ y poˇcet hran: nH = |u| − 1

kde u je poˇcet vrchol˚ u. Pokud nejsou hrany ohodnocené, nelze urˇcit, která z nich je nejvhodnˇejˇs´ı pro dan´ y u ´ˇcel (napˇr. minimáln´ı). Nicménˇe i v pˇr´ıpadˇe ohodnocen´ ych hran m˚ uˇze doj´ıt k tomu, ˇze minim´ aln´ı kostra nen´ı jednoznaˇcnˇe urˇcena. Hled´ an´ı minim´ aln´ı kostry grafu spojován´ım podkoster s minimáln´ım ohodnocen´ım je bl´ızké postupu agregace. Navrˇzen´ y algoritmus právˇe krokem hledán´ı minimáln´ı kostry grafu agregaci prov´ ad´ı (viz ˇc´ ast 6.2). 36

´ Vyuˇ zit´ı. Ulohy, které vyuˇz´ıvaj´ı hledán´ı minimáln´ı kostry, maj´ı za c´ıl spojit mnoˇzstv´ı bod˚ u (m´ıst) cestou nejmenˇs´ıch n´ aklad˚ u. Pˇr´ıkladem m˚ uˇze b´ yt oblast dopravy (napˇr. nalezen´ı nejkratˇs´ı cesty pro posyp silnic ve mˇestˇe), energetiky (napˇr. návrh s´ıtˇe pro rozvod elektˇriny tuto u ´lohu ˇreˇsil O. Bor˚ uvka pˇri n´ avrhu elektrick´ ych s´ıt´ı v polovinˇe 20. let 20. stolet´ı) nebo telekomunikac´ı. Hled´ an´ı minim´ aln´ı kostry grafu. Z algoritmického hlediska lze ke konstrukci minim´ aln´ı kostry (Minimum Spanning tree - MST ) pˇristupovat v´ıce zp˚ usoby. Vˇsechny varianty pracuj´ı iteraˇcnˇe: postupnˇe konstruuj´ı podgrafy daného grafu tak, aby se pˇribliˇzovaly hledané minim´ aln´ı kostˇre. Pˇribliˇzov´ an´ı se m˚ uˇze dosáhnout bud’ vypouˇstˇen´ım hran v´ ychoz´ıho grafu, pˇridáv´ an´ım hran k podgrafu, kter´ y je na poˇcátku prázdn´ y, nebo v´ ymˇenou hran v nˇejaké v´ ychoz´ı kostˇre. Z hlediska efektivity je nejv´ yhodnˇejˇs´ı varianta pˇridáván´ı hran k podgrafu. Zaˇc´ın´ a se prázdnou mnoˇzinou hran T , ke které se pˇridávaj´ı dalˇs´ı vhodné hrany. Tento pˇr´ıstup ilustruje alg. 4.1. Z´ akladn´ı podm´ınkou je, ˇze mnoˇzina hran T je podmnoˇzinou hran nˇejaké minim´ aln´ı ´ R, ˇ 2004, s. 100) kostry - tato podm´ınka se nesm´ı pˇridán´ım nové hrany poruˇsit. (KOLA Algoritmus 4.1 - hled´ an´ı minim´ aln´ı kostry grafu 1. T = ∅ 2. while T netvoˇ r´ ı kostru 3. 4.

do najdi vhodnou hranu [u, v] pro T T = T ∪ {[u, v]}

5. return T

Základem u ´spˇeˇsného nalezen´ı minimáln´ı kostry je grafu je zvolen´ı hrany [u, v], kter´ a je pˇrid´ av´ ana ke vznikaj´ıc´ı kostˇre (alg. 4.1, krok 3). Tento krok je ˇreˇsen dvˇema zp˚ usoby. Jako prvn´ı navrhl algoritmus pro hledán´ı minimáln´ı kostry jiˇz v roce 1926 O. Bor˚ uvka, v roce 1956 ho v souvislosti s rozvojem v´ ypoˇcetn´ı techniky znovuobjevil ameriˇcan J. Kruskal. Dnes je tento algoritmus oznaˇcov´ an za Bor˚ uvk˚ uv-Kruskal˚ uv. Efektivnˇejˇs´ı metodu ˇreˇsen´ı navrhl v roce 1930 V. Jarn´ık a nez´ avisle na nˇem v roce 1957 R. C. Prim. Tento algoritmus tak b´ yv´ a oznaˇcov´ an jako Jarn´ık˚ uv-Prim˚ uv. Pˇri ˇreˇsen´ı diplomové práce byl vyuˇzit Kruskal˚ uv algoritmus, na tomto m´ıstˇe proto uvedeme pouze jeho princip. Bor˚ uvk˚ uv-Kruskal˚ uv algoritmus Princip algoritmu. Princip ilustruje obr. 4.11 a alg. 4.2. Základn´ı myˇslenkou je pˇrid´ an´ı takové hrany E = [u, v], kter´ a m´ a ze vˇsech hran spojuj´ıc´ıch dva podstromy vznikaj´ıc´ı kostry minim´ aln´ı ohodnocen´ı ω. U vybrané hrany je zjiˇst’ováno um´ıstˇen´ı inciduj´ıc´ıch uzl˚ u. Na základˇe um´ıstˇen´ı uzl˚ u je pak provedeno spojen´ı odpov´ıdaj´ıc´ıch podstrom˚ u.

37

´ R, ˇ 2004, s. 102) Obr. 4.11: Princip Bor˚ uvkova-Kruskalova algoritmu (pˇrevzato z: KOLA Algoritmus 4.2 - Bor˚ uvk˚ uv-Kruskal˚ uv algoritmus 1. T = ∅ 2. for ∀u ∈ U 3. do MAKE-SET(u) 4. uspoˇ r´ adej E do neklesaj´ ıc´ ı posloupnosti podle v´ ahy ω 5. for ∀e = [u, v] ∈ E v poˇ rad´ ı neklesaj´ ıc´ ıch vah 6. do if FIND-SET(u) 6= FIND-SET(v) 7. then T = T ∪ {[u, v]} 8. UNION(u, v) 9. return T MAKE-SET(x) vytvoˇr´ı nov´ y podgraf, jehoˇz jedin´ ym prvkem (a zároveˇ n i reprezentantem) je prvek x. Pˇredpokl´ ad´ a se pˇritom, ˇze x nen´ı prvkem ˇzádného jiného podgrafu. 1. p[x] = x //nastaven´ ı otce ve stromu 2. hod[x] = 0 //ud´ av´ a vzd´ alenost k nejvzd´ alenˇ ejˇ s´ ımu listu stromu UNION(x,y) provede sjednocen´ı podgraf˚ u obsahuj´ıc´ıch prvky x a y. Tyto podgrafy jsou pˇred sjednocen´ım disjunktn´ı. D˚ usledkem je i to, ˇze se p˚ uvodn´ı podgrafy odstran´ı a m´ısto nich se vytvoˇr´ı jeden sjednocen´ y podgraf. Reprezentantem sjednocen´ı m˚ uˇze b´ yt jak´ ykoliv prvek. 1. LINK(FIND-SET(x), FIND-SET(y)) LINK (x,y) 1. if hod[x] > hod[y] then p[y] = x 2. else p[x] = y 3. if hod[x] = hod[y] then hod[y] = hod[y] + 1 FIND-SET(x) vrac´ı jako svou hodnotu reprezentanta podgrafu obsahuj´ıc´ı prvek x. 1. if x 6= p[x] then p[x] = FIND-SET(p[x]) 2. return p[x]

ˇ ˇ Casov´ a sloˇ zitost. Casovou sloˇzitost lze stanovit rovnou O(n log n), kde n je poˇcet hran ´ R, ˇ 2004) grafu. (KOLA 38

4.5.2

Prohled´ av´ an´ı grafu do hloubky (Depth First Search)

Tento algoritmus je vyuˇz´ıv´ an pro anal´ yzu grafu, jeho c´ılem je dostat se do grafu co nej” hloubˇeji“. Algoritmus proch´ az´ı hrany vycházej´ıc´ı z poslednˇe nalezeného uzlu u, kter´ y jeˇstˇe má nˇejaké neprozkoumané hrany. Kdyˇz projde vˇsechny jeho hrany, vrát´ı se zpátky k uzlu, ze kterého se do uzlu u dostal a z nˇeho pokraˇcuje po dalˇs´ı dosud neprozkoumané hranˇe. Postupuje se tak dlouho, dokud nejsou objeveny vˇsechny uzly dosaˇzitelné z v´ ychoz´ıho uzlu. Pokud jeˇstˇe nˇejaké neprozkoumané vrcholy zb´ yvaj´ı, zvol´ı se nov´ y v´ ychoz´ı uzel. Takto se pokraˇcuje, dokud nejsou prozkoum´ any vˇsechny vrcholy. Oznaˇ cen´ı uzl˚ u. Algoritmus rozdˇeluje uzly do tˇr´ı skupin: • nové (zat´ım neobjevené), • otevˇrené, • uzavˇrené. Na zaˇc´ atku jsou vˇsechny vrcholy oznaˇceny jako nové (stav[v] == −1). Otevˇren´ ymi se stanou po svém objeven´ı (stav[v] == 0) a uzavˇren´ ymi po kompletn´ım prozkoumán´ı sv´ ych soused˚ u (stav[v] == 1). Pˇri prov´ adˇen´ı algoritmu jsou kaˇzdému vrcholu v pˇriˇrazeny znaˇcky d[v] a f [v], které odpov´ıdaj´ı okamˇziku otevˇren´ı a uzavˇren´ı uzlu. S pomoc´ı tˇechto znaˇcek lze provádˇet dalˇs´ı grafové algoritmy. Pˇri objeven´ı nového uzlu u je do vektoru p uloˇzen jeho pˇredch˚ udce v. Algoritmus 4.3 - Prohled´ av´ an´ı do hloubky Inicializace 1. for ∀v ∈ V : stav[v] = −1 a p[v] = −1. ˇ C´ ıtaˇ c znaˇ cek i = 0 2. for ∀v ∈ V 3.

if stav[v] == −1

4.

DFS(v)

DFS(v) 1. stav[v] = 0 2. i = i + 1; d[v] = i 3. for ∀u ∈ Adj[v] 4.

if stav[u] == −1

5.

p[u] = v

6.

DFS(u)

7. stav[v] = 1 8. i = i + 1; f [v] = i

ˇ Casov´ a sloˇ zitost. Algoritmus je realizován rekurzivn´ım zp˚ usobem a jeho sloˇzitost je O(m + ´ ˇ 2004) n), kde m je poˇcet vrchol˚ u a n je poˇcet hran grafu. (KOLAR,

39

4.6

Douglas-Peucker algoritmus

V pr˚ ubˇehu agregace je tˇreba zjednoduˇsit tvar redukovaného skeletonu agregovaného polygonu. Pro generalizaci bude pouˇzit Douglas-Peucker˚ uv algoritmus, kter´ y patˇr´ı mezi nejˇcastˇeji pouˇz´ıvané algoritmy pro generalizaci polylini´ı. Algoritmus byl nez´ avisle na sobˇe publikován v roce 1973 dvˇema autory - D. Douglasem a T. Peuckerem, b´ yv´ a proto oznaˇcován jako Douglas-Peucker algoritmus. V informatice je znám´ y sp´ıˇse jako Ramer algoritmus. Patˇr´ı mezi globáln´ı algoritmy, které zohledˇ nuj´ı tvar generalizované linie jako celku. Jedná se o rekurzivn´ı algoritmus, kter´ y postupnˇe pˇridává k linii vrcholy splˇ nuj´ıc´ı danou podm´ınku. Princip algoritmu. Princip ilustruje obr. 4.12 a alg. 4.4. Lomená ˇcára L = {p1 , p2 , . . . , pn } je nahrazena u ´seˇckou L0 = p1 pn spojuj´ıc´ı poˇcáteˇcn´ı a koncov´ y bod p˚ uvodn´ı ˇcáry. Je definov´ an koridor o ˇs´ıˇrce h. Pak je hled´ an bod p vnˇe koridoru takov´ y, ˇze plat´ı d(p, L0 ) = max(d(pi , L0 )) Pokud takov´ y bod neexistuje, algoritmus konˇc´ı. V opaˇcném pˇr´ıpadˇe je bod p pˇridán k L0 a pokraˇcuje se hled´ an´ım nového bodu p. Vstupn´ımi parametry algoritmu jsou tak indexy poˇcáteˇcn´ıho a koncového bodu generalizované linie a ˇs´ıˇrka koridoru h.

Obr. 4.12: Princip Douglas-Peucker algoritmu

40

Algoritmus 4.4 - Douglas-Peucker(L, h, start, end ) 1. if (end > start + 1) do 2.

max = start + 1

3.

dmax = dist(pmax , pstart pend )

4.

i = max + 1

5.

do untill (i < end)

6.

d = dist(pi , pstart pend )

7.

if (d > dmax ) do

8. 9.

max = i; dmax = d i=i+1

10. if (dmax > h) 11.

L0 ← pmax

12.

Douglas-Peucker(L,h,start,max)

13.

Douglas-Peucker(L,h,max,end)

41

5

´ STANOVENÍ GEOMETRICKYCH ´ A KARTOGRAFICKYCH PODMÍNEK PRO AGREGACI

V této ˇc´ asti, pˇred pˇredstaven´ım vlastn´ıho návrhu algoritmu, budou stanoveny podm´ınky pro agregaci. Generalizaˇcn´ı algoritmus byl navrhován tak, aby co nejlépe splnil pomˇernˇe ˇsiroké poˇzadavky kartografického i geometrického charakteru. Uved’me nejv´ yznamnˇejˇs´ı kartografické poˇzadavky kladené na navrhované ˇreˇsen´ı: • kartografick´ a vˇernost výstupu, • alespoˇ n r´ amcové zachov´ an´ı plochy generalizovaných objekt˚ u, • univerzalita (pouˇzitelnost pro r˚ uzné tvary budov vˇcetnˇe modern´ı architektury), • malý posunu tˇeˇziˇstˇe agregovaného objektu vzhledem ke vstupn´ım dat˚ um, • zjednoduˇsen´ı tvaru pˇri souˇcasném zachov´ an´ı výˇse uvedených parametr˚ u. Z hlediska informatického poˇzadujeme: • snadnou implementaci algoritmu, • rozumnou výpoˇcetn´ı sloˇzitost, • uchov´ an´ı topologie dat, • schopnost pˇredch´ azen´ı tzv. self-intersections, které negativnˇe ovlivˇ nuj´ı kvalitu výstup˚ u. ˇ Rada stanoven´ ych poˇzadavk˚ u má pomˇernˇe protich˚ udn´ y charakter, a nebude zˇrejmˇe jednoduché je beze zbytku pˇri n´ avrhu algoritmu splnit. Algoritmus vyuˇz´ıvá pomˇernˇe ˇsiroké ˇsk´ aly pomocn´ ych algoritm˚ u a datov´ ych struktur, jejichˇz zkombinován´ı nebude pˇri implementaci snadné. Zachov´ an´ı polohy, plochy a topologie dat by mˇely b´ yt silnˇejˇs´ımi stránkami algoritmu. S t´ım souvisej´ıc´ı kartografick´ a vˇernost v´ ystupu (pˇredevˇs´ım zachován´ı pravo´ uhlosti a orientace budov) je v teoretickém n´ avrhu splnitelná, jej´ı cenou je vˇsak sloˇzitˇejˇs´ı implementace.

42

Ve zpr´ avˇe AGENT (DA2, 2001) jsou stanoveny omezen´ı pro generalizaci budov a shluk˚ u budov. Nˇekteré z nich, podpoˇrené napˇr. prac´ı STEINIGERA a TAILLANDIERA i vlastn´ım studov´ an´ım ˇcesk´ ych mapov´ ych dˇel (Základn´ı mapy, Topografické mapy) jsou dále uvedeny v jednotliv´ ych podkapitol´ ach, nebot’ definuj´ı podm´ınky kartografické pˇrirozenosti a ˇcitelnosti v´ ystup˚ u.

5.1

Kartograficky pˇ rirozen´ e v´ ystupy

Jedn´ım z hlavn´ıch poˇzadavk˚ u na algoritmus je kartografická vˇernost v´ ystupu. Tento aspekt se prom´ıtne nejen do samotného procesu agregace, ale také uˇz pˇri v´ ybˇeru prvk˚ u, které budou do agregace vstupovat. Omezen´ı liniov´ ymi prvky. Budovy a shluky budov v rámci s´ıdeln´ıch systém˚ u jsou omezeny pˇredevˇs´ım cestn´ı s´ıt´ı. Agregace by proto nemˇela spojovat budovy, které náleˇz´ı do r˚ uzn´ ych blok˚ u. Tato skuteˇcnost je stanovena jako jedna ze základn´ıch omezuj´ıc´ıch podm´ınek pro navrhovan´ y algoritmus. Obdobnˇe by bylo moˇzné stanovit podm´ınku, aby se neagregovaly budovy, mezi kter´ ymi leˇz´ı napˇr´ıklad vodn´ı tok, nebo které jsou od sebe v´ yˇskovˇe pˇr´ıliˇs vzdáleny. Tyto skuteˇcnosti v algoritmu zahrnuty nejsou, jejich zabudován´ı by vˇsak nebylo pˇr´ıliˇs nároˇcné. Pro kaˇzdou dvojici agregovan´ ych budov m˚ uˇzeme zjiˇst’ovat, zda spojnice jejich centroid˚ u kˇr´ıˇz´ı vodn´ı tok nebo stanoven´ y poˇcet vrstevnic (viz obr. 5.1). Odpov´ıdaj´ıc´ı vrstvy bychom samozˇrejmˇe museli m´ıt k dispozici.

Obr. 5.1: Omezen´ı liniov´ ymi prvky: (a) kˇr´ıˇzen´ı vrstevnic, (b) kˇr´ıˇzen´ı vodn´ıho toku Zachov´ an´ı geografick´ eho kontextu. V rámci zachován´ı geografického kontextu by mˇely b´ yt z agregace vylouˇceny osamocené malé budovy, které by v mapˇe menˇs´ıho mˇeˇr´ıtka nemˇely zaniknout. V r´ amci kontextu by také mˇel b´ yt zachován charakteristick´ y vzor budov. Problematika zachov´ an´ı charakteristického vzoru byla rozvedena v ˇcásti 3.2. V oblastech rozvolnˇenˇejˇs´ı z´ astavby by v˚ ubec nemˇelo docházet k agregaci, ale sp´ıˇse k typifikaci budov. Identifikovat tyto oblasti by bylo vhodné pˇred samotnou aplikac´ı navrˇzeného algoritmu. Jedná se o samostatn´ y problém, ˇreˇsen´ y napˇr. pomoc´ı pˇr´ıstup˚ u zaloˇzen´ ych na gestalt teorii (STEINIGER a TAILLANDIER; LI et al., 2004) nebo kombinac´ı bufferu a Voronoi diagramu (BASARANER a SELCUK, 2004).

43

Navrˇzen´ y algoritmus v této otázce ˇreˇs´ı pouze pro ˇceské prostˇred´ı ˇcast´ y fenomén chatov´ ych oblast´ı. Budovy v chatov´ ych oblastech maj´ı typicky ˇctvercov´ y p˚ udorys s malou plochou. ˇ ´ Podle informac´ı od CUZK se napˇr´ıklad vektorizace ZABAGED na základˇe ZM 10 ˇr´ıdila následuj´ıc´ım pravidlem. Mohly se umˇele zvˇetˇsovat budovy právˇe v chatov´ ych oblastech tak, 2 aby splˇ novaly kritérium minim´ aln´ı plochy 50m , resp. se mu pˇribl´ıˇzily (odpov´ıdaj´ı ˇctverci o stranˇe 7 metr˚ u). Jedn´ a se o postup v kartografii pomˇernˇe ˇcast´ y, tzv. kresba pˇres m´ıru. V pˇr´ıpadˇe jin´ ych datov´ ych sad mohou b´ yt minimáln´ı rozmˇery jiné, mˇely by vˇsak b´ yt podˇr´ızeny podm´ınk´ am ˇcitelnosti, viz obr. 5.2. Navrˇzen´ y algoritmus pˇri naˇc´ıtán´ı budov ze zdrojov´ ych soubor˚ u odfiltruje budovy menˇs´ı neˇz kritick´ a hodnota Smin , v pˇr´ıpadˇe testován´ı na datech ZABAGED bude Smin stanoveno na hodnotu 50m2 .

Obr. 5.2: Grafické limity (upraveno podle: AGENT, DA2, 2001, s. 32)

Obr. 5.3: Omezuj´ıc´ı podm´ınky pro budovy (upraveno podle: STEINIGER a TAILLANDIER, s. 2)

44

5.2

Zachov´ an´ı plochy a tˇ eˇ ziˇ stˇ e agregovan´ ych oblast´ı

V souvislosti se zachov´ an´ım kartografické vˇerohodnosti je tˇreba také minimalizovat zmˇeny geometrick´ ych vlastnost´ı budov. Mezi hlavn´ı kritéria patˇr´ı (podle AGENT, DA2, 2001) zachován´ı pˇresnosti p˚ uvodn´ıho um´ıstˇen´ı, zachován´ı absolutn´ı a relativn´ı orientace, s ˇc´ımˇz souvis´ı i zachov´ an´ı tvaru - prot´ ahlost budov, pravo´ uhlost, minimáln´ı velikost hran a v´ ystupk˚ u budov (obr. 5.3). Pˇri agregaci mus´ı vˇzdy z´ akonitˇe doj´ıt ke zvˇetˇsen´ı plochy objekt˚ u, stejnˇe tak k posunu tˇeˇziˇstˇe. Pˇri hodnocen´ı algoritmu budou tyto charakteristiky vypoˇcteny a posouzeny.

5.3

R˚ uzn´ e typy budov, zjednoduˇ sen´ı tvaru

Schopnost zpracov´ an´ı budov obecn´ ych tvar˚ u pˇredstavuje znaˇcnˇe sloˇzit´ y problém. Agregace v´ıceménˇe pravo´ uhl´ ych budov bez zvláˇstn´ıch v´ ystupk˚ u je pomˇernˇe jednoduchá, dobré v´ ysledky v tomto pˇr´ıpadˇe d´ av´ a algoritmus REGNAULDA, 1998 (viz ˇcást 3.3.1), vˇetˇs´ı problém vˇsak má v pˇr´ıpadˇe budov sloˇzitˇejˇs´ıch tvar˚ u. D˚ uleˇzitou roli hraje nejen tvar jedné budovy, ale i tvar a poloha budov sousedn´ıch, které jsou adepty pro agregaci. Algoritmus je proto navrhován se snahou provést agregaci bez explicitn´ıho zjiˇst’ov´ an´ı charakteristik jednotliv´ ych budov (protáhlost, pravo´ uhlost, poˇcet vrchol˚ u, u ´hel natoˇcen´ı, minim´ aln´ı ˇs´ıˇrka...) tak, aby dok´ azal zpracovat budovy sloˇzitˇejˇs´ıch tvar˚ u. Pˇri fináln´ım zjednoduˇsen´ı prvk˚ u je nutné br´ at v u ´vahu geometrické limity tvar˚ u budov.

5.4

Zmˇ ena datov´ e reprezentace

Rastrov´ a reprezentace dat, která diskrétnˇe rozdˇeluje prostor, má své v´ yhody pro mnohé prostorové anal´ yzy. Uved’me napˇr´ıklad ˇsiroké vyuˇzit´ı mapové algebry, interpolace, filtrace nebo modelov´ an´ı geografick´ ych jev˚ u. Také v n´ı nen´ı nutné ˇreˇsit topologickou správnost objekt˚ u v takové m´ıˇre, jako u vektorov´ ych dat. Naproti tomu vektorová reprezentace dat je pamˇet’ovˇe ménˇe n´ aroˇcn´ a, umoˇzn ˇuje pˇr´ımé propojen´ı s databáz´ı, snadnou editaci, lepˇs´ı provádˇen´ı nˇekter´ ych anal´ yz (napˇr´ıklad s´ıt’ové anal´ yzy). Datab´ aze, z kter´ ych vznikaj´ı státn´ı mapová d´ıla, turistické mapy, mapy na webov´ ych portálech atd. jsou uloˇzeny ve vektorovém formátu. Algoritmy pro kartografickou generalizaci by proto mˇely umˇet pracovat s t´ımto typem dat. Jak bylo uvedeno v ˇcásti 3.3.2, konverze mezi datov´ ymi reprezentacemi jsou n´ aroˇcné. C´ılem je proto navrhnout nov´ y algoritmus pracuj´ıc´ı pouze ve vektorovém prostˇred´ı.

45

6

´ ˇ ÍHO ALGORITMU NAVRH GENERALIZACN

V této ˇc´ asti je pˇredstaven vlastn´ı návrh generalizaˇcn´ıho algoritmu. Problém generalizace technikou agregace je netrivi´ aln´ı, pˇri návrhu je nutné zohlednit ˇradu geometrick´ ych i kartografick´ ych poˇzadavk˚ u, které jsou v mnoh´ ych pˇr´ıpadech protich˚ udné. C´ılem je navrhnout algoritmus s co nejvˇetˇs´ı m´ırou automatizace tak, aby se minimalizoval poˇcet ruˇcn´ıch korekc´ı v´ ysledk˚ u. Algoritmus bude vhodné aplikovat na datové sady, ve kter´ ych jsou budovy znázornˇeny jako samostné objekty, pˇr´ıpadnˇe jako bloky budov. Tuto podm´ınku splˇ nuj´ı datové sady do mˇeˇr´ıtka podrobnosti 1:100 000. Vstupn´ı datové sady by mˇely b´ yt pˇred vstupem do algoritmu generalizov´ any tak, aby neobsahovaly nadbyteˇcné vrcholy. Vstupn´ım i v´ ystupn´ım formátem pro generalizaci je shapefile. Uˇzivatelsk´ ym vstupem algoritmu bude nav´ıc hodnota minim´ aln´ı plochy Smin (viz ˇc´ ast 5.1) a mˇeˇr´ıtkové ˇc´ıslo M mˇeˇr´ıtka mapy, do které chceme generalizovat. Pr˚ ubˇeh navrhovaného algoritmu m˚ uˇzeme v zásadˇe rozdˇelit do dvou krok˚ u: urˇcen´ı budov vhodn´ ych pro agregaci a vlastn´ı postup agregace. Prvn´ı krok zahrnuje vyhledán´ı soused´ıc´ıch budov, zhodnocen´ı kritéri´ı pro jejich agregaci a urˇcen´ı skupin budov, které budou tvoˇrit agregovan´ y polygon. Druh´ y krok zahrnuje vytvoˇren´ı redukovaného skeletonu agregovaného polygonu a jeho n´ asledné rozˇs´ıˇren´ı.

6.1

Urˇ cen´ı budov vhodn´ ych pro agregaci

Vyhled´ an´ı soused´ıc´ıch budov. Definujme navzájem soused´ıc´ı budovy na základˇe sousednosti Voronoi bunˇek. Gener´ atory Voronoi diagramu tvoˇr´ı centroidy generalizovan´ ych budov, viz obr. 6.1.

Obr. 6.1: Voronoi diagram nad centroidy budov pro urˇcen´ı sousednosti polygon˚ u 46

Zhodnocen´ı krit´ eri´ı pro agregaci. Oznaˇcme dvˇe navzájem soused´ıc´ı budovy jako P , Q. Základn´ım kritériem pro rozhodnut´ı, zda budou slouˇceny, je hodnota jejich minim´ aln´ı vzdálenosti d(P, Q), vypoˇcten´ a pomoc´ı algoritmu z ˇcásti 4.2. Kritická hodnota vzdálenosti dmax bude stanovena v z´ avislosti na uˇzivatelském vstupu mˇeˇr´ıtkového ˇc´ısla M - bude odpov´ıdat vzd´ alenosti 0, 25mm ve v´ ysledném mˇeˇr´ıtku (hodnota stanovená dle grafick´ ych limit˚ u, viz. obr. 5.2): dmax = 0, 25 ·

M 1000

Agregovat se tedy budou pouze takové polygony P , Q, pro které plat´ı: d(P, Q) < dmax

V souladu s ˇc´ ast´ı 5.1 jsou ze zpracován´ı vynechány polygony P , pro které plat´ı: S(P ) < Smin

Pro testov´ an´ı algoritmu na datech ZABAGED je Smin = 50m2 . Hodnota je stanovena na základˇe textu v ˇc´ asti 5.1. Mnoˇ zina omezen´ı. Definujme mnoˇzinu omezen´ı O tvoˇrenou liniov´ ymi segmenty pˇredstavuj´ıc´ı prvky, pˇres které nesm´ı b´ yt agregace provádˇena (silnice, vodn´ı toky, vrstevnice...) - viz ˇc´ ast 5.1. N´ aslednˇe testujme vzájemnou polohu spojnic centroid˚ u agregovan´ ych budov s prvky mnoˇziny O, viz obr. 6.2. K agregaci dojde pouze v pˇr´ıpadˇe, je-li splnˇena podm´ınka O ∩ sc = ∅

kde sc je testovan´ a spojnice centroid˚ u.

Obr. 6.2: Testov´ an´ı vz´ ajemné polohy spojnic centroid˚ u a segment˚ u omezen´ı 47

Uved’me vztahy pro v´ ypoˇcet souˇradnic centroidu polygonu:

n−1

Cx =

Cy =

1 X (xi + xi+1 )(xi yi+1 − xi+1 yi ) 6A

(6.1)

1 6A

(6.2)

i=0 n−1 X

(yi + yi+1 )(xi yi+1 − xi+1 yi )

i=0

kde A je plocha polygonu: n−1

A=

1X (xi yi+1 − xi+1 yi ) 2 i=0

n je poˇcet vrchol˚ u polygonu, posledn´ı vrchol je shodn´ y s poˇcáteˇcn´ım. Oznaˇcme P seznam vˇsech vstupn´ıch polygon˚ u, Pagr seznam vˇsech polygon˚ u, které budou agregov´ any, C(P ) seznam vˇsech centroid˚ u a Padj seznam soused˚ u polygonu Pi ∈ P . Plat´ı, ˇze Pagr je podmnoˇzinou P . Vlastn´ı algoritmus pro nalezen´ı budov vhodn´ ych pro agregaci lze zapsat takto: Algoritmus 6.1 - Urˇ cen´ı budov pro agregaci Vstup: seznam P , v´ ystup: Padj for ∀Pi ∈ P 1. for ∀Pi ∈ P 2. if (S(Pi ) > Smin ) 3. Pagr ← Pi 4. for ∀Pi ∈ Pagr 5. urˇ ci centroid C(Pi ) dle vztah˚ u 6.1, 6.2 6. Voronoi diagram V (C(P )) ← C(Pi ) 7. for ∀ buˇ nka fp ∈ V (C(P )) 8. for ∀ hrana h ∈ fp 9. urˇ ci soused´ ıc´ ı polygon s 10. if (O ∩ sc = ∅ and vzd´ alenost d(s, p) < dmax ) 11. Padj ← s

Vytvoˇ ren´ı seznamu soused˚ u. Sekvenˇcn´ım procházen´ım Voronoi bunˇek jsou kaˇzdému polygonu pˇriˇrazeny indexy sousedn´ıch polygon˚ u, s nimiˇz se má agregovat (za dodrˇzen´ı podm´ınek minim´ aln´ı plochy a pr˚ useˇc´ık˚ u s omezen´ımi). T´ım se vytvoˇr´ı pro kaˇzd´ y polygon lineárn´ı seznam soused˚ u pro agregaci, Padj (alg 6.1, krok 7-11). Mnoˇzina vˇsech line´ arn´ıch seznam˚ u Padj je spojovou reprezentac´ı grafu G, pˇredstavuj´ıc´ıho skupiny budov pro agregaci (pˇr´ıklad viz. obr. 6.3). Kaˇzd´ y podstrom grafu G definuje jednu skupinu budov pro agregaci. Urˇcen´ı - explicitn´ı vyjádˇren´ı - tˇechto podstrom˚ u je c´ılem prvn´ı ˇcásti algoritmu. Pro jejich nalezen´ı je na graf G spuˇstˇen algoritmus prohledáván´ı do hloubky (alg. 4.3). 48

Obr. 6.3: Graf pˇredstavuj´ıc´ı skupiny budov pro agregaci Spojov´ a reprezentace grafu G (tj. mnoˇzina ∀Padj ) vypadá pro obr. 6.3 následovnˇe: 0→∅

6 → 2, 1

12 → 10, 15

1 → 4, 6

7 → 9, 8

13 → ∅

2 → 6, 9

8→7

14 → ∅

3→∅

9 → 7, 2

15 → 12

4→1

10 → 12, 11

5→∅

11 → 10

Nalezen´ı podstrom˚ u grafu. Prohledáván´ı do hloubky grafu G je zahájeno ve vrcholu v (pro ilustraci napˇr. vrchol 0 na obr. 6.3). Jedná se o izolovan´ y vrchol, prohledáván´ı proto pokraˇcuje dalˇs´ım vrcholem (napˇr. 1 na obr. 6.3). Po objeven´ı vˇsech vrchol˚ u dosaˇziteln´ ych z vrcholu 1 (tj. po objeven´ı celého podstromu) se zvol´ı nov´ y v´ ychoz´ı vrchol. V algoritmu se pokraˇcuje tak dlouho, dokud nen´ı graf kompletnˇe prohledán. Pokud v pr˚ ubˇehu DFS ukl´ adáme vˇzdy do jednoho nového lineárn´ıho seznamu sekvenci vrchol˚ u tvoˇr´ıc´ıch d´ılˇc´ı podstrom (pˇri souˇcasném ignorován´ı izolovan´ ych vrchol˚ u), je v´ ysledkem prohled´ av´ an´ı mnoˇzina line´ arn´ıch seznam˚ u pˇredstavuj´ıc´ıch podstromy grafu G, pro obr. 6.3 ve tvaru: 8, 7, 9, 2, 6, 1, 4 11, 10, 12, 15, 13 Kaˇzd´ y z line´ arn´ıch seznam˚ u tedy pˇredstavuje jeden podstrom, tj. jednu skupinu budov, které se budou vz´ ajemnˇe agregovat.

49

6.2

Vlastn´ı agregace

Pro vlastn´ı agregaci byl navrˇzen pˇr´ıstup s vyuˇzit´ım konstrukce topologické kostry, konkrétnˇe straight skeletonu, konstruovaném nad agregovan´ ymi polygony. Na u ´vod popiˇsme a ilustrujme funkcionalitu algoritmu na konkrétn´ım pˇr´ıpadˇe (viz obr. 6.4). Obr 6.4a zn´ azorˇ nuje budovy urˇcené pro agregaci. V prvn´ı fázi zkonstruujme pro kaˇzdou z budov straight skeleton (obr. 6.4b). Z kaˇzdého straight skeletonu z´ıskejme redukovan´ y straight skeleton (obr. 6.4c). N´ aslednˇe agregujme redukované straight skeletony Kruskalov´ ym ´ algoritmem. Uloha agregace budov je tedy pˇrevedena na u ´lohu agregace podkoster grafu (obr. 6.4d). Posledn´ım krokem celého algoritmu je rekonstrukce polygonu z vytvoˇrené kostry (obr. 6.4e). Vytvoˇrme z kostry pohybem jej´ıch vrchol˚ u po bisektorech u ´hl˚ u smˇerem ven mal´ y polygon, jehoˇz plocha se limitnˇe bl´ıˇz´ı 0, a nazvˇeme ho prvn´ı aproximac´ı agregovaného polygonu. Poté rozˇsiˇrujme tento pomocn´ y polygon (opˇet po bisektorech u ´hl˚ u), dokud wakt ≤ w

kde wakt je aktu´ aln´ı ˇs´ıˇrka polygonu, w je ukonˇcovac´ı ˇs´ıˇrka. Nastaven´ı hodnoty w bude diskutováno v ˇc´ asti 6.2.3.

Obr. 6.4: Princip agregace polygon˚ u

50

V n´ asleduj´ıc´ıch podkapitol´ ach jsou podrobnˇeji popsány jednotlivé kroky vlastn´ı agregace polygon˚ u - prvn´ı se vˇenuje tvorbˇe a generalizaci redukovaného skeletonu agregovaného polygonu, druh´ a rozˇs´ıˇren´ı redukovaného skeletonu na prvn´ı aproximaci polygonu a tˇret´ı vlastn´ımu rozˇsiˇrov´ an´ı polygonu. Funkcionalita celého algoritmu je znázornˇena na obr. 6.5.

Obr. 6.5: Schéma generalizaˇcn´ıho algoritmu

51

6.2.1

Tvorba a generalizace redukovan´ eho straight skeletonu agregovan´ eho polygonu

Tvorba redukovan´ eho skeletonu agregovan´ eho polygonu. Pro kaˇzd´ y z polygon˚ u urˇcen´ ych pro agregaci sestrojme straight skeleton. Ze skeletonu z´ıskejme redukovan´ y skeleton (obr. 6.4b,c,d). Kaˇzd´ y z redukovan´ ych skeleton˚ u povaˇzujme za graf Gi = (Vi , Ei , εi ), kde Vi a Ei jsou mnoˇziny vrchol˚ u a hran redukovan´ ych skeleton˚ u. Nyn´ı uvaˇzujme, ˇze kaˇzd´ y z tˇechto graf˚ u je podgrafem grafu H = (V, E, ε). Graf H je tvoˇren vˇsemi vrcholy a vˇsemi hranami vˇsech redukovan´ ych skeleton˚ u. Minimáln´ı kostra grafu H pak urˇcuje redukovan´ y straight skeleton agregovaného polygonu. Ohodnocen´ı hran pˇredstavuj´ı jejich délky. Generalizace redukovan´ eho skeletonu. Vytvoˇren´ y redukovan´ y skeleton je vhodné generalizovat - pˇredevˇs´ım odstranit krátké v´ ystupky a zjednoduˇsit jeho tvar. Definujme na tomto m´ıstˇe pojem vˇetev. Vˇ etev. Podgraf grafu G, kter´ y je stromem a pro kaˇzd´ y z jeho uzl˚ u plat´ı: su ≤ 2

kde su je stupeˇ n uzlu (tj. poˇcet hran s uzlem inciduj´ıc´ıch), nazvˇeme vˇetv´ı grafu.

Obr. 6.6: Generalizace redukovaného skeletonu agregovaného polygonu Na obr. 6.6a je zn´ azornˇen redukovan´ y straight skeleton agregovaného polygonu. C´ılem je provést jeho generalizaci. Navrˇzen´ y algoritmus generalizuje redukovan´ y skeleton po vˇetv´ıch, tj. v pˇr´ıpadˇe na obr. 6.6 dojde ke generalizaci tˇr´ı vˇetv´ı: • 1-2-3-4-5 • 5-6-7 • 5-8-9-10-11-12-13-14 52

Generalizace je prov´ adˇena Douglas-Peuckerov´ ym algoritmem (ˇcást 4.6). V pˇr´ıpadˇe, ˇze kostra obsahuje kr´ atké vˇetve, jsou tyto vˇetve zcela odstranˇeny. Douglas-Peucker algoritmus poˇzaduje jako vstup ˇs´ıˇrku koridoru h. Pro odstranˇen´ı vˇetv´ı je tˇreba stanovit minimáln´ı délku vˇetve hmin . Hodnoty h a hmin budou urˇceny v závislosti na uˇzivatelském vstupu mˇeˇr´ıtkového ˇc´ısla M - budou odpov´ıdat kritické hodnotˇe 0, 2mm ve v´ ysledném mˇeˇr´ıtku:

h = hmin = 0, 2 ·

M 1000

(6.3)

Hodnota 0, 2mm je stanovena na základˇe grafick´ ych limit˚ u (obr. 5.2). Stejnou hodnotu pouˇzili (pro ˇs´ıˇrku p´ asu h Douglas-Peuckerova algoritmu) ve své práci STEINIGER a TAILLANDIER. Zhodnocen´ı kvality generalizace. Zd˚ uraznˇeme, ˇze kvalita generalizace redukovaného skeletonu bude ve v´ ysledku v´ yraznˇe ovlivˇ novat tvar polygonu vzniklého z této kostry. Z implementaˇcn´ıho hlediska se jedn´ a o netriviáln´ı u ´kol a navrˇzen´ y algoritmus je v otázce generalizace redukovaného skeletonu ponˇekud omezen. Na obr. 6.6 ilustrujme ideáln´ı“, stˇredn´ı“ ” ” a reáln´ y“ stav generalizované kostry. ” Situace na obr. 6.6b, 6.6c a 6.6d znázorˇ nuj´ı r˚ uznou m´ıru generalizace redukovaného skeletonu. Obr. 6.6d pˇredstavuje ideáln´ı stav“, kdy: ” • je zachov´ ana hlavn´ı linie, podél které jsou budovy um´ıstˇeny (spojnice AB), • jsou odstranˇeny hrany, které vznikly v m´ıstech p˚ uvodn´ıch prav´ ych u ´hl˚ u (hrana 2-3, 8-9, 10-11, 12-13) tak, aby tyto u ´hly z˚ ustaly po rekonstrukci zachovány, • jsou odstranˇeny kr´ atké segmenty, • jsou odstranˇeny nadbyteˇcné vrcholy v jednotliv´ ych vˇetv´ıch. Obr. 6.6b pˇredstavuje stˇredn´ı stav“, kdy: ” • jsou odstranˇeny hrany, které vznikly v m´ıstech p˚ uvodn´ıch prav´ ych u ´hl˚ u (hrana 2-3, 8-9, 10-11, 12-13) tak, aby tyto u ´hly z˚ ustaly po rekonstrukci zachovány, • jsou odstranˇeny kr´ atké segmenty, • jsou odstranˇeny nadbyteˇcné vrcholy v jednotliv´ ych vˇetv´ıch. Obr. 6.6c pˇredstavuje re´ aln´ y stav“, kter´ y bude dosaˇzen aplikac´ı navrˇzeného algoritmu: ” • jsou odstranˇeny kr´ atké segmenty, • jsou odstranˇeny nadbyteˇcné vrcholy v jednotliv´ ych vˇetv´ıch.

53

Algoritmus dosahuje pouze stavu ilustrovaného na obr. 6.6c z následuj´ıc´ıch d˚ uvod˚ u: • Douglas-Peucker algoritmus zjednoduˇsuje linii pouze odstranˇen´ım bod˚ u, nemˇen´ı jejich polohu, • generalizace prob´ıh´ a po vˇetv´ıch, takˇze lze tˇeˇzko zachovat hlavn´ı linii (AB na obr. 6.6d), • nahrazen´ı hran v m´ıstˇe prav´ ych u ´hl˚ u by vyˇzadovalo identifikaci tˇechto hran a jejich spr´ avné nahrazen´ı. Pro dalˇs´ı rozpracov´ an´ı navrˇzeného algoritmu pˇredstavuje krok generalizace redukovaného skeletonu jednu z nejvˇetˇs´ıch v´ yzev. Nalezen´ı vˇ etv´ı redukovan´ eho skeletonu. Uved’me zde jeˇstˇe algoritmus pro nalezen´ı vˇetv´ı redukovaného skeletonu. Redukovan´ y skeleton je uloˇzen ve formˇe spojové reprezentace grafu. Pro nalezen´ı vˇetv´ı je vyuˇzito prohledáván´ı do hloubky. Vˇetve jsou ukládány v kontejneru branches. Poˇcet vˇetv´ı RS(P ) je urˇcen následuj´ıc´ım vztahem: z=

n X

! su − 1

+1

i=0

kde n je poˇcet uzlov´ ych vrchol˚ u, su je stupeˇ n uzlu. Algoritmus 6.2 - Nalezen´ı vˇ etv´ı RS(P) Vstup: redukovan´ y skeleton agregovan´ eho polygonu RS(P ), v´ ystup: dvojrozmˇ ern´ y vektor branches 1. urˇ ci poˇ cet vˇ etv´ ı RS(P) z 2. ˇ c´ ıslo vˇ etve branchN o = 0 3. if (z 6= 1) 4. for ∀ vrchol u ∈ RS(P ) 5. if (stav[u] == −1 and su > 2) 6. aktu´ aln´ ı uzel nodeDF S = u 7. DFS(u) 8. if (z == 1) 9. najdi uzel u takov´ y, ˇ ze su == 1 10. DFS2(u) - klasick´ e prohled´ av´ an´ ı do hloubky, alg. 4.3 DFS(u) 1. stav[u] = 0 2. for ∀ vrchol v ∈ Adj[u] 3. if (sv > 2) 4. if (stav[v] == −1) 5. branches[branchNo].pushback(v) 6. branches[branchNo].pushfront(nodeDF S) 7. branchNo++

54

8. else if (sv == 1) 9. branches[branchNo].pushback(v) 10. branches[branchNo].pushfront(nodeDF S) 11. branchNo++ 12. else 13. if (stav[v] == −1) 14. branches[branchNo].pushback(v) 15. DFS(v)

6.2.2

Prvn´ı aproximace agregovan´ eho polygonu

Vezmˇeme generalizovan´ y redukovan´ y skeleton agregovaného polygonu a rozˇsiˇrme ho pohybem po bisektorech u ´hl˚ u smˇerem ven (viz obr. 6.7). Z 1D entity tvoˇrené stromem tak vznikne 2D entita pˇredstavuj´ıc´ı polygon. Nazvˇeme ji prvn´ı aproximac´ı polygonu.

Obr. 6.7: Prvn´ı aproximace polygonu Prvn´ı aproximace polygonu mus´ı splˇ novat dvˇe podm´ınky: • mus´ı se jednat o jednoduch´ y polygon (bez vnitˇrn´ıch intersekc´ı), • polygon mus´ı b´ yt spr´ avnˇe orientován (pro ˇreˇsen´ı práce je zvolena counter-clockwise orientace). Korektn´ı konstrukce prvn´ı aproximace polygonu je zajiˇstˇena dvˇema kroky. Nejprve urˇceme správnou orientaci polygonu. K tomu vyuˇzijme modifikovaného prohledáván´ı do hloubky. Poté proved’me vlastn´ı zmˇenu prostorové dimenze. Urˇ cen´ı spr´ avn´ e orientace vrchol˚ u polygonu. Ilustrujme postup na obr. 6.8 a 6.9. Mˇejme k dispozici redukovan´ y straight skeleton ve formˇe spojové reprezentace grafu, jeho grafick´ a reprezentace viz obr. 6.8 vlevo. Urˇceme správnou orientaci a ˇrazen´ı vrchol˚ u pro tento graf tak, aby z nˇeho bylo moˇzno prost´ ym pohybem po bisektorech vytvoˇrit polygon v counterˇ clockwise orientaci. Razen´ı pro obr. 6.8 by bylo následuj´ıc´ı: 0 − 1 − 6 − 7 − 8 − 7 − 6 − 1 − 4 − 5 − 4 − 1 − 2 − 3 − 2 − 1 − 0. Vlastn´ı modifikované prohledáván´ı do hloubky ilustruje obr. 6.9.

55

Vstupme do algoritmu pro prohledáván´ı do hloubky v koncovém bodˇe grafu (bod A). Dojdeme-li do uzlového bodu (bod U ), postupujme následovnˇe. Oznaˇcme u ´hly α = ∠AU B, β = ∠AU C, γ = ∠AU D, δ = ∠AU A

Uloˇzme u ´hly podle jejich velikosti do prioritn´ı fronty PQ. Vyzvedávejme postupnˇe z PQ u ´hly od nejmenˇs´ıho po nejvˇetˇs´ı a procházejme odpov´ıdaj´ıc´ı segmenty kostry, dokud nen´ı graf kompletnˇe prohled´ an.

Obr. 6.8: Vytvoˇren´ı prvn´ı aproximace polygonu

Obr. 6.9: Urˇcen´ı u ´hl˚ u pro správnou orientaci vrchol˚ u kostry Zmˇ ena prostorov´ e dimenze. Urˇceme pro kaˇzd´ y vrchol redukovaného skeletonu osu u ´hlu inciduj´ıc´ıch hran. V pˇr´ıpadˇe koncov´ ych vrchol˚ u je bisektor urˇcen jako u ´hel inciduj´ıc´ı hrany ◦ ∓135 (viz obr. 6.7). Pˇri counter-clockwise orientaci jsou bisektory vˇzdy orientovány smˇerem vpravo od redukovaného skeletonu. Vytvoˇrme prvn´ı aproximaci polygonu ve vzdálenosti d od redukovaného skeletonu. Souˇradnice vrchol˚ u se zmˇen´ı podle vztah˚ u: d sin(ap ) d p.y = p.y + sin(bp ) · sin(ap )

p.x = p.x + cos(bp ) ·

(6.4) (6.5)

kde bp je u ´hel bisektoru vrcholu p, αp ∈ 0; π2 je polovina u ´hlu sevˇreného inciduj´ıc´ımi hranami vrcholu p. 56

Hodnota vzd´ alenosti d mus´ı b´ yt velmi malá, aby pˇri tvorbˇe prvn´ı aproximace polygonu nedoˇslo k ˇz´ adné topologické zmˇenˇe. Obecnˇe nem˚ uˇzeme zaruˇcit, ˇze ke zmˇenˇe topologie nedojde (viz n´ asleduj´ıc´ı ˇc´ ast 6.2.3). Za pˇredpokladu, ˇze redukovan´ y skeleton je generalizov´ an a nevyskytuj´ı se v nˇem body vz´ ajemnˇe velmi bl´ızké, m˚ uˇze b´ yt d napˇr: d = 0, 001m

Tato hodnota je zvolena empiricky a je pouˇzita v implementaci algoritmu. Vztahy 6.4, 6.5 lze odvodit pomoc´ı obr. 6.10. Oznaˇcme Q[x, y] p˚ uvodn´ı vrchol, Q0 [x0 , y 0 ] hledan´ y vrchol. Dle obr. 6.10a: d = dist(P Q, P 0 Q0 ),

bq pˇredstavuje u ´hel bisektoru vrcholu Q, aq ∈ h0, πi u ´hel sevˇren´ y hranami inciduj´ıc´ımi s vrcholem Q.

Obr. 6.10: Odvozen´ı vztah˚ u pro posun vrchol˚ u po bisektorech Souˇradnice vrcholu Q0 lze vypoˇc´ıtat jako: −−→ Q0 = Q + QQ0 −−→ Kl´ıˇcov´ ym u ´kolem je tedy urˇcit sloˇzky ux ,uy vektoru QQ0 . Z obr. 6.10b plyne: lq =

d a sin 2q

57

Dle obr´ azku 6.10c m˚ uˇzeme ps´ at: ux = dx = cos(bq ) · lq uy = dy = sin(bq ) · lq

a tedy x0 = x + ux y 0 = y + uy

6.2.3

Zpˇ etn´ a rekonstrukce polygonu

Oznaˇcme prvn´ı aproximaci polygonu P jako PA = {p1 , p2 , . . . , pn }, kde pi = [xi , yi ] pˇredstavuje vrchol PA . Rozˇsiˇrujme PA posunován´ım vrchol˚ u pi po osách u ´hl˚ u inciduj´ıc´ıch hran smˇerem ven, dokud nedos´ ahneme poˇzadované ˇs´ıˇrky w. Jedná se o postup inverzn´ı ke konstrukci straight skeletonu, nazvˇeme ho zpˇetnou rekonstrukc´ı polygonu P. Podobnˇe jako pˇri konstrukci skeletonu pˇri nˇem docház´ı k nˇekolika typ˚ um událost´ı (topologick´ ym zmˇen´ am), viz obr. 6.11: • ud´ alost vertex-vertex - obr. 6.11b), docház´ı k zániku hrany • ud´ alost vertex-hrana - obr. 6.11a), docház´ı ke stˇretu nekonvexn´ıho vrcholu a protilehlé hrany, polygon je rozdˇelen na dvˇe ˇcásti. Podobnˇe m˚ uˇze doj´ıt ke stˇretu dvou nekonvexn´ıch vrchol˚ u proti sobˇe, je to v podstatˇe hraniˇcn´ı situace stˇretu vertexu a hrany • ud´ alost hrana-hrana - obr. 6.11c,d) - dojde ke stˇretu rovnobˇeˇzn´ ych hran, d˚ usledkem ’ je bud vznik d´ıry nebo jednoduchého polygonu Princip konstrukce. Pro spr´ avnou konstrukci nového polygonu je nutné uvedené ud´ alosti správnˇe detekovat (algoritmus 6.3). Pro detekci je pouˇzit stejn´ y princip jako vyuˇzili FELKEL ˇ ALEK, ´ a OBDRZ 1998. Pro kaˇzd´ y vertex je urˇcen nejbliˇzˇs´ı pr˚ useˇc´ık: • bud’ jako pr˚ useˇc´ık s bisektory soused´ıc´ıch vertex˚ u, • nebo jako pr˚ useˇc´ık vertexu a hrany. Pr˚ useˇc´ık vertexu a hrany je urˇcován stejn´ ym zp˚ usobem jako pˇri konstrukci straight skeletonu pro nekonvexn´ı polygony (ˇca´st 4.3). Je také vyuˇzita datová struktura SLAV. Pr˚ useˇc´ıky I jsou stejnˇe jako u Felkela a Obdrˇzálka ukládány v prioritn´ı frontˇe PQ a zpracovávány podle vzdálenosti d od generuj´ıc´ı hrany (alg. 6.3). Algoritmus 6.4 popisuje zpracován´ı detekovan´ ych událost´ı. Oznaˇcme vrcholy generuj´ıc´ı I jako vLEF T , vRIGHT . V pˇr´ıpadˇe pr˚ useˇc´ıku vzniklého jako ud´ alost vertex-hrana vLEF T = vRIGHT . 58

Obr. 6.11: Topologické zmˇeny polygonu pˇri rekonstrukci polygonu. (a) stˇretnut´ı vertexu a protˇejˇs´ı hrany - vznik d´ıry, (b) stˇretnut´ı dvou vertex˚ u - zánik hrany, (c) stˇretnut´ı dvou hran - vznik d´ıry, (d) - stˇretnut´ı dvou hran bez vzniku d´ıry Algoritmus 6.3 - Identifikace ud´ alost´ı: urˇ cen´ı pr˚ useˇ c´ık˚ u 1. for ∀ vrchol vi ∈ P 2.

spoˇ cti pr˚ useˇ c´ ıky I1 , I2 bisektor˚ u bv , bprev a bv , bnext

3.

urˇ ci vzd´ alenosti d1 = d(I1 , e1 = vi vprev ) a d2 = d(I2 , e2 = vi vnext )

4.

if (bv > π)

5.

urˇ ci pr˚ useˇ c´ ık B - viz. ˇ c´ ast 4.3

6.

urˇ ci vzd´ alenost d3 = d(B, e), e je protilehl´ a hrana

7.

urˇ ci dmin ∈ {d1 , d2 , d3 }

8.

if (dmin == d1 )

9.

P Q ← I1 , I1 .type == convex

10. else if (dmin == d2 ) 11.

P Q ← I2 , I2 .type == convex

12. else 13.

// (dmin == d3 )

P Q ← I3 , I3 .type == nonconvex

Algoritmus 6.4 - Zpracov´ an´ı ud´ alost´ı 1. while (P Q ! empty) 2.

PQ → I

3.

P Q.pop

4.

if (vLEF T .done and vRIGHT .done)

5. 6.

continue; else

59

7.

if (I.type == convex)

8.

vytvoˇ r vrchol U na m´ ıstˇ e I

9.

vLEF T .done = true, vRIGHT .done = true

10.

modifikuj LAV - viz ˇ c´ ast 4.3

11.

urˇ ci IU - alg. 6.3

12.

P Q ← IU

13.

if (I.type == nonconvex)

14.

vytvoˇ r vrcholy U1 , U2 na m´ ıstˇ e I

15.

vLEF T .done = true, vRIGHT .done = true

16.

modifikuj SLAV - viz ˇ c´ ast 4.3

17.

urˇ ci IU 1 , IU 2 - alg. 6.3

18.

P Q ← IU 1 , P Q ← IU 2

Objasnˇeme jeˇstˇe v dalˇs´ım textu zpracován´ı události hrana-hrana - bude zˇrejmé, ˇze i tento typ ud´ alosti lze detekovat a zpracovat stejn´ ym zp˚ usobem jako události vertex-vertex a vertexhrana. Ud´ alost hrana-hrana. K této události m˚ uˇze doj´ıt v pˇr´ıpadˇe, kdy se spolu stˇretnou dvˇe rovnobˇeˇzné hrany. Ud´ alost hrana-hrana m˚ uˇze b´ yt dvoj´ıho typu: bud’ pˇri n´ı docház´ı zároveˇ n i k zániku hrany (obr. 6.11d), nebo pouze ke vzniku d´ıry (obr. 6.11c). Rozeberme nyn´ı obˇe z tˇechto situac´ı na pˇr´ıkladu obr. 6.12, události budou zpracovány v poˇrad´ı 1-4: • ud´ alost 1 a 2: dojde k detekci dvou událost´ı ve stejné vzdálenosti od p˚ uvodn´ıho polygonu. Ud´ alost 1 je typu rozdˇelen´ı (událost vertex-hrana), událost 2 je typu z´ anik (ud´ alost vertex-vertex). Jako prvn´ı bude zpracována událost 1 - dojde k rozdˇelen´ı LAV na dvˇe ˇc´ asti. Jako druh´ a bude zpracována událost 2 - LAV tvoˇren´ y vrcholy na m´ıstˇe pr˚ useˇc´ık˚ u 1 a 2 bude m´ıt nulovou plochu a pro v´ ysledn´ y polygon jiˇz nemá v´ yznam, • ud´ alost 3 a 4: dojde k detekci dvou událost´ı ve stejné vzdálenosti, obˇe budou typu rozdˇelen´ı (ud´ alost vertex-hrana). Pˇri zpracován´ı události 3 se LAV znovu rozpadne. Pˇri zpracov´ an´ı ud´ alosti 4 vznikne dalˇs´ı LAV, jeden z nich je tvoˇren pouze vrcholy na m´ıstˇe pr˚ useˇc´ık˚ u 3 a 4, opˇet bude m´ıt nulovou plochu a pro v´ ysledn´ y polygon jiˇz nem´ a v´ yznam. V pˇredchoz´ım textu byla objasnˇena detekce a zpracován´ı událost´ı, k nimˇz doch´ az´ı pˇri zpˇetné rekonstrukci polygonu. V následuj´ıc´ım textu budou vyloˇzeny zmˇeny, které byly do algoritmu Felkela a Obdrˇz´ alka zabudovány, aby mohla b´ yt zpˇetná rekonstrukce u ´spˇeˇsnˇe dokonˇcena. Pˇripomeˇ nme, ˇze algoritmus Felkela a Obdrˇzálka neaktualizuje souˇradnice vˇsech vrchol˚ u polygonu P pˇri zpracov´ an´ı ud´ alosti I. Dojde pouze k zapojen´ı vrcholu V na m´ıstˇe pr˚ useˇc´ıku I do SLAV (viz obr. 6.13b). Po zpracován´ı vˇsech událost´ı je proto nutné aktualizovat souˇradnice dosud nezpracovan´ ych vrchol˚ u rekonstruovaného polygonu - t´ım je z´ıskán fináln´ı rekonstruovan´ y polygon (obr. 6.13c). 60

Obr. 6.12: Stˇret rovnobˇeˇzn´ ych hran Do datové struktury Felkela a Obdrˇzálka byly proto pˇridány dva nové atributy pro vrcholy ve SLAV: double Idist a int offset. Nav´ıc je pˇridána globáln´ı promˇenná int sizeOfOffset, jej´ıˇz funkcionalita souvis´ı s atributem offset. Vyloˇzme nejprve funkcionalitu atributu Idist.

Obr. 6.13: Zapojen´ı vrcholu na m´ıstˇe pr˚ useˇc´ıku I do SLAV Atribut Idist. Necht’ PA pˇredstavuje prvn´ı aproximaci polygonu P . Atribut Idist udrˇzuje pro kaˇzd´ y vrchol pi ∈ PA hodnotu: pi .Idist = d(pi , PA )

Pˇred zapoˇcet´ım rekonstrukce polygonu je tedy hodnota atributu pro kaˇzd´ y vrchol pi ∈ PA nulová.

61

Hodnota w (viz obr. 6.13) pˇredstavuje ukonˇcovac´ı podm´ınku zpˇetné rekonstrukce polygonu. Oznaˇcme vzd´ alenost d(I, 45) na obr. 6.13a jako wakt - pˇredstavuje vzdálenost pr˚ useˇc´ıku I od generuj´ıc´ı hrany. Na obr. 6.13b je vrchol 9 na m´ıstˇe pr˚ useˇc´ıku I zapojen do LAV a je tˇreba mu nastavit hodnotu atributu Idist: Idist = wakt ˇ adn´ Z´ y dalˇs´ı pr˚ useˇc´ık, pro kter´ y by platilo wakt ≤ w

(6.6)

neexistuje. Zpracov´ av´ an´ı pr˚ useˇc´ık˚ u z prioritn´ı fronty je ukonˇceno a dle algoritmu 6.5 dojde k v´ ypoˇctu souˇradnic v´ ysledného rekonstruovaného skeletonu. Atribut offset. Atribut offset udrˇzuje pro kaˇzd´ y vrchol v informaci, ke kterému LAV n´ aleˇz´ı. Pˇr´ısluˇsnost k LAV je vyuˇzita pˇri exportu rekonstruovaného polygonu do shapefilu, také je udrˇzena informace o poˇctu LAV ve SLAV. Pˇred zapoˇcet´ım zpracov´ an´ı je nastavena globáln´ı promˇenná sizeOfOffset a kaˇzdému vrcholu pi ∈ PA nastavena hodnota atributu offset: sizeOfOffset = 1 p.offset = sizeOfOffset Dojde-li k ud´ alosti vedouc´ı k rozpadu LAV, je hodnota promˇenné sizeOfOffset nav´ yˇsena o 1. Oznaˇcme jeden LAV jako LAV 1, druh´ y jako LAV 2. Pro kaˇzd´ y vrchol v ∈ LAV 2 aktualizujme hodnotu offset: v.offset = sizeOfOffset Algoritmus 6.5 - Fin´ aln´ı aktualizace souˇ radnic rekonstruovan´ eho polygonu 1. for ∀ vrchol p ∈ P 2.

if (! p.done)

3.

double l = w − p.Idist

4.

aktualizuj souˇ radnice vrcholu p podle vztah˚ u 6.4, 6.5 (ˇ c´ ast 6.2.2), kde d = l

62

Posledn´ı neurˇcenou hodnotou je ukonˇcovac´ı podm´ınka w zpˇetné rekonstrukce polygonu, která urˇcuje vzd´ alenost rekonstruovaného polygonu P od prvn´ı aproximace polygonu PA . Stanoven´ı hodnoty w. Hodnota w je nezbytná pro ukonˇcen´ı bˇehu algoritmu. Mˇela by b´ yt volena s ohledem na data vstupuj´ıc´ı do agregaˇcn´ıho algoritmu. Plocha a poloha agregovaného polygonu by se mˇely co nejv´ıce pˇribliˇzovat charakteristikám p˚ uvodn´ıch polygon˚ u. Souˇcasnˇe by hodnota w mˇela b´ yt vˇetˇs´ı neˇz kritéria ˇcitelnosti pro dané mˇeˇr´ıtko. Pro kaˇzd´ y nov´ y polygon P bude tedy hodnota w r˚ uzná. V navrˇzeném algoritmu byl zvolen pomˇernˇe jednoduch´ y zp˚ usob urˇcen´ı hodnoty w, je vˇsak docela efektivn´ı: Pn Si 1 · w = Pi=0 m j=0 lj 2

(6.7)

kde n je poˇcet p˚ uvodn´ıch polygon˚ u, Si je plocha kaˇzdého z polygon˚ u, m je poˇcet segment˚ u kostry agregovaného polygonu, lj je délka kaˇzdého segmentu.

Obr. 6.14: Stanoven´ı hodnoty w Koeficient 12 je ve vztahu pro v´ ypoˇcet w z prostého d˚ uvodu - w urˇcuje pouze polovinu ˇs´ıˇrky v´ ysledného rekonstruovaného polygonu, viz obr. 6.14.

63

7

IMPLEMENTACE ALGORITMU

Algoritmus byl implementován pomoc´ı volnˇe dostupn´ ych knihoven CGAL, Boost a ShapeLib v prostˇred´ı Microsoft Visual C++ 2010 Express. Zde mus´ı b´ yt uvedeno, ˇze tento postup se m´ırnˇe odliˇsuje od zad´ an´ı diplomové práce. Podle zadán´ı mˇel b´ yt algoritmus implementov´ an jako nadstavba pro program ArcGIS. Od této implementace jsem vˇsak musela odstoupit z nˇekolika d˚ uvod˚ u. Podle specifikac´ı poˇzadavk˚ u pro SDK ArcGISu (ESRI, ArcGIS Resource Center ) je pro programován´ı v C++, na rozd´ıl od Javy a .NET, nutn´ y ArcGIS Engine Runtime a komerˇcn´ı verze Microsoft Visual Studia. Komerˇcn´ı verze VS sice poskytuj´ı 90-denn´ı trial verzi, ovˇsem v pr˚ ubˇehu této doby jsem nemˇela k dispozi ArcGIS Engine Runtime, kter´ y se pro verzi 10 nepodaˇrilo z´ıskat ani po konzultaci s firmou ARCDATA Praha. Na katedˇre dostupn´ a verze 9.2 zase nemohla b´ yt naistalována z d˚ uvodu naistalované novˇejˇs´ı verze ArcGIS Desktopu 10 s roˇcn´ı licenc´ı poskytnutou katedrou. Tyto problémy s licencemi tak vy´ ustily v nutnost ˇreˇsit vznikl´ y problém jinak. Z uˇzivatelského hlediska sice v´ ysledné ˇreˇsen´ı pˇrináˇs´ı nutnost spustit samostatn´ y program mimo prostˇred´ı ArcGIS, na druhé stranˇe vˇsak také pracuje s nativn´ım formátem ESRI (shapefile) a nav´ıc uˇzivatel nemus´ı m´ıt tento komerˇcn´ı software (vˇcetnˇe nutn´ ych extenz´ı) v˚ ubec naistalovan´ y. Prohl´ıˇzet, vyb´ırat a editovat shapefile je moˇzné napˇr. pomoc´ı open source programu QuantumGIS (http://www.qgis.org/). V dalˇs´ıch ˇc´ astech jsou nejprve struˇcnˇe pˇredstaveny vyuˇzité knihovny a dále následuje vlastn´ı postup implementace.

7.1

Knihovny CGAL, Boost a ShapeLib

Knihovna CGAL (Computational Geometry Algorithms Library) je volnˇe dostupn´ a knihovna napsan´ a v jazyce C++, která umoˇzn ˇuje pˇr´ıstup k efektivn´ım a spolehliv´ ym algoritm˚ um v oblasti v´ ypoˇcetn´ı geometrie, jako jsou napˇr´ıklad triangulace, Voronoi teselace nebo tvorba konvexn´ıch ob´ alek. Projekt byl zaloˇzen v roce 1996 sedmi v´ yzkumn´ ymi institucemi a od té doby se st´ ale rozˇsiˇruje. V souˇcasné dobˇe je nejnovˇejˇs´ı verz´ı verze 4.0 uvolnˇen´ a v bˇreznu 2012. Pro zpracov´ an´ı diplomové práce byla pouˇzita verze 3.9. Boost knihovny jsou taktéˇz psány v jazyce C++. Jejich instalace je nutná uˇz pˇri instalován´ı knihovny CGAL, a pro dalˇs´ı práci byla nav´ıc vyuˇzita knihovna BGL - The Boost Graph Library, kter´ a implementuje rozliˇcné grafové algoritmy. Nejnovˇejˇs´ı verze boost knihoven je 1.49.0, uvolnˇen´ a v u ńoru 2012, pro zpracován´ı diplomové práce byla vyuˇzita verze 1.47.0. 64

Knihovna ShapeLib napsan´ a v C slouˇz´ı pro ˇcten´ı, zápis a editaci shapefil˚ u. Jej´ım autorem je Frank Warmerdam, prvn´ı verze je z roku 1998. Dokumentace knihovny je struˇcná, ale vzhledem k jej´ı jednoduchosti dostateˇcná. Nev´ yhodou je neexistence veˇrejného fóra, ale dotazy mohou b´ yt pos´ıl´ any pˇr´ımo autorovi. Nejnovˇejˇs´ı verze je 1.3.0, diplomová práce byla zpracov´ ana pomoc´ı verze 1.2.10.

7.2

Urˇ cen´ı budov pro agregaci

Fin´ aln´ım v´ ystupem prvn´ı fáze algoritmu je dvojrozmˇern´ y vektor typu vector >, nesouc´ı v kaˇzdém ˇrádku seznam ID polygon˚ u, které se maj´ı agregovat. ID ˇrádku je z´ aroveˇ n ID nového polygonu, vzniklého z odpov´ıdaj´ıc´ıch záznam˚ u. V následuj´ıc´ıch podkapitol´ ach je rozveden postup, jak k tomuto fináln´ımu poli dojdeme. 7.2.1

Naˇ cten´ı shapefil˚ u

Jako prvn´ı je poˇzadov´ ano zad´ an´ı cest k shapefil˚ um (k samostatn´ ym soubor˚ um s koncovkou .shp, ne k feature classes uloˇzen´ ym v geodatabázi) se zdrojov´ ymi daty. Jeden shapefile by mˇel obsahovat polygonovou vrstvu budov. Tato vrstva mus´ı splˇ novat následuj´ıc´ı podm´ınky. • polygony nesm´ı obsahovat d´ıry, • orientace polygon˚ u mus´ı b´ yt bˇeˇzná pro shapefile (uzavˇren´ y polygon je zadán body po smˇeru hodinov´ ych ruˇciˇcek), • vrstva mus´ı m´ıt v atributové tabulce sloupec se spoˇctenou plochou polygonu (s názvem Shape Area“). ” Druh´ a vrstva je vrstva liniov´ a obsahuj´ıc´ı (osy) cestn´ı s´ıtˇe. Shapefily jsou naˇc´ıt´ any pomoc´ı funkc´ı knihovny ShapeLib. Funkc´ı SHPOpen se vytvoˇr´ı objekt typu SHPHandle, kter´ y je dále vyuˇzit pro zjiˇstˇen´ı informac´ı o shapefilu, pˇredevˇs´ım typu geometrie (point, line, polygon, multipoint) a poˇctu záznam˚ u (viz kód 7.1).

65

Kaˇzd´ y prvek shapefilu je reprezentován objektem typu SHPObject, kter´ y je návratov´ ym typem funkce SHPReadObject. Procházen´ım shapefilu se dostáváme ke konkrétn´ım prvk˚ um, jejichˇz souˇradnice lze uloˇzit do vhodné datové struktury. Vzhledem k tomu, ˇze k dalˇs´ım operac´ım s polygonem je vyuˇzita knihovna CGAL, jsou souˇradnice ukládány do datov´ ych struktur Point 2 a 2D Polygon této knihovny. Linie jsou naˇc´ıtány do struktury Segment 2 (tj. u ´seˇcka). Pˇri naˇc´ıt´ an´ı jednotliv´ ych prvk˚ u shapefilu je kontrolována plocha objektu, nebot’ algortimus nebude zpracov´ avat budovy s plochou menˇs´ı Smin (ˇcást 6.2). Hodnota plochy je naˇc´ıt´ ana pˇr´ımo z atributové tabulky (souboru .dbf) shapefilu. Podobnˇe jako v pˇr´ıpadˇe ˇcten´ı geometrie je nutné pouˇz´ıt funkci pro otevˇren´ı databáze DBFOpen (kód 7.2).

Do promˇenné area je naˇc´ıt´ ana plocha ze sloupce Shape Area“ a je porovnávána s kritic” kou hodnotou Smin . Pokud je plocha menˇs´ı, geometrie objektu se v˚ ubec nenaˇcte a pokraˇcuje se dalˇs´ım prvkem. 7.2.2

Voronoi diagram a urˇ cen´ı sousednosti polygon˚ u

Dalˇs´ı f´ az´ı je vytvoˇren´ı Voronoi diagramu nad centroidy naˇcten´ ych polygon˚ u. Voronoi diagramy jsou n´ aslednˇe vyuˇzity pro hledán´ı sousedn´ıch polygon˚ u. Centroidy jsou vypoˇc´ıtáv´ any pro kaˇzd´ y polygon ihned po jeho naˇcten´ı dle vztah˚ u 6.1 a 6.2 a uloˇzeny do samostatného vektoru. Z´ aroveˇ n je kaˇzdému centroidu pˇriˇrazen index shodn´ y s ID polygonu. Voronoi diagram je generov´ an pomoc´ı knihovny CGAL. Algoritmus implementoval Menelaos Karavelas a to ve formˇe adaptoru 2D Delaunay triangulace. V´ ysledná teselace je uloˇzena ve struktuˇre DCEL, kter´ a umoˇzn ˇuje standardn´ı operace: procházet hrany bunˇek, zjiˇst’ovat sousedn´ı buˇ nky, proch´ azet hrany vycházej´ıc´ı z daného vertexu a dalˇs´ı. Z uˇzivatelského hlediska jsou diagramy konstruov´ any pomoc´ı pˇr´ıkazu insert(gener´ ator buˇ nky): vd.insert(centr[i]); Pro nalezen´ı navz´ ajem soused´ıc´ıch polygon˚ u jsou postupnˇe procházeny vˇsechny buˇ nky vytvoˇrené Voronoi teselace. Pomoc´ı funkce dual() je pˇr´ıstupn´ y generátor aktuáln´ı buˇ nky. Procház´ı se hrany aktu´ aln´ı buˇ nky a pro kaˇzdou z nich je urˇcen sousedn´ı centroid. Spojnice centroid˚ u vytvoˇr´ı u ´seˇcku. Testuje se, zda prot´ıná nˇekterou z lini´ı cestn´ı s´ıtˇe postupn´ ym testov´ an´ım, dokud se najde/nenajde pr˚ useˇc´ık. Pokud neprot´ınaj´ı, vypoˇc´ıtá se minimáln´ı vzd´ alenost mezi pˇr´ısluˇsn´ ymi polygony, viz ˇcást 4.2. Pokud je vzdálenost menˇs´ı neˇz dmax je index testovaného centroidu (tj. i polygonu) pˇridán do spojového seznamu (linked list) aktuáln´ıho centroidu (polygonu). T´ım je vytvoˇren seznam soused˚ u pro agregaci pro kaˇzd´ y polygon (kontejner vecRef2) - dle alg. 6.1, viz kód 7.3. 66

67

Pro nalezen´ı seznam˚ u budov pro agregaci je pouˇzit algoritmus prohledáván´ı do hloubky (viz ˇcást 6.1). Jak bylo uvedeno v ˇcásti 4.5.2, v´ ysledn´ ymi produkty tohoto algoritmu jsou ˇcasové znaˇcky otevˇren´ı a uzavˇren´ı vrchol˚ u a vektor pˇredch˚ udc˚ u. Tyto vektory nejsou v naˇsem pˇr´ıpadˇe potˇreba, naopak jsou zavedeny dva nové dvojrozmˇerné vektory paths a ToAggreg. Oba jsou typu vector>. Protoˇze pˇred zaˇcátkem prohledáván´ı nev´ıme, kolik izolovan´ ych podstrom˚ u (tj. kolik skupin polygon˚ u pro agregaci) bude v grafu objeveno, je pomocnou strukturou pˇri prohled´ aván´ı do hloubky vektor paths, jehoˇz délka odpov´ıdá poˇctu polygon˚ u. Po ukonˇcen´ı prohled´ aván´ı jsou hodnoty vektoru paths pˇrekop´ırovány do vektoru ToAggreg, aby se eliminovaly pr´ azdné ˇrádky tohoto vektoru. Zároveˇ n pak poˇrad´ı ve vektoru ToAggreg urˇcuje index nového agregovaného polygonu (kód 7.4).

7.3 7.3.1

Vlastn´ı agregace Konstrukce straight skeletonu a nalezen´ı minim´ aln´ı kostry grafu

Po naplnˇen´ı kontejneru ToAggreg je pro kaˇzd´ y polygon v nˇem obsaˇzen´ y zkonstruov´ an straight skeleton pomoc´ı funkce knihovny CGAL create interior straight skeleton 2. V´ ysledn´ a skeletonizace je uloˇzena v datové struktuˇre HDS, která umoˇzn ˇuje podobné operace jako struktura DCEL. Z vytvoˇren´ ych straight skeleton˚ u jsou vybrány pouze vnitˇrn´ı vrcholy - z´ıskáme redukované straight skeletony. Pro zjiˇstˇen´ı, zda se jedná o vnitˇrn´ı uzel skeletonu, je moˇzné vyuˇz´ıt funkci CGAL is skeleton(). Odpov´ıdaj´ıc´ı uzly jsou naˇc´ıtány do dvojrozmˇerného vektoru vector> pointsOfGraph. Dále jsou pˇripravena data pro spuˇstˇen´ı funkce pro nalezen´ı minim´ aln´ı kostry grafu. Jsou vytvoˇreny vˇsechny moˇzné (ve své podstatˇe orientované) hrany mezi body, jejichˇz indexy jsou uloˇzeny do kontejneru vector> Edges a zároveˇ n jsou vypoˇc´ıtáv´ any jejich v´ ahy a ukl´ ad´ any do vektoru vector> Eweights. Naplnˇené kontejnery pˇredstavuj´ı vstupn´ı argumenty kruskalova algoritmu pro nalezen´ı minimáln´ı kostry grafu. Funkce je z knihovny BGL (k´ od 7.5 a 7.6). Nalezen´ a kostra grafu, tj. redukovan´ y skeleton agregovaného polygonu, je uloˇzena ve formˇe spojové reprezentace grafu do nového kontejneru vector>> MST. Tento kontejner je trojrozmˇern´ y, protoˇze udrˇzuje informaci o kaˇzdém novém polygonu, ke kaˇzdému polygonu udrˇzuje seznam vrchol˚ u a ke kaˇzdému vrcholu seznam soused´ıc´ıch vrchol˚ u.

68

69

7.3.2

Generalizace redukovan´ eho skeletonu a tvorba prvn´ı aproximace polygonu

Podle algoritmu 6.2 jsou na základˇe informac´ı z kontejneru MST uloˇzeny vˇsechny vˇetve kaˇzdého polygonu do kontejneru vector>> branches. Tento kontejner je opˇet trojrozmˇern´ y, protoˇze nese informaci o kaˇzdém polygonu, ke kaˇzdému polygonu udrˇzuje seznam vˇetv´ı a kaˇzd´ a vˇetev je tvoˇrena posloupnost´ı vrchol˚ u (jejich index˚ u). Struktura seznam (list) je nejen pro kontejner branches pouˇzita kv˚ uli následuj´ıc´ım v´ yhodám: • seznam umoˇzn ˇuje pˇrid´ av´ an´ı prvk˚ u na konec i na zaˇcátek seznamu, • seznam umoˇzn ˇuje rychlé smazán´ı vˇsech prvk˚ u dané hodnoty. Prvn´ı v´ yhoda seznamu je vyuˇzita uˇz pˇri sestavován´ı vˇetv´ı, nebot’ kv˚ uli správnému poˇrad´ı vrchol˚ u je nutné pˇri prohled´ av´ an´ı pˇridávat vrcholy jak na zaˇcátek, tak na konec seznamu. Následuje generalizace vˇetv´ı podle algoritmu 4.6 (Douglas-Peucker) a odstranˇen´ı krátk´ ych vˇetv´ı. V´ ystupem algoritmu vˇsak nen´ı seznam bod˚ u, které maj´ı v dané vˇetvi z˚ ustat. Naopak, v´ ystupem je kontejner vector<list> toErase, kter´ y nese seznam index˚ u vrchol˚ u, ˇıˇrka koridoru h pro Douglas-Peucker algoritmus je urˇcena dle vztahu které se maj´ı smazat. S´ 6.3. Dále je vytvoˇren kontejner vector<list> finalSkeleton. V nˇem je uloˇzen topologicky spr´ avn´ y a proti smˇeru hodinov´ ych ruˇciˇcek orientovan´ y redukovan´ y skeleton agregovaného polygonu (viz ˇc´ ast 6.2.2). Zb´ yvá tyto dva kontejnery, finalSkeleton a toErase, zkombinovat: ze seznamu finalSkeleton jsou smazány vˇsechny indexy vrchol˚ u, které jsou uloˇzeny v seznamu toErase - z´ıskáme generalizovan´ y redukovan´ y skeleton. Posledn´ım krokem pˇred samotnou rekonstrukc´ı polygonu je tvorba jeho prvn´ı aproximace, kter´ a vznikne posunut´ım bod˚ u po bisektorech podle vztah˚ u 6.4 a 6.5, kdy d = 0, 001 (viz ˇcást 6.2.2). Souˇradnice bod˚ u jsou naˇc´ıtány z kontejneru pointsOfGraph a fináln´ı vrcholy jsou uloˇzeny v kontejneru vector> finalPoints. 7.3.3

Zpˇ etn´ a rekonstrukce polygonu

Jak bylo uvedeno v ˇc´ asti 6.2.3, pro zpˇetnou rekonstrukci polygonu byla vyuˇzita datov´ a struktura SLAV Felkela a Obdrˇz´ alka, která byla jen m´ırnˇe modifikována. Základn´ı definované tˇr´ıdy a struktury jsou n´ asleduj´ıc´ı: • tˇr´ıda PointRec: nese souˇradnice vrchol˚ u (double x, double y) • tˇr´ıda RayRec: slouˇz´ı pro uloˇzen´ı polopˇr´ımek - bisektor˚ u a hran • struktura Vertex: ukl´ ad´ a jednotlivé vrcholy v LAV • struktura Intersection: slouˇz´ı pro uloˇzen´ı souˇradnic, vzdálenosti a typu detekované ud´ alosti • tˇr´ıda VertexList: udrˇzuje dvojit´ y kruhov´ y seznam 70

Cel´ a datov´ a struktura i definované algoritmy jsou pomˇernˇe komplexn´ı a popisovat zde celou funkcionalitu algoritmu by nebylo vhodné: • za prvé, jedn´ a se z velké ˇca´sti o pˇrejat´ y kód (z d˚ uvodu velké podobnosti funkcionality a vhodnosti datové struktury), • za druhé, k´ od je rozs´ ahl´ y a dávat do textu jen nˇekteré ukázky by vyˇzadovalo velké mnoˇzstv´ı vysvˇetluj´ıc´ıho textu. Pro zájemce bude proto patrnˇe nejvhodnˇejˇs´ı pod´ıvat se pˇr´ımo do zdrojového k´ odu (viz pˇr´ıloha 1), kter´ y je podrobnˇe okomentován. Zde bude uvedena jen z´ akladn´ı funkcionalita algoritmu. Vstupn´ı a v´ ystupn´ı typy argument˚ u funkce pro zpˇetnou rekonstrukci polygonu createOffset jsou n´ asleduj´ıc´ı: vector createOffset(vector &input, double offsetDistance)

Vstupn´ı vektor input obsahuje seznam vrchol˚ u prvn´ı aproximace polygonu v counterclockwise orientaci. Argument offsetDistance pˇredstavuje ukonˇcovac´ı podm´ınku w. Navrátov´ ym typem je vector. Pˇri naˇc´ıt´ an´ı vstupn´ıho polygonu jsou body typu PointRec ukládány do struktury VertexList, kter´ a je tvoˇrena jednotliv´ ymi vertexy. Kaˇzd´ y Vertex je inicializován tˇremi body - prvn´ı nese souˇradnice vlastn´ıho vertexu, dalˇs´ımi dvˇema jsou pˇredchoz´ı a následuj´ıc´ı bod vstupn´ıho polygonu (viz k´ od 7.7). Pˇri naˇc´ıtán´ı je vypoˇcten bisektor a definovány soused´ıc´ı hrany (atributy axis, leftLine, rightLine). Zapojen´ı do LAV (atributy prevVertex, nextVertex) je provedeno aˇz po naˇcten´ı vˇsech bod˚ u polygonu, nebot’ se jedná o pointery. Atributy leftVertex a rightVertex jsou ukazatele na vrcholy, z nichˇz dan´ y vrchol vznikl.

Druh´ y z uveden´ ych konstruktor˚ u slouˇz´ı pro vytvoˇren´ı Vertexu na m´ıstˇe p˚ uvodn´ıho pr˚ useˇc´ıku - Vertex je inicializov´ an souˇradnicemi pr˚ useˇc´ıku a pointery na vrcholy v LAVu, z nichˇz nov´ y vrchol vznik´ a. Do struktury jsou nav´ıc pˇrid´ any atributy double Idist a int offset. Ty slouˇz´ı pro fin´ aln´ı rekonstrukci polygonu - viz ˇc´ ast 6.2.3. Po zpracov´ an´ı vˇsech pr˚ useˇc´ık˚ u splˇ nuj´ıc´ıch podm´ınku 6.6 jsou podle algoritmu 6.5 aktualizovány souˇradnice v´ ysledného rekonstruovaného polygonu, viz kód 7.8.

71

Z´ apis do shapefilu. N´ avratov´ ym typem funkce createOffset je vector, ve kterém jsou uloˇzeny vrcholy rekonstruovaného polygonu v clockwise orientaci (orientace pro uzavˇren´ y polygon v shapefilu). Ve SLAV jsou uloˇzeny vˇsechny LAV, tedy vˇcetnˇe dˇer. Pro zjednoduˇsen´ı z´ apisu do shapefilu je vˇsak navrácen pouze ten LAV, kter´ y urˇcuje konturu uzavˇreného polygonu. Pro tvorbu shapefilu a z´ apis dat je podobnˇe jako pˇri naˇc´ıtán´ı vyuˇzita knihovna ShapeLib. Do shapefilu je spoleˇcnˇe s geometri´ı samotnou uloˇzen atribut double origArea, ve kterém je uloˇzena hodnota souˇctu ploch p˚ uvodn´ıch polygon˚ u (kód 7.9).

72

7.4

Vytvoˇ ren´ y n´ astroj

Vytvoˇren´ y n´ astroj je ve formˇe konzolové aplikace pro Windows 32-bit. Uˇzivatelsk´ ym vstupem jsou cesty k shapefil˚ um polygonové a liniové vrstvy, m´ısto uloˇzen´ı a název novˇe vytváˇreného shapefilu. D´ ale je poˇzadována hodnota Smin a mˇeˇr´ıtkové ˇc´ıslo M . V´ ystupem je shapefile obsahuj´ıc´ı agregované polygony.

73

8

ˇ ´ VYSLEDKY ´ DOSAZEN E A JEJICH ZHODNOCENÍ

Generalizaˇcn´ı algoritmus byl testován na dev´ıti vzorov´ ych u ´zem´ıch, které reprezentuj´ı ˇsest dále uveden´ ych typ˚ u z´ astavby, typick´ ych pro ˇceské prostˇred´ı. Algoritmus byl pro kaˇzdé u ´zem´ı spuˇstˇen ve dvou m´ır´ ach generalizace - s parametry odpov´ıdaj´ıc´ı mˇeˇr´ıtk˚ um 1:25 000 a 1:50 000. Ve stejn´ ych m´ır´ ach generalizace byla vzorová data agregována i nástrojem pro agregaci zabudovaném v SW ArcGIS. Dosaˇzené v´ ysledky jsou vzájemnˇe porovnány. Z kartografického hlediska jsou v´ ysledky zhodnoceny vizuálnˇe. Hodnoceno je pˇredevˇs´ım: • zachov´ an´ı pravo´ uhlosti budov, • zachov´ an´ı polohové pˇresnosti budov, • celkov´ a kartografick´ a pˇrirozenost v´ ysledk˚ u. Z objektivn´ıho hlediska je hodnocena zmˇena plochy a posun tˇeˇziˇstˇe agregovan´ ych budov. Kapitola je rozdˇelena do ˇctyˇr ˇcást´ı - prvn´ı popisuje testovac´ı data, druhá definuje a charakterizuje vybran´ a vzorov´ au ´zem´ı, tˇret´ı posuzuje dosaˇzené v´ ysledky a ˇctvrtá obecnˇe hodnot´ı navrˇzen´ y algoritmus na z´ akladˇe dosaˇzen´ ych v´ ysledk˚ u.

74

8.1

Testovac´ı data

Algoritmus byl testov´ an na datech ZABAGED a CEDA, data byla k dispozici pro západn´ı ˇcást mˇesta Prahy a pro u ´ˇcely testován´ı byla poskytnuta katedrou kartografie a aplikované geoinformatiky PˇrF UK. Z datab´ aze ZABAGED byla pouˇzita vrstva 1.02 - budova jednotliv´ a nebo blok budov, z datab´ aze CEDA byla pouˇzita vrstva os cestn´ı s´ıtˇe pro Prahu. Obˇe datové vrstvy jsou v mˇeˇr´ıtku odpov´ıdaj´ıc´ı podrobnosti 1:10 000.

8.2

Vybran´ a vzorov´ au ´ zem´ı

Pro u ´ˇcely testov´ an´ı bylo definováno ˇsest typ˚ u zástavby, typick´ ych pro ˇceské prostˇred´ı, aby mohla b´ yt zhodnocena efektivita algoritmu z kartografického hlediska. Pro kaˇzd´ y z typ˚ u byla vybr´ ana jedna nebo v´ıce lokalit, na nichˇz prob´ıhalo testován´ı. Lokality jsou menˇs´ıho rozsahu, s poˇctem vstupn´ıch polygon˚ u < 250 (kromˇe u ´zem´ı 2). Uved’me jednotlivé typy zástavby a konkrétn´ı testovac´ı lokality (viz obr. 8.1). V dalˇs´ım textu je struˇcnˇe charakterizujme. • s´ıdliˇstˇe - s´ıdliˇstˇe Petˇriny, Nové Butovice a Velká Ohrada • ˇctvrti rodinn´ ych dom˚ u a vil - Vokovice, Suchdol • bloky starˇs´ıch budov - Vinohrady • historické centrum mˇesta - Malá Strana ˇ • centrum menˇs´ı obce - Repy • pr˚ umyslov´ y are´ al - Bran´ık

Obr. 8.1: V´ yˇrezy vzorov´ ych u ´zem´ı (mˇeˇr´ıko je promˇenlivé v rozsahu 1:10 000 - 1:25 000)

75

S´ıdliˇ stˇ e. Tento typ z´ astavby m˚ uˇze b´ yt pomˇernˇe r˚ uznorod´ y, a proto je testován na tˇrech r˚ uzn´ ych lokalit´ ach. M˚ uˇze b´ yt typick´ y uniformn´ımi budovami s pravo´ uhl´ ym p˚ udorysem a podobnou orientac´ı budov v˚ uˇci ulici nebo se naopak m˚ uˇze vyznaˇcovat r˚ uznˇe tvarovan´ ymi a vzájemnˇe r˚ uznˇe natoˇcen´ ymi budovami. Spoleˇcn´ ym rysem vˇsak b´ yvá v´ yrazná protáhlost budov. ˇ Ctvrti rodinn´ ych dom˚ u a vil. Rodinné domy a vily jsou vesmˇes charakteristické jednoduch´ ym p˚ udorysem ve tvaru ˇctverce nebo obdéln´ıka, avˇsak ˇcasto se u nich vyskytuj´ı drobné v´ ystupky. Jako celek jsou typicky zarovnány podél komunikace, ˇc´ımˇz vytváˇr´ı r˚ uzné vzory ˇctverec, obdéln´ık, kruhovou v´ yseˇc apod. (viz. obr. 8.1). Jedná se o rozvolnˇenou zástavbu. Bloky (starˇ s´ıch) budov. Jsou typické vyˇsˇs´ımi, tˇesnˇe na sebe navazuj´ıc´ımi budovami kop´ıruj´ıc´ımi komunikaci, ˇc´ımˇz zpravidla vytváˇr´ı uzavˇren´ y blok budov s vnitˇrn´ım dvorem. V testovac´ıch datech byl tento typ zástavby vˇetˇsinou znázornˇen jako blok budov. Historick´ e centrum mˇ esta. Je typické hustou zástavbou, r˚ uznˇe tvarovan´ ymi budovami a uˇzˇs´ımi ulicemi. Ulice b´ yvaj´ı kˇrivolaké a zástavba je kop´ıruje. Historické budovy m´ıvaj´ı sloˇzitˇejˇs´ı p˚ udorys. Centrum menˇ s´ı obce. Je typické námˇest´ım (návs´ı) uprostˇred, od kterého se rozeb´ıhaj´ı ulice r˚ uzn´ ymi smˇery. Budovy b´ yvaj´ı jednoduˇsˇs´ıho p˚ udorysu (ˇcverec, obdéln´ık), ale vzájemnˇe r˚ uznˇe natoˇcené. Z´ astavba b´ yv´ a rozvolnˇenˇejˇs´ı, ale hustˇs´ı neˇz v pˇr´ıpadˇe ˇctvrt´ı rodinn´ ych dom˚ u. Pr˚ umyslov´ y are´ al. Podobnˇe jako s´ıdliˇstˇe m˚ uˇze nab´ yvat mnoha podob. Typick´ y je vˇsak budovami velkého a malého rozsahu v tˇesné bl´ızkosti, ˇcasto r˚ uznˇe vzájemnˇe natoˇcen´ ymi. Velké budovy mohou m´ıt bud’ jednoduch´ y p˚ udorys, nebo naopak p˚ udorys pomˇernˇe komplikovan´ y. Zástavba b´ yv´ a volnˇejˇs´ı.

8.3

Testov´ an´ı algoritmu na vzorov´ ych u ´ zem´ıch a porovn´ an´ı se SW ArcGIS

V této ˇc´ asti jsou posouzeny v´ ystupy algoritmu na menˇs´ıch shluc´ıch budov s c´ılem ohodnotit kartografickou vˇernost v´ ysledk˚ u. Pˇr´ılohy 2 - 8 ilustruj´ı generalizaci cel´ ych vzorov´ ych u ´zem´ı (pˇr´ıpadnˇe vˇetˇsiny jejich rozsahu, v závislosti na jejich velikosti). Tab. 8.1 a 8.2 pod´ avaj´ı pˇrehled o zmˇen´ ach ploch a poloze tˇeˇziˇstˇe agregovan´ ych budov. Porovnán´ı se SW ArcGIS je provedeno vizu´ alnˇe. Funkce ArcGIS pro agregaci je nazvána Area Aggregate, uved’me zde jej´ı princip. Area Aggregate. Algoritmus prob´ıhá v rastrovém prostˇred´ı. Nejprve je vstupn´ı vektorov´ a vrstva pˇrevedena na vrstvu rastrovou. Aplikac´ı funkc´ı Expand a Shrink (pravdˇepodobnˇe funkce dilatace a eroze, viz ˇc´ ast 3.3.2) docház´ı k agregaci budov ve specifikované vzdálenosti (uˇzivatelsk´ y vstup). V´ ysledek je pˇreveden zpˇet na rastr. Základn´ımi variantami algoritmu je bud’ moˇznost zachov´ an´ı pravo´ uhlosti (vhodné pro budovy) nebo nikoliv - viz obr. 8.2 (ESRI, 2000). 76

Obr. 8.2: Ilustrace v´ ysledk˚ u funkce Area Aggregate. Agregace neortogonáln´ıch prvk˚ u (vlevo), agregace ortogon´ aln´ıch prvk˚ u (vpravo). (pˇrevzato z: ESRI, 2000, s. 11) Pˇred vlastn´ım testov´ an´ım navrˇzeného algoritmu i algoritmu Area Aggregate byla nejprve v´ ybˇerem zjednoduˇsena vrstva os cestn´ı s´ıtˇe. Byly vytvoˇreny dvˇe nové vrstvy - jedna odpov´ıdaj´ıc´ı mˇeˇr´ıtku 1:25 000, druhá odpov´ıdaj´ıc´ı mˇeˇr´ıtku 1:50 000 (podkladem pro v´ ybˇer ˇ byly Topografické mapy CR odpov´ıdaj´ıc´ıch mˇeˇr´ıtek). Poté byly spuˇstˇeny vlastn´ı algoritmy pro agregaci. Urˇ cen´ı centroid˚ u budov. V tab. 8.1 a 8.2 jsou porovnány vzdálenosti centroid˚ u p˚ uvodn´ıch polygon˚ u a v´ ysledného agregovaného polygonu. Souˇradnice centroidu v´ ysledného polygonu jsou spoˇcteny dle vztah˚ u 6.1 a 6.2 (ˇcást 6.1). Centroid p˚ uvodn´ıho shluku budov je urˇcen jako váˇzen´ y pr˚ umˇer centroid˚ u d´ılˇc´ıch budov: Pn wi x i x ¯ = Pi=1 n i=1 wi kde wi je plocha d´ılˇc´ıho polygonu. Pˇred zhodnocen´ım v´ ysledk˚ u uved’me legendu platnou pro obrázky 8.3 - 8.9:

´ ´ Uzem´ ı 1 - Vokovice. Pohled na generalizaci u ´zem´ı jako celku pˇrináˇs´ı pˇr´ıloha 2. Uzem´ ı bylo zvoleno pˇredevˇs´ım pro testován´ı, zda je algoritmus schopen zachovat zarovnán´ı budov podél zakˇrivené komunikace. Z v´ ysledku je zˇrejmé, ˇze obecnˇe zarovnán´ı nezachov´ a. Pˇr´ıˇcinou je pˇredevˇs´ım generalizace redukovaného skeletonu agregovaného polygonu. Pˇri pohledu na v´ yslednou generalizaci jako celek je nutné konstatovat, ˇze pˇredevˇs´ım pro mˇeˇr´ıtko 1:50 000 je v´ ysledek z kartografického hlediska nepˇr´ızniv´ y.

77

Ze statistického hlediska (tab. 8.1 a 8.2) m˚ uˇzeme konstatovat, ˇze posun tˇeˇziˇstˇe je mal´ y a ve v´ ysledn´ ych mˇeˇr´ıtc´ıch zanedbateln´ y (< 2mm). Obr. 8.3 ilustruje agregaci konkrétn´ıch skupin budov. Algoritmus zachová pravé u ´hly, budovy tvarovˇe zjednoduˇsˇs´ı. Problematick´ a je agregace vˇetˇs´ıho poˇctu budov - zaˇc´ınaj´ı vznikat nepˇrirozené u ´tvary (viz i pˇr´ıloha 2). V pˇr´ıpadˇe obr. 8.3 m˚ uˇzeme sledovat i vˇetˇs´ı odchylku od p˚ uvodn´ıho um´ıstˇen´ı budov. D˚ uvody jsou dva: • generalizace kostry agregovaného polygonu, • volba ukonˇcovac´ı podm´ınky w: pˇri agregaci vzdálenˇejˇs´ıch budov malé plochy dává vztah 6.7 pˇr´ıliˇs malou hodnotu w.

Obr. 8.3: Ilustrace v´ ysledk˚ u pro u ´zem´ı 1: 1:25 000 (vlevo), 1:50 000 (vpravo) ´ Uzem´ ı 2 - Suchdol. Vzorové u ´zem´ı je podobné u ´zem´ı 1, ale vzdálenost mezi budovami v rámci blok˚ u jsou menˇs´ı. D˚ usledkem je ˇcastˇejˇs´ı (a z kartografického hlediska nepˇr´ızniv´ a) agregace budov napˇr´ıˇc bloky (viz pˇr´ıloha 3, obr. 8.4 vlevo). Jako celek p˚ usob´ı v´ ysledn´ a generalizace obdobnˇe jako v pˇr´ıpadˇe u ´zem´ı 1 - problematická je generalizace pˇredevˇs´ım vˇetˇs´ıho mnoˇzstv´ı budov. Alogritmus dok´ aˇze zachovat pravé u ´hly, ovˇsem stejnˇe jako v pˇr´ıpadˇe u ´zem´ı 1 doch´ az´ı k vˇetˇs´ım odchylk´ am v p˚ uvodn´ım um´ıstˇen´ı budov. ´ ´ Uzem´ ı 3 - Bran´ık. Uzem´ ı bylo zvoleno pˇredevˇs´ım pro testován´ı, jak se algoritmus vypoˇr´ ad´ a s agregac´ı bl´ızk´ ych budov r˚ uzné velikosti a tvaru. Vzhledem k tomu, ˇze pˇri zpˇetné rekonstrukci docház´ı k rozˇsiˇrov´ an´ı redukovaného skeletonu konstatn´ı rychlost´ı, nebude pravdˇepodobnˇe algoritmus schopen spr´ avnˇe vystihnout tvar agregovan´ ych budov. Bud’ budou p˚ uvodnˇe velké budovy pˇr´ıliˇs malé, nebo naopak p˚ uvodnˇe malé budovy pˇr´ıliˇs velké. Provedenou agregaci ilustruje obr. 8.5, kter´ y potvrzuje tyto domnˇenky. Je t´ım také negativnˇe ovlivnˇena schopnost algoritmu zachovat p˚ uvodn´ı polohu agregovan´ ych polygon˚ u.

78

Obr. 8.4: Ilustrace v´ ysledk˚ u pro u ´zem´ı 2: 1:25 000 (vlevo), 1:50 000 (vpravo)

Obr. 8.5: Ilustrace v´ ysledk˚ u pro u ´zem´ı 3: 1:25 000 ´ Uzem´ ı 4 a 5 - Nov´ e Butovice, Velk´ a Ohrada. V´ yslednou generalizaci u ´zem´ı 5 pˇrin´ aˇs´ı pˇr´ıloha 5. V pˇr´ıpadˇe obou u ´zem´ı docház´ı ke generalizaci pˇredevˇs´ım pravo´ uhl´ ych budov srovnatelné ˇs´ıˇrky. Jejich pravo´ uhlost i polohová pˇresnost jsou dobˇre zachovány (viz i obr. 8.6). V pˇr´ıpadˇe generalizace do mˇeˇr´ıka 1:50 000 vˇsak opˇet sledujeme v´ yˇse zm´ınˇené problémy nepˇrirozenou agregaci vˇetˇs´ıho mnoˇzstv´ı budov a budov v´ yraznˇe odliˇsného tvaru a velikosti v tˇesné bl´ızkosti.

Obr. 8.6: Ilustrace v´ ysledk˚ u pro u ´zem´ı 5: 1:50 000

79

Tab. 8.1: Statistické charakteristiky testován´ı v mˇeˇr´ıtku 1:25 000

Tab. 8.2: Statistické charakteristiky testován´ı v mˇeˇr´ıtku 1:50 000

´ Uzem´ ı 6 - Petˇ riny. Pˇr´ıloha 6 dokumentuje v´ yslednou generalizaci. Na u ´zem´ı je testov´ ano, jak algoritmus zpracuje budovy vzájemnˇe r˚ uznˇe natoˇcené, které maj´ı srovnatelnou ˇs´ıˇrku. Generalizaci ilustruje i obr. 8.7. V´ ysledky jsou v tomto pˇr´ıpadˇe pomˇernˇe uspokojivé. Agregované polygony zachov´ av´ aj´ı polohu p˚ uvodn´ıch budov a budovy jsou dobˇre zjednoduˇsené. ´ ´ ˇ Uzem´ ı 7 - Repy. Uzem´ ı bylo zvoleno pro posouzen´ı agregace bl´ızk´ ych budov r˚ uzné velikosti, které jsou vz´ ajemnˇe r˚ uznˇe natoˇcené. Vzhledem k bl´ızkosti jednotliv´ ych budov se jich agreguje pomˇernˇe velké mnoˇzstv´ı (obr. 8.8, pˇr´ıloha 7). Aˇckoliv posun tˇeˇziˇstˇe v´ ysledn´ ych a p˚ uvodn´ıch budov nen´ı pˇr´ıliˇs velk´ y, z kartografického hlediska jsou v´ ysledky krajnˇe nepˇr´ıznivé.

80

Obr. 8.7: Ilustrace v´ ysledk˚ u pro u ´zem´ı 6: 1:25 000 (vlevo), 1:50 000 (vpravo)

Obr. 8.8: Ilustrace v´ ysledk˚ u pro u ´zem´ı 7: 1:50 000 ´ ´ Uzem´ ı 8 - Mal´ a Strana. Uzem´ ı obsahuje velké mnoˇzstv´ı r˚ uznorod´ ych budov. Budovy jsou vzájemnˇe r˚ uznˇe natoˇcené, v tˇesné bl´ızkosti se nacházej´ı budovy r˚ uzn´ ych tvar˚ u. V´ ysledek generalizace dokumentuje pˇr´ıloha 8. Jako celek p˚ usob´ı v´ ysledek relativnˇe dobˇre v porovn´ an´ı s v´ ysledkem generalizace v SW ArcGIS. Pˇri bliˇzˇs´ım zkoumán´ı jednotliv´ ych agregovan´ ych budov vˇsak opˇet objevujeme dˇr´ıve uvedené skuteˇcnosti (obr. 8.9 vlevo): problematická agregace budov r˚ uzné ˇs´ıˇrky, problematick´ a agregace velkého mnoˇzstv´ı budov, ale i pomˇernˇe zdaˇril´ a agregace budov podobné ˇs´ıˇrky. ´ Uzem´ ı 9 - Vinohrady. Z´ astavba u ´zem´ı je ve vzorov´ ych datech znázornˇena jako bloky budov. Je tedy testov´ ana schopnost algoritmu agregovat bloky budov. Mus´ıme konstatovat, ˇze v´ ysledky jsou velmi nevhodné, at’ uˇz se jedná o hledisko kartografické (obr. 8.9 vpravo) nebo statistické (velk´ y posun centroid˚ u). Nav´ıc docház´ı k pˇrekryv˚ um soused´ıc´ıch agregovan´ ych polygon˚ u. Problém pˇrekryv˚ u algoritmus v˚ ubec neˇreˇs´ı, k pˇrekryv˚ um proto m˚ uˇze doj´ıt i v jin´ ych pˇr´ıpadech (i kdyˇz nebyly pˇri testován´ı zaznamenány).

81

Obr. 8.9: Ilustrace v´ ysledk˚ u pro u ´zem´ı 8: 1:50 000 (vlevo), ilustrace v´ ysledk˚ u pro u ´zem´ı 9: 1:50 000 (vpravo) Porovn´ an´ı se SW ArcGIS. Ukázky agregace vzorov´ ych u ´zem´ı funkc´ı Area Aggregate ilustruje obr. 8.10. Algoritmus agreguje budovy vyplnˇen´ım prázdného prostoru mezi nimi. Dobˇre zachov´ av´ a pravé u ´hly. Z hlediska kartografické pˇrirozenosti poskytuje obecnˇe lepˇs´ı v´ ysledky neˇz navrˇzen´ y algoritmus - pˇredevˇs´ım skuteˇcnˇe dokáˇze dobˇre zpracovat ˇsiroké spektrum budov i v souvislosti s okoln´ımi budovami. Oproti navrˇzenému algoritmu provád´ı agregaci bez ohledu na omezen´ı liniov´ ymi prvky. Agregované budovy nejsou tvarovˇe zjednoduˇseny. Jako celek lze v´ ysledky dosahované navrˇzen´ ym algoritmu porovnat s algoritmem Area Aggregate na z´ akladˇe pˇr´ıloh 2-8. Agregace v SW ArcGIS p˚ usob´ı ve vˇetˇsinˇe pˇr´ıpad˚ u pˇrirozenˇeji - na rozd´ıl od navrˇzeného algoritmu totiˇz dokáˇze budovy agregovat tak, ˇze vytvoˇr´ı vizu´ alnˇe pˇekné bloky budov (viz. napˇr. obr. 8.10 dole). Navrˇzen´ y algoritmus se v tˇechto pˇr´ıpadech pot´ yká s t´ım, ˇze vytv´ aˇr´ı nepˇrirozené polygony (napˇr. obr. 8.8), coˇz má dle mého n´ azoru nejvˇetˇs´ı dopad na negativn´ı p˚ usoben´ı v´ ysledné agregace na vzorov´ ych u ´zem´ıch. M˚ uˇzeme vˇsak objevit i nˇekteré nedostatky algoritmu Area Aggregate. Protoˇze algoritmus v˚ ubec nezjednoduˇsuje tvar agregovan´ ych budov, lze pozorovat napˇr. vznik velmi u ´zk´ ych propojen´ı mezi dvˇema agregovan´ ymi budovami nebo budovy s velk´ ym mnoˇzstv´ım mal´ ych v´ ystupk˚ u. Aˇc ani Area Aggregate algoritmus nen´ı dokonal´ y, mus´ıme na závˇer zkonstatovat, ˇze v souˇcasné chv´ıli pod´ av´ a lepˇs´ı v´ ysledky neˇz navrˇzen´ y algoritmus.

82

Obr. 8.10: Generalizace vybran´ ych budov generalizaˇcn´ım algoritmem Area Aggregate

8.4

Zhodnocen´ı navrˇ zen´ eho algoritmu a jeho implementace

V této podkapitole bude diskutována kvalita dosaˇzen´ ych v´ ysledk˚ u a efektivita implementace algoritmu. N´ avrh algoritmu byl podrobnˇe popsán v 6. kapitole. Byly v n´ı naznaˇceny nˇekteré potenci´ aln´ı problémy algoritmu. Shrˇ nme nyn´ı ve tˇrech bodech skuteˇcnosti, které algoritmus v souˇcasné podobˇe omezuj´ı: 1. kvalita generalizace redukovaného straight skeletonu agregovaného polygonu, 2. zpˇetné rozˇsiˇrov´ an´ı polygonu prob´ıhaj´ıc´ı konstantn´ı rychlost´ı pro vˇsechny vrcholy, 3. volba ukonˇcovac´ı podm´ınky w. Zhodnocen´ı dosaˇ zen´ ych v´ ysledk˚ u. Dosaˇzené v´ ysledky jsou ovlivnˇeny v´ yˇse uveden´ ymi skuteˇcnostmi. Zhodnot’me nejprve u ´spˇeˇsnost agregace z pohledu agregace nˇekolika budov mimo geografick´ y kontext. Algoritmus d´ av´ a dobré v´ ysledky pˇri agregaci menˇs´ıho mnoˇzstv´ı jednoduch´ ych pravo´ uhl´ ych budov i budov obecnˇejˇs´ıch tvar˚ u (viz napˇr. obr. 8.3 vlevo, obr. 8.6, obr. 8.7). 83

V pˇr´ıpadˇe agregace v´ıce menˇs´ıch budov, zarovnan´ ych v ˇradˇe a s vˇetˇs´ımi rozestupy (napˇr. obr. 8.3 vpravo), vnikaj´ı pˇr´ıliˇs u ´zké polygony. Pˇr´ıˇcinou je volba ukonˇcovac´ı podm´ınky w (vztah 6.7). Pro tyto pˇr´ıpady, kdy: • poˇcet agregovan´ ych budov je relativnˇe velk´ y (> 5), • pomˇer plochy agregovan´ ych budov a délky kostry v´ ysledného polygonu je pˇr´ıliˇs mal´ y (napˇr. na hranˇe grafick´ ych limit˚ u), ´ by bylo vhodné upravit podm´ınku w. Uprava by mohla spoˇc´ıvat ve zmˇenˇe koeficientu vztahu 6.7, napˇr. Pn Si 1 · w = Pi=0 m j=0 lj 4 nov´ y koeficient by bylo nutné d´ at do souvislosti s konkrétn´ım pˇr´ıpadem, coˇz by vyˇzadovalo dalˇs´ı testov´ an´ı tˇechto pˇr´ıpad˚ u. Tˇret´ım diskutovan´ ym pˇr´ıpadem je problém agregace dvou budov rozd´ılné ˇs´ıˇrky (napˇr. obr. 8.5). Tento problém je z logiky návrhu algoritmu vpodstatˇe neˇreˇsiteln´ y, jedná se o d˚ usledek v´ yˇse zm´ınˇen´ ych omezen´ı (bod 2). Potenciáln´ım moˇzn´ ym ˇreˇsen´ım by mohlo b´ yt udrˇzen´ı informace o (napˇr. pr˚ umˇerné) vzd´ alenosti vrchol˚ u kaˇzdého polygonu od jeho redukovaného straight skeletonu (oznaˇcme tento atribut jako vzd´ al ). Atribut vzd´ al by byl vyuˇzit pˇri tvorbˇe prvn´ı aproximace agregovaného polygonu. Délka posunut´ı jednotliv´ ych vrchol˚ u kostry by byla pˇr´ımo u ´mˇern´ a atributu vzd´ al kaˇzdého z vrchol˚ u. Vlastn´ı rekonstrukce polygonu by jiˇz prob´ıhala konstantn´ı rychlost´ı. Zda by tento pˇr´ıstup pˇrináˇsel lepˇs´ı v´ ysledky by opˇet vyˇzadovalo dalˇs´ı testován´ı. Zmiˇ nme jeˇstˇe pˇr´ıpad agregace dvou blok˚ u budov (obr. 8.9 vpravo). Pˇr´ıˇcinu chován´ı algoritmu se v tomto pˇr´ıpadˇe nepodaˇrilo z teoretického hlediska objasnit. Pˇr´ıˇcinou m˚ uˇze b´ yt chyba v implementaci (pravdˇepodobné slabé stránky implementace budou jeˇstˇe diskutov´ any), pro tento pˇr´ıpad se vˇsak nepodaˇrila objasnit. Na z´ avˇer zhodnot’me celkové p˚ usoben´ı provedené generalizace na vzorov´ ych u ´zem´ıch (pˇr´ılohy 2-8). Bohuˇzel je nutno konstatovat, ˇze z kartografického pohledu generalizace jako celek pˇr´ıliˇs dobˇre nep˚ usob´ı. D˚ uvody jsou pˇredevˇs´ım následuj´ıc´ı: • v´ yskyt u ´zk´ ych polygon˚ u, tento problém by mohl b´ yt odstranˇen metodou uvedenou v´ yˇse, • v nˇekter´ ych m´ıstech nezachován´ı linie podél komunikace (problematika generalizace, viz ˇc´ ast 6.2.1), • vznik nepˇrirozen´ ych tvar˚ u pˇri agregaci velkého mnoˇzstv´ı budov (napˇr. obr. 8.8).

84

Pokud by se podaˇrilo odstranit jednotlivé d´ılˇc´ı problémy agregace, pravdˇepodobnˇe by v´ ysledky byly v´ yraznˇe kartograficky pˇr´ıznivˇejˇs´ı. Vyˇzadovalo by to vˇsak jeˇstˇe nemal´ y objem práce. M˚ uˇzeme konstatovat, ˇze algoritmus je schopn´ y zpracovat budovy sloˇzitˇejˇs´ıch tvar˚ u (kromˇe budov s d´ırami, viz d´ ale), ovˇsem dosaˇzené v´ ysledky jsou ovlivnˇeny pˇredevˇs´ım polohou, tvarem a orientac´ı soused´ıc´ıch budov, které se liˇs´ı pro kaˇzd´ y konkrétn´ı pˇr´ıpad. Omezen´ı algoritmu. Mimo v´ yˇse uvedené skuteˇcnosti algoritmus nedokáˇze zpracovat budovy s d´ırami (tj. napˇr´ıklad budovy s vnitˇrn´ım dvorem). D˚ uvodem je pˇredevˇs´ım sloˇzitost zpracov´ an´ı. Polygon˚ um s d´ırami by bylo nutné vˇenovat velkou pozornost nejen pˇri tvrobˇe prvn´ı aproximace polygonu, ale pˇredevˇs´ım pˇri zpˇetné rekonstrukci polygonu. Oba problémy jsou znaˇcnˇe sloˇzité a dos´ ahnout u ´spˇeˇsné implementace by bylo velmi nároˇcné (alespoˇ n pro studenta neiformatického oboru). Zhodnocen´ı implementace algoritmu. Algoritmus se podaˇrilo v´ıceménˇe u ´spˇeˇsnˇe implementovat v jazyce C++ a vytvoˇrit konzolovou aplikaci pro Windows. Zat´ım byla objevena jedna slabé str´ anka implementace, a to pravdˇepodobnˇe v m´ıstˇe konstrukce prvn´ı aproximace polygonu nebo v m´ıstˇe generalizace kostry. U nˇekter´ ych v´ ysledn´ ych polygon˚ u (napˇr. pˇr´ıloha 2, viz obr. 8.11) m˚ uˇzeme sledovat ul´ıtl´ y“ vrchol, tedy vrchol, kter´ y pˇri konstantn´ım ” rozˇsiˇrov´ an´ım prvn´ı aproximace polygonu nikdy nem˚ uˇze vzniknout. Pˇresné m´ısto chyby se ale zat´ım nepodaˇrilo objevit. Z hlediska ˇcasové sloˇzitosti je nejnároˇcnˇejˇs´ı testován´ı pr˚ useˇc´ık˚ u s omezen´ımi (alg. 6.1), v´ ypoˇcet vzd´ alenosti dvou polygon˚ u (ˇcást 4.2) a konstrukce straight skeletonu (ˇcást 4.3). Délka bˇehu algoritmu je z´ avisl´ a pˇredevˇs´ım na poˇctu budov, které jsou urˇcené pro agregaci. Pˇri poˇctu budov urˇcen´ ych pro agregaci do 1000 prob´ıhal algoritmus do 20 sekund, pˇri 1200 agregovan´ ych budov´ ach 25 sekund, pˇri 2500 budovách 51 sekund. Pˇri testován´ı vˇetˇs´ıho mnoˇzstv´ı budov bohuˇzel doˇslo k p´ adu aplikace (v pr˚ ubˇehu zpracován´ı). Pˇri zpracován´ı cca 28 000 vstupn´ıch budov by odhadem algoritmus prob´ıhal déle neˇz 10 minut a pˇri dalˇs´ım navyˇsov´ an´ı poˇctu budov by pravdˇepodobnˇe doba zpracován´ı nar˚ ustala strmˇeji.

Obr. 8.11: Chyba implementace

85

Zhodnocen´ı vhodnosti pouˇ zit´ ych metod. Vyuˇzit´ı straight skeletonu a grafov´ ych algoritm˚ u pro agregaci budov dosud nebylo v literatuˇre publikováno (nebo se v záplavˇe odborn´ ych ˇclánk˚ u nepodaˇrilo objevit). Jedná se tedy ve své podstatˇe o pr˚ ukopnickou práci v oblasti agregaˇcn´ıch algoritm˚ u. Samotnou myˇslenku tvorby topologické kostry, jej´ıho pˇreveden´ı na redukovan´ y straight skeleton a n´ aslednou agregaci koster aplikac´ı algoritmu pro nalezen´ı minimáln´ı kostry grafu povaˇzuji za u ´spˇeˇsnou. Jej´ı realizace je vˇsak dosti sloˇzitá. Nav´ıc pouhou aplikac´ı tohoto postupu nem˚ uˇzeme dosáhnout optimáln´ıch v´ ysledk˚ u pro vˇsechny (nebo alespoˇ n vˇetˇsinu) vstupn´ı konfigurace budov. Jako nejvˇetˇs´ı problém (nav´ıc tˇeˇzko ˇreˇsiteln´ y) bych uvedla jiˇz diskutovanou neschopnost algoritmu agregovat vˇetˇs´ı mnoˇzstv´ı budov do kartograficky dobˇre vypadaj´ıc´ıch blok˚ u budov. Nicménˇe jeˇstˇe jednou zd˚ uraznˇeme, ˇze se jedná o zcela nov´ y pˇr´ıstup k agregaci budov a bylo by naivn´ı se domn´ıvat, ˇze hned prvn´ım pokusem dosáhneme optimáln´ıch v´ ysledk˚ u pro kaˇzdou situaci. Navrˇzen´ y algoritmus skr´ yvá potenciál, bylo by vˇsak nutno jej jeˇstˇe pˇrepracovat a doplnit. Jako negativn´ı faktor se nav´ıc jev´ı pomˇernˇe velká ˇcasová sloˇzitost algoritmu. Z´ avˇ ereˇ cn´ e shrnut´ı v´ ysledk˚ u. Algoritmus prokázal dobrou schopnost agregovat menˇs´ı mnoˇzstv´ı budov pˇri souˇcasném zjednoduˇsen´ı agregovan´ ych polygon˚ u. Dosaˇzené v´ ysledky jsou kartograficky pˇrirozené, zachov´ avaj´ı pravé u ´hly i polohovou pˇresnost p˚ uvodn´ıch budov. Slabˇs´ımi str´ ankami algoritmu je vznik pˇr´ıliˇs u ´zk´ ych polygon˚ u v pˇr´ıpadˇe agregace vˇetˇs´ıho mnoˇzstv´ı budov, tento problém by mˇel b´ yt odstraniteln´ y zmˇenou podm´ınky w. Dále je problematick´ a generalizace kostry agregovaného polygonu, coˇz se projevuje napˇr. v nedodrˇzen´ı linie komunikace. Tento bod patˇr´ı zajisté k jednˇem z moˇznost´ı dalˇs´ıho rozpracován´ı pr´ ace. Tˇret´ım problémem je vznik nepˇrirozen´ ych, dlouh´ ych polygon˚ u v pˇr´ıpadˇe agregace velkého mnoˇzstv´ı budov, kdy by z kartografického hlediska mˇel agregovan´ y polygon tvoˇrit uzavˇren´ y blok budov. Do budoucna by bylo moˇzné práci jeˇstˇe rozˇs´ıˇrit o zpracován´ı budov s d´ırami, coˇz, jak bylo uvedeno v´ yˇse, je pomˇernˇe sloˇzit´ y problém.

86

9

´ ER ˇ ZAV

Pˇredloˇzen´ a diplomov´ a pr´ ace se zab´ yvá tématem automatizované kartografické generalizace. Jej´ım hlavn´ım c´ılem bylo navrhnout nov´ y generalizaˇcn´ı algoritmus pro agregaci budov. V prvn´ı, teoretické ˇc´ asti diplomové práce, byl podán pˇrehled dosud publikovan´ ych algoritm˚ u pouˇz´ıvan´ ych pro agregaci budov. Byly zm´ınˇeny algoritmy pracuj´ıc´ı ve vektorovém i rastrovém prostˇred´ı. Dalˇs´ı kapitoly se jiˇz vˇenovaly návrhu nového algoritmu. Z formáln´ıho hlediska byly pops´ any pouˇzité pomocné datové struktury a algoritmy, byly stanoveny kartografické a geometrické podm´ınky pro agregaci. Vlastn´ı algoritmus je zaloˇzen pˇredevˇs´ım na myˇslence redukce polygon˚ u na topologickou kostru metodou straight skeletonu, ze které je z´ısk´ an redukovan´ y straight skeleton. Agregac´ı redukovan´ ych straight skeleton˚ u je vpodstatˇe provedena i vlastn´ı agregace budov. V´ ysledn´ y polygon je zrekonstruován postupn´ ym rozˇsiˇrov´ an´ım topologické kostry pohybem po bisektorech smˇerem ven. V´ ystupem praktické ˇc´ asti diplomové práce je konzolová aplikace implementovaná v jazyce C++. Aplikace byla otestov´ ana na datov´ ych sadách ZABAGED a CEDA. Pro u ´ˇcely testov´ an´ı bylo vybr´ ano nˇekolik vzorov´ ych u ´zem´ı, na kter´ ych byl algoritmus spuˇstˇen ve dvou variant´ ach vstupn´ıch parametr˚ u. Dosaˇzené v´ ysledky byly zhodnoceny a struˇcnˇe porovnány s v´ ysledky dosahovan´ ymi n´ astrojem implementovan´ ym v SW ArcGIS. V u ´plném z´ avˇeru pr´ ace byly diskutovány problémy navrˇzeného algoritmu a naznaˇcena moˇzná ˇreˇsen´ı tˇechto problém˚ u. Byla také zhodnocena u ´spˇeˇsnost implementace algoritmu.

87

ˇ YCH ´ ˚ SEZNAM POUZIT ZDROJU AGENT, DA2: Constraint Analysis [on-line]. [cit. 5. 3. 2012] Agent Consortium, 8. 2. 2001. Dostupné na WWW: AGENT, DD2: Selection of Basic Algorithms [on-line]. [cit. 14. 9. 2011] Agent Consortium, 8. 2. 2001. Dostupné na WWW: AGENT, DD3: Strategic Algorithms Using Organisations [on-line]. [cit. 5. 3. 2012] Agent Consortium, 8. 2. 2001. Dostupné na WWW: AICHHOLZER, O. et al.: A novel type of skeleton for polygons. The Journal of Universal Computer Science, 1995. pp. 752-761. AICHHOLZER, O., AURENHAMMER, F: Straight Skeletons for General Polygonal Figures in the Plane. Proceedings of the Second Annual International Conference on Computing and Combinatorics, June 17-19, 1996. pp. 117-126. BASARANER, M., SELCUK, M.: An Attempt to Automated Generalization of Buildings and Settlement Areas in Topographic Maps. ISPRS, 2004, pp. 188-193. BAYER, T.: Algoritmy v digit´ aln´ı kartografii. 1. vyd. Karolinum, Praha, 2008. BAYER, T.: Automated building simplification using a recursive approach. In: ICA Symposium on Cartography for Central and Eastern Europe, LNG&C, pp. 121-145, Vienna, Springer, 2009. BERG, M. de et al.: Computational Geometry: Algorithms and Applications. 3. vyd. Springer, Berlin, 2008. 386 s. CACCIOLA, F.: A CGAL implementation of the Straight Skeleton of a Simple 2D Polygon with Holes [on-line]. [cit. 10. 4. 2012]. Dostupné na WWW:

88

CGAL: Computational Geometry Algorithms Library [on-line]. [cit. 10. 4. 2012]. Dostupné na WWW: Cplusplus.com [on-line]. [cit. 23. 5. 2012]. Dostupné na WWW: DEMEL, J.: Grafy a jejich aplikace. 1. vyd. Academia, Praha, 2002. ISBN 80-200-0990-6. DUCHENE, C.: The CartACom model: a generalisation model for taking relational constraints into account. In: ICA Workshop on Generalisation and Multiple representations, Leicester, 2004. DUCHENE, C., GAFFURI, J.: Combining three multi-agent based generalisation models: AGENT, CartACom and GAEL. In: 13th International Symposium on Spatial Data Handling, Montpellier, France, 2008. ˇ ECER, P.: Vyuˇzit´ı Straight skeletonu pro rekonstrukci tvaru stˇrechy z dat laserového skenov´ an´ı. Diplomov´ a pr´ ace, katedra aplikované geoinformatiky a kartografie PˇrF UK, 2010. Vedouc´ı pr´ ace: Ing. Tom´ aˇs Bayer, Ph.D. EPPSTEIN, D., ERICKSON, J.: Raising Roofs, Crashing Cycles, and Playing Pool: Applications of a Data Structure for Finding Pairwise Interactions. Discrete & Computational Geometry 22, pp. 569-592 [on-line]. [cit. 10. 4. 2012]. Dostupné na WWW: ESRI: Map Generalization in GIS: Practical Solutions with Workstation ArcInfo Software. An ESRI Technical Paper, 2000 [on-line]. [cit. 1.9.2011]. Dostupné na WWW: ESRI: ArcGIS Desktop 9.3 Help [on-line]. [cit. 1.9.2011]. Dostupné na WWW: ESRI: ArcGIS Resource Center [on-line]. [cit. 1.9.2011]. Dostupné na WWW: ˇ ALEK, ´ ˇ Straight Skeleton Implementation. 14th Spring Conference FELKEL, P., OBDRZ S.: on Computer Graphics, Budmerice, Slovakia, 1998, pp. 210-218. HAUNERT, J-H.: Aggregationin Map Generalization by Combinatorial Optimization. Disertaˇcn´ı pr´ ace, Leibniz Universität Hannover, 2008. In:Reihe C, Heft 626 der Veröffentlichungen der Deutsche Geod¨ atische Kommission. 89

HAUNERT, J-H., SESTER, M.: Using the Straight Skeleton for Generalisation in a Multiple Representation Environment [on-line]. [cit. 16.4.2012]. In: ICA Workshop on Generalisation and Multiple representations, Leicester, 2004. Dostupné na WWW: HAUNERT, J.-H., SESTER, M.: Area Collapse and Road Centerlines based on Straight Skeletons. Geoinformatica, 2008, Vol. 12, No. 2, pp. 169-191. ´ L.: Teorie graf˚ JÍROVSKY, u [on-line]. [cit. 13.4.2012]. Diplomová práce, MFF UK, 2010. Dostupné na WWW: ´ R, ˇ J.: Teoretick´ ˇ a informatická spoleˇcnost, Praha, 2004. KOLA a informatika. 2. vyd. Cesk´ LAMY S. et al.: AGENT Project: Automated Generalisation New Technology. [on-line]. [cit. 14. 9. 2011]. Dostupné na WWW: LI, Z.: Algorithmic Foundation of Multi-Scale Spatial Representation. CRC Press, 2007. 282 s. LI, Z. et al.: Automated Building Generalization Based on Urban Morphology and Gestalt Theory. International Journal of Geographical Information Science, 2004, Vol. 18, No. 5, pp. 513-534. MACKANESS, W., RUAS, A., SARJAKOSKI, L. T. (eds.): Generalisation of Geograhic Information: Cartograhic Modelling and Applications. International Cartographic Association, 2007. 282 s. OKABE, A. et al: Spatial Tessellations: Concepts and Applications of Voronoi Diagrams. 2. vyd. Wiley Series in Probability and Statistics, 2000. 671 s. ´ J.: Automatizovan´ POPELÍNSKY, a kartografick´ a generalizace ˇr´ıˇcn´ıch s´ıt´ı. Diplomová pr´ ace, Geografick´ yu ´stav PˇrF MU Brno, 2011. Vedouc´ı práce: Mgr. Karel Stanˇek, Ph.D. SESTER, M.: Generalization Based on Least Squares Adjustment. Internationl Archives of Photogrammetry and Remote Sensing. Vol. 33, Part B4, Amsterdam, 2000, pp. 931-938. Shapefile C Library [on-line]. [cit. 23. 5. 2012]. Dostupné na WWW: SHEA, K. S., McMASTER, R. B.: Cartographic Generalization in a Digital Environment: When and How to Generalize. AUTO-CARTO 9, Ninth International Symposium on ComputerAssisted Cartography, Baltimore,Maryland, April 2-7 1989, pp. 56-67. 90

STEINIGER, S., TAILLANDIER, P.: Improving Map Generalisation of Buildings by Introduction of Urban Context Rules. [on-line]. [cit. 7. 3. 2012]. Dostupné na WWW: SU, B. et al..: Algebraic models for the aggregation of areafeatures based upon morphological operators. International Journal of Geographical Information Science, 1997, Vol. 11, No. 3, pp 233 - 246. ˇÍP, M.: Topologick´ S a kostra polygonu a jej´ı vyuˇzit´ı pˇri kartografické generalizaci. Diplomov´ a práce,katedra aplikované geoinformatiky a kartografie PˇrF UK, 2007. Vedouc´ı pr´ ace: Ing. Tom´ aˇs Bayer, Ph.D. ˇ STAMPACH, R.: Automatick´ a kartografick´ a generalizace stavebn´ıch objekt˚ u z KM do map stˇredn´ıch mˇeˇr´ıtek. Diplomov´ a pr´ ace, Geografick´ yu ´stav PˇrF MU Brno, 2006. Vedouc´ı pr´ ace: Mgr. Karel Stanˇek, Ph.D. The Boost Grahp Library (BGL) [on-line]. [cit. 23. 5. 2012]. Boost C++ Libraries, 2000-2001. Dostupné na WWW: QI, H., LI, Z.: An Approach to Building Grouping Based on Hierarchical Constraints. The Internationl Archives of the Photogrammetry, Remote Sensing and Spatial Information Sciences. Vol. 37, Part B2. Peking, 2008.

91

ˇ ÍLOH SEZNAM PR Pˇr´ıloha Pˇr´ıloha Pˇr´ıloha Pˇr´ıloha Pˇr´ıloha Pˇr´ıloha Pˇr´ıloha Pˇr´ıloha

1 2 3 4 5 6 7 8

DVD s elektronickou verz´ı práce Generalizace u ´zem´ı 1 - Vokovice Generalizace u ´zem´ı 2 - Suchdol Generalizace u ´zem´ı 3 - Bran´ık Generalizace u ´zem´ı 5 - Velká Ohrada Generalizace u ´zem´ı 6 - Petˇriny ˇ Generalizace u ´zem´ı 7 - Repy Generalizace u ´zem´ı 8 - Malá Strana

92

UNIVERZITA KARLOVA V PRAZE

Recommend Documents