DIPLOMOVA PR ACE -...

CESKE VYSOKE UCENI TECHNICKE V PRAZEFAKULTA STAVEBNI

DIPLOMOVA PRACE

PRAHA 2014 Bc. et Bc. Katerina HYNKOVA

CESKE VYSOKE UCENI TECHNICKE V PRAZEFAKULTA STAVEBNI

STUDIJNI OBOR GEODEZIE A KARTOGRAFIE

STUDIJNI PROGRAM GEOINFORMATIKA

DIPLOMOVA PRACEGENERALIZACE VODSTVA TECHNIKOU

REDUKCE PROSTOROVE DIMENZE

Vedoucı prace: prof. Dr. Ing. Karel PavelkaKatedra geomatiky

cerven 2014 Bc. et Bc. Katerina HYNKOVA

ZDE VLOZIT LIST ZADANI

Z duvodu spravneho cıslovanı stranek

ABSTRAKT

Diplomova prace se v uvodu zabyva skeletonem jako kartografickym operatorem

pouzıvanym pri automatizovane generalizaci. Hlavnı cast prace je venovana navrhu nove

geometricke struktury modifikovany straight skeleton, ktera vychazı ze straight skele-

tonu, ale oproti nemu ma tu vyhodu, ze eliminuje prılisny vliv nekonvexnıch vrcholu

polygonu na vysledny tvar jeho skeletonu. Tato struktura je vyuzita v implementaci

algoritmu pro generalizaci vodnıch toku technikou redukce prostorove dimenze, ktery

extrahuje z modifikovaneho straight skeletonu nerozvetvenou linii metodou orezavanı

binarnıho stromu.

KLICOVA SLOVA

Straight skeleton, modifikovany straight skeleton, generalizace vodnıch toku, redukce

prostorove dimenze

ABSTRACT

At the beginning this master’s thesis discusses a skeleton as an operator which is used for

automatic generalization in cartography. A focus of the work is to design a new geometry

structure modified straight skeleton that is based on straight skeleton, however compared

to straight skeleton its advantage is that it eliminates excessive influence of reflex vertices

of a polygon to a shape of its skeleton. This structure is used in implementation of

algorithm for generalization of water bodies using a spatial dimension reduction method.

The algorithm derives a simple line from a modified straight skeleton using pruning of a

binary tree.

KEYWORDS

Straight skeleton, modified straight skeleton, generalization of water bodies, collapse

PROHLASENI

Prohlasuji, ze diplomovou praci na tema”Generalizace vodstva technikou redukce

prostorove dimenze“ jsem vypracovala samostatne. Pouzitou literaturu a podkladove

materialy uvadım v seznamu zdroju.

V Praze dne . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

(podpis autora)

PODEKOVANI

Chtela bych podekvat vedoucımu prace prof. Dr. Ing. Karlu Pavelkovi za pochopenı

a trpelivost a Ing. Tomasi Bayerovi za velmi prınosne konzultace.

Obsah

Uvod 11

1 Kartograficka generalizace 12

1.1 Generalizace vodstva . . . . . . . . . . . . . . . . . . . . . . . . . . . 13

1.1.1 Generalizace vodnıch toku . . . . . . . . . . . . . . . . . . . . 14

2 Digitalnı generalizace 16

2.1 Filosoficka vychodiska digitalnı generalizace . . . . . . . . . . . . . . 16

2.1.1 Teoreticke faktory . . . . . . . . . . . . . . . . . . . . . . . . . 16

2.1.2 Faktory urcene funkcı mapy . . . . . . . . . . . . . . . . . . . 18

2.1.3 Vypocetnı faktory . . . . . . . . . . . . . . . . . . . . . . . . . 18

2.2 Kartometricke vyhodnocenı . . . . . . . . . . . . . . . . . . . . . . . 18

2.2.1 Geometricke situace . . . . . . . . . . . . . . . . . . . . . . . 18

2.2.2 Prostorove a holisticke charakteristiky . . . . . . . . . . . . . 19

2.2.3 Faktory rıdıcı transformaci . . . . . . . . . . . . . . . . . . . . 20

2.3 Prostorove a atributove transformace . . . . . . . . . . . . . . . . . . 20

2.3.1 Prostorove transformace . . . . . . . . . . . . . . . . . . . . . 20

2.3.2 Atributove transformace . . . . . . . . . . . . . . . . . . . . . 21

3 Skeletonizace 22

3.1 Skeleton jako kartograficky operator . . . . . . . . . . . . . . . . . . . 22

3.1.1 Medial axis . . . . . . . . . . . . . . . . . . . . . . . . . . . . 23

3.1.2 Chordal axis . . . . . . . . . . . . . . . . . . . . . . . . . . . . 25

3.1.3 Straight skeleton . . . . . . . . . . . . . . . . . . . . . . . . . 26

3.1.4 Linear axis . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 28

4 Modifikovany straight skeleton 29

4.1 Implementace straight skeletonu podle Felkel & Obdrzalek . . . . . . 30

4.1.1 Vypocet straight skeletonu konvexnıho polygonu . . . . . . . . 33

4.1.2 Vypocet straight skeletonu nekonvexnıho polygonu . . . . . . 34

4.1.3 Datove struktury pouzite v implementaci algoritmu . . . . . . 39

4.2 Modifikace algoritmu pro vypocet straight skeletonu . . . . . . . . . . 43

5 Extrakce linie ze skeletonu 48

5.1 Prohledavanı do sırky . . . . . . . . . . . . . . . . . . . . . . . . . . . 49

5.2 Reprezentace skeletonu jako binarnıho stromu . . . . . . . . . . . . . 59

5.3 Orezavanı zjednoduseneho binarnıho stromu . . . . . . . . . . . . . . 66

5.4 Prevod extrahovane linie na seznam bodu . . . . . . . . . . . . . . . 82

6 Program Collapse Polygons to Lines 90

6.1 Predzpracovanı vstupnıch dat . . . . . . . . . . . . . . . . . . . . . . 90

6.2 Vstupnı data . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 90

6.2.1 Nastroj pro prıpravu vstupnıch dat . . . . . . . . . . . . . . . 91

6.3 Prace s programem Collapse Polygons to Lines . . . . . . . . . . . . . 94

6.3.1 Implementace funkce pro nacıtanı polygonu . . . . . . . . . . 96

6.3.2 Implementace funkce pro zapis vystupnıch dat . . . . . . . . . 97

6.3.3 Nastroj pro import vystupu z programu do ArcGIS . . . . . . 98

6.4 Nastroj pro castecnou redukci prostorove dimenze . . . . . . . . . . . 101

6.5 Zhodnocenı vysledku programu . . . . . . . . . . . . . . . . . . . . . 104

Zaver 107

Pouzite zdroje 108

Seznam prıloh 111

A Elektronicke prılohy 112

CVUT v Praze SEZNAM OBRAZKU

Seznam obrazku

3.1 Prıklad medial axis . . . . . . . . . . . . . . . . . . . . . . . . . . . . 23

3.2 Ukazka citlivosti medial axis . . . . . . . . . . . . . . . . . . . . . . . 24

3.3 Ukazka citlivosti medial axis . . . . . . . . . . . . . . . . . . . . . . . 25

3.4 Prıklad straight skeletonu . . . . . . . . . . . . . . . . . . . . . . . . 27

4.1 Prıklad modifikovaneho straight skeletonu . . . . . . . . . . . . . . . 29

4.2 Konstrukce straight skeletonu smrst’ovanım – krok 1 . . . . . . . . . . 31




4.6 Ukazka edge event a split event . . . . . . . . . . . . . . . . . . . . . 35

4.7 Ukazka urcenı bodu B pri split event . . . . . . . . . . . . . . . . . . 36

4.8 Ukazka principu vlozenı hrany nulove delce . . . . . . . . . . . . . . . 43

5.1 Prıklad modifikovaneho straight skeletonu, z nejz bude extrahovana

linie . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 48

5.2 Modifikovany straight skeleton bez hran vychazejıcıch z vrcholu po-

lygonu . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 49

5.3 Ilustrace principu prohledavanı do sırky (1) . . . . . . . . . . . . . . 51





5.8 Prevod grafu skeletonu na zjednoduseny binarnı strom – krok 1 . . . 60




5.12 Orezanı zjednoduseneho binarnıho stromu – krok 1 . . . . . . . . . . 66




8

CVUT v Praze SEZNAM OBRAZKU



5.18 Vysledna extrahovana linie . . . . . . . . . . . . . . . . . . . . . . . . 82

6.1 Uzivatelske rozhranı nastroje Polygons to Points . . . . . . . . . . . . 92

6.2 Model nastroje Polygons to Points . . . . . . . . . . . . . . . . . . . 92

6.3 Popis nastroje Polygons to Points . . . . . . . . . . . . . . . . . . . . 93

6.4 Uzivatelske rozhranı nastroje Collapse Polygons to Lines . . . . . . . 99

6.5 Model nastroje Collapse Polygons to Lines . . . . . . . . . . . . . . . 99

6.6 Popis nastroje Collapse Polygons to Lines . . . . . . . . . . . . . . . 100

6.7 Ukazka polygonu pred castecnou redukcı . . . . . . . . . . . . . . . . 101

6.8 Ukazka polygonu po castecne redukci . . . . . . . . . . . . . . . . . . 101

6.9 Uzivatelske rozhranı nastroje Polygons to Points . . . . . . . . . . . . 102

6.10 Model nastroje Polygons to Points . . . . . . . . . . . . . . . . . . . 102

6.11 Popis nastroje Polygons to Points . . . . . . . . . . . . . . . . . . . . 103

6.12 Ukazka chybneho skeletonu . . . . . . . . . . . . . . . . . . . . . . . 104

6.13 Porovnanı – linie z modifikovaneho straight skeletonu . . . . . . . . . 105

6.14 Porovnanı – linie ze straight skeletonu . . . . . . . . . . . . . . . . . 105

6.15 Ukazka kombinace castecne a uplne redukce . . . . . . . . . . . . . . 106

6.16 Ukazka uplne redukce . . . . . . . . . . . . . . . . . . . . . . . . . . . 106

9

CVUT v Praze SEZNAM TABULEK

Seznam tabulek

1.1 Doporucena minimalnı sırka vodnıho toku zobrazeneho polygonem . . 14

6.1 Ukazka vstupnıho textoveho souboru . . . . . . . . . . . . . . . . . . 91

6.2 Ukazka vystupu programu do konzole . . . . . . . . . . . . . . . . . . 94

6.3 Ukazka vystupnıho textoveho souboru . . . . . . . . . . . . . . . . . 95

10

CVUT v Praze UVOD

Uvod

Obraz zemskeho povrchu zachyceny v mapach je nutne generalizovany, protoze

mapovy obraz je oproti skutecnosti zmenseny a nenı tedy mozne zachytit vsechny

jevy v plnem rozsahu. Autor mapy se nejprve musı rozhodnout, ktere prvky zobrazı

a nalezt jejich vhodnou reprezentaci. Cım mensı je merıtko mapy, tım je k jejımu

vytvorenı potrebna vetsı mıra abstrakce. Cılem je zachovat smysl mapy tak, aby byl

jejı ctenar schopen porozumet sdelenı, jez mu chtel kartograf predat.

Ackoli se kartografove uz mnoho let snazı vytvorit jednoznacna pravidla, jak po-

stupovat pri tvorbe map, generalizace je svym zpusobem umenı, a proto zustava jejı

vysledek subjektivnı, ovlivneny osobou kartografa. To se nezmenilo ani s rozvojem

pocıtacove techniky, jelikoz faktory ovlivnujıcı kvalitu mapy a pozadavky na vlast-

nosti vysledneho produktu lze formalizovat jen velmi obtızne nebo vubec ne.

Presto je vyvoj generalizacnıch algoritmu dulezitou cinnostı, protoze automati-

zovane zpracovanı generalizovaneho mapoveho obrazu muze vyrazne usnadnit praci

kartografa, ktery casto urcuje vysledek automatizovaneho postupu volbou parametru

generalizacnıho algoritmu, vyberem prvku a naslednymi upravami vystupu.

Tato prace se v prvnı casti venuje obecnemu prıstupu ke generalizaci v digitalnım

prostredı. Dalsı kapitoly se zabyvajı ruznymi typy skeletonu, liniovych struktur re-

prezentujıcıch plosne prvky, ktere se v kartografii casto pouzıvajı pro generalizaci

technikou redukce prostorove dimenze. Hlavnım cılem prace je navrh a implemen-

tace algoritmu pro generalizaci vodnıch toku technikou redukce prostorove dimenze.

Pro prevod polygonove reprezentace vodnıho toku na liniovou prace predstavuje

novou geometrickou strukturu modifikovany straight skeleton.

11

CVUT v Praze 1. KARTOGRAFICKA GENERALIZACE

1 Kartograficka generalizace

Pri tvorbe map se snazıme dosahnout vysoke informacnı hodnoty a zaroven

urcite esteticke kvality, dıky cemuz je jejich ctenari mohou pouzıvat v souladu

s ucelem, za jehoz dosazenım vznikly. Mapa ze sve podstaty zachycuje zmenseny

obraz skutecnosti, coz odpovıda jejı definici, jak ji uvadı Mezinarodnı kartograficka

asociace (ICA):

”Mapa je zmensene zevseobecnene zobrazenı povrchu Zeme, ostatnıch nebeskych

teles nebo nebeske sfery, sestrojene podle matematickeho zakona na rovine a vy-

jadrujıcı pomocı smluvenych znaku rozmıstenı a vlastnosti objektu vazanych na

jmenovane povrchy.“ [1]

I jak ji nachazıme v CSN 73 0402:

”Mapa je zmenseny generalizovany konvencnı obraz Zeme, nebeskych teles, kos-

mu, ci jejich castı, prevedeny do roviny pomocı matematicky definovanych vztahu

(kartografickym zobrazenım), ukazujıcı podle zvolenych hledisek polohu, stav a vzta-

hy prırodnıch, socioekonomickych a technickych objektu a jevu.“ [2]

Protoze mapa tedy nemuze zachytit vsechny skutecnosti v plnem rozsahu a geo-

metricky verne, je nutne provest urcite zjednodusenı, zevseobecnenı zobrazovanych

jevu, aby se dosahlo citelnosti mapove kresby. Tento postup se nazyva kartograficka

generalizace. Jejı definice uvedena v CSN 73 046 znı:

”Kartograficka generalizace spocıva ve vyberu, geometrickem zjednodusenı a

zevseobecnenı objektu, jevu a jejich vzajemnych vztahu pro jejich graficke vyjadrenı

v mape, ovlivnene ucelem, merıtkem mapy a vlastnım predmetem kartografickeho

znazornovanı.“ [3]

12


Cılem generalizace je zachytit pomocı mapove kresby hlavnı a podstatne jevy

nejenom vzhledem k merıtku, ve kterem mapa vznika, ale take podle jejıho ucelu.

Dulezitym faktorem je pri procesu generalizace zachovanı vzajemnych vazeb mezi

prvky tak, jak tyto vztahy fungovaly v realite. Protoze podstatu generalizace nenı

mozne zredukovat na soubor nejakych univerzalnıch pravidel, vzdy velmi zalezı na

osobe kartografa a na jeho rozhodnutıch v jednotlivych prıpadech [4, str. 28].

Rozvoj pocıtacove techniky prinesl i do kartograficke generalizace snahu o auto-

matizaci tohoto procesu. Osoba kartografa je nahrazena generalizacnım algoritmem,

ale proto, aby byl tento algoritmus schopen rozhodovat v jednotlivych prıpadech

stejne, jako by tuto volbu musel provest kartograf, je obvykle nutne nastavit urcita

vstupnı kriteria a parametry, coz opet cinı vysledek automatizovane generalizace

subjektivnım.

1.1 Generalizace vodstva

Kartografie chape vodstvo jako souhrn prırodnıch a umelych vodnıch objektu a

hydrotechnickych zarızenı s nimi souvisejıcıch, jez jsou zakresleny na mape. Radı se

mezi ne [5, str. 30(57)]:

• vodnı toky a kanaly (tekoucı vodstvo),

• jezera, rybnıky a vodnı nadrze,

• baziny a mocaly,

• prameny a studny,

• more a oceany,

• ledovce a trvala snehova pokryvka,

• hydrotechnicka zarızenı.

Dale se tato prace zabyva predevsım vodnımi toky, u nichz se generalizace casto

provadı redukcı jejich dimenze z plosnych objektu na liniove. Pozornost by se mela

13


venovat i jezerum, rybnıkum a vodnım nadrzım, protoze v mnoha prıpadech lezı na

vodnıch tocıch a ve vstupnı digitalnı reprezentaci dat nemusı byt polygony stojate

a tekoucı vody rozliseny. Pro dosazenı korektnıho generalizovaneho vystupu je ale

vhodnejsı, pokud uzivatel provede klasifikaci dat pred jejich zpracovanım.

1.1.1 Generalizace vodnıch toku

”Vodnı toky (a kanaly) se vykreslujı na obecne zemepisnych mapach od pramene

jednoduchou plynule se rozsirujıcı carou [5, str. 30(57)].“ Ve chvıli, kdy skutecna

sırka vodnıho toku presahne v merıtku mapy 0,3 mm, zacne se zobrazovat jako po-

lygonovy prvek. Tento meznı rozmer se vztahuje k hodnote nejmensıho rozlisitelneho

bodu, ktera se u nas pohybuje v rozmezı 0,23 az 0,28 mm [6]. Doporucena hranicnı

skutecna sırka vodnıho toku, kdy dochazı k prechodu mezi liniı a polygonem, je pro

jednotliva merıtka, v nichz se vyhotovujı topograficke mapy, uvedena v tabulce 1 [5,

str. 30(57)].

Merıtko Skutecna sırka toku v metrech

1 : 10 000 nad 5 m [7]

1 : 25 000 nad 15 m

1 : 50 000 nad 30 m

1 : 100 000 nad 60 m

Tab. 1.1: Doporucena minimalnı sırka vodnıho toku zobrazeneho polygonem

U obecne zemepisnych map (v merıtku mensım nez 1 : 200 000) dochazı ke

znacne mıre abstrakce, a proto se pri jejich automatizovane generalizaci doporucuje

pouzıvat jine algoritmy a postupy nez pro topograficke mapy [4, str. 29].

Vodnı tok jako liniovy prvek je dany mnozinou souradnic prostorove definujıcı

prubeh proudnice [4, str. 28]. Vodnı tok musı vzdy respektovat relief, tedy sledovat

udolnici. Pokud se generalizace vodnıho toku provadı oddelene od tvorby napr. vrs-

tevnic, muze se stat, ze toto pravidlo nebude splneno. Tuto situaci lze resit zasahem

kartografa v dalsım kroku zpracovanı, ktery opravı polohu toku, cımz se ale do

14


vysledne mapy vnası dalsı subjektivnı prvek [4, str. 28]. Kdyz vodnı toky tvorı rıcnı

soustavu, mela by po generalizaci zustat zachovano jejı usporadanı a hustota. K

tomuto ucelu lze pouzıt ruzne klasifikace, praktickou aplikaci uvadı napr. [8].

15

CVUT v Praze 2. DIGITALNI GENERALIZACE

2 Digitalnı generalizace

Logicky ramec pro kartografickou generalizaci v digitalnım prostredı se snazı po-

skytnout Shea a McMaster [9] a uvadı tuto definici digitalnı generalizace:

”Digitalnı generalizace muze byt definovana jako proces odvozenı symbolicky ci

digitalne ulozeneho souboru kartografickych dat z datoveho zdroje s vyuzitım pro-

storovych a atributovych transformacı.“ [9, str. 3–4]

Auto5i tento proces delı na tri komponenty [9, str. 56]. Prvnım z nich jsou filo-

soficka vychodiska generalizace, cili proc generalizujeme. Jako dalsı uvadı kartome-

tricke vyhodnocenı, tedy rozpoznanı kdy generalizovat. Poslednı komponentu tvorı

prostorove a atributove transformace, ktere urcujı jak generalizovat.

2.1 Filosoficka vychodiska digitalnı generalizace

Filosoficka vychodiska, proc provadet generalizaci v digitalnım prostredı, zahr-

nujı tri soucasti, faktory teoreticke, faktory urcene funkcı mapy a vypocetnı faktory

[9, str. 27].

2.1.1 Teoreticke faktory

Nejdrıve je nutne se zabyvat teoretickymi faktory, coz jsou obecne, intuitivnı

kartograficke generalizacnı principy, ktere pomahajı redukovat nechtene dusledky

zmensovanı merıtka na mapovy obraz. Aby proces generalizace mohl fungovat v di-

gitalnım prostredı, je nutne rozlisovat techto sest teoretickych faktoru [9, str. 28–34]:

Redukce slozitosti

Slozitost mapove kresby muzeme chapat jako vzajemne vizualnı pusobenı jejıch

soucastı. Mnozstvı a rozmanitost techto grafickych prvku ma vyrazny vliv na sro-

zumitelnost obsahu mapy jejımu uzivateli. Pri zmene merıtka mapy je nutne najıt

16


spravnou mıru slozitosti mapove kresby tak, aby byla zachovana jejı citelnost a

zaroven nedoslo ke ztrate podstatnych jevu a jejich vzajemnych vztahu [9, str. 28–29].

Zachovanı prostorove presnosti

Pri generalizaci se snazıme i o co nejmensı ztratu prostorove informace mezi

puvodnım prvkem a jeho zjednodusenou reprezentacı. Cım mensı je merıtko mapy,

tım mensı je potreba zachovat presnost obrazu [9, str. 29].

Zachovanı atributove presnosti

Pro udrzenı spravnosti atributu prvku mapoveho obrazu se pri jejich digitalnı

reprezentaci pouzıvajı statisticke a klasifikacnı metody [9, str. 30]. Vetsı pozornost

se musı venovat zachovanı atributu pri praci tematickymi mapami.

Zachovanı esteticke kvality

Pres snahu stanovit presna pravidla pro kartografickou tvorbu, jde stale o proces,

ktery v sobe zahrnuje umelecky aspekt, a proto ho nelze plne zformalizovat [9,

str. 33]. Mapa by mela mıt urcitou extetickou hodnotu, aby se s nı lepe pracovalo.

Zachovanı logicke hierarchie

Behem generalizace je vhodne najıt vztahy logicke vyznamove nadrazenosti a

podrazenosti mezi jednotlivymi prvky mapove kresby a pomocı nich urcit jejich

prioritu pri zobrazovanı v mape [9, str. 33]. Dulezite a zaroven komplikovane je

najıt tuto hierarchii mezi vsemi geometrickymi i vyznamovymi kategoriemi prvku,

ktere se vyskytujı v generalizovane mape.

Konzistentnı pouzıvanı generalizacnıch pravidel

Vysledky automatizovaneho procesu generalizace nejsou zbaveny subjektivity,

ale pokud by se nalezlo presne urcenı jake algoritmy pouzıt, v jakem poradı a

s jakymi vstupnımi parametry, aby se dosahlo pozadovaneho vystupu v pozadovanem

merıtku, doslo by ke snızenı teto subjektivity [9, str. 34]. Takovyto postup zatım

17


stale jeste nebyl objeven, proto automatizovana generalizace slouzı spıse k usnadnenı

prace kartografu a vysledny vystup obvykle jeste potrebuje zasah cloveka.

2.1.2 Faktory urcene funkcı mapy

Mıru generalizace urcuje funkce, jiz ma mıt vysledna mapa [9, str. 35–38]. Obsah

mapy a jejı vzhled by mel odpovıdat ucelu mapy a zamyslenemu okruhu uzivatelu.

Velky vliv ma i volba vhodneho merıtka. Prvky mapoveho obrazu musı byt take

prizpusobeny schopnostem lidskeho vnımanı.

2.1.3 Vypocetnı faktory

Pokud pracujeme s prostorovymi daty v digitalnım prostredı, musıme uvazovat

i parametry vypocetnı techniky. Snazıme se tedy, aby algoritmy, ktere pouzıvame,

byly efektivnı a vhodne kombinovaly casovou narocnost vypoctu, presnost vystupu

a pozadavky na hardware [9, str. 38–42]. Zohlednuje se i velikost digitalne uchovava-

nych dat.

2.2 Kartometricke vyhodnocenı

Zda je po zmensenı merıtka potreba generalizovat, muzeme urcit kartometrickym

vyhodnocenım, ktere se podle Shea a McMaster [9, str. 42–43] delı na geometricke

situace, prostorove a holisticke parametry a faktory rıdıcı transformaci.

2.2.1 Geometricke situace

Pri zmensenı merıtka se mohou objevit tyto geometricke situace [9, str. 43–46]:

• nahromadenı – prılis mnoho prvku se nachazı v omezenem prostoru,

• prekrytı – prvky se mohou castecne nebo uplne prekryvat,

• konflikt – prvek se dostane do logickeho rozporu s ostatnımi prvky (pr. most

pres reku, ktera byla pri generalizaci odstranena)

18


• komplikace – rozdıl ve vysledku generalizacnıho postupu kvuli urcitym podmın-

kam, ktere existujı v danem bode v case, ale mohou se lisit v bode jinem,

• nekonzistentnost – generalizacnı pravidla nejsou aplikovana stejne v celem

rozsahu mapove reprezentace,

• nerozlisitelnost – jednotlive prvky jsou prılis male a prılis blızko, nez aby mohly

byt rozliseny.

Problematickou zustava kvantifikace techto situacı tak, aby byly spravne identi-

fikovany.

2.2.2 Prostorove a holisticke charakteristiky

Prostorove a holisticke charakteristiky vyjadrujı vnitrnı a vnejsı vztahy a inter-

akce v ramci jedno, dvou nebo vıce prvku. Pomahajı nam stanovit podmınky, kdy

uz je treba pristoupit ke generalizaci. Patrı mezi ne naprıklad [9, str. 46–48]:

• mıra hustoty,

• rozlozenı

• delka a klikatost,

• tvarove charakteristiky,

• vzdalenosti,

• Gestalt charakteristiky – isomorfismus prvku,

• abstraktnı charakteristiky – vyznamove charakteristiky prostroveho rozlozenı

prvku.

Vetsinu uvedenych charakteristik, krome Gestalt a abstraktnıch, lze relativne

snadno implementovat v prostredı GIS a pouzıvat pri rozhodovanı, zda generalizovat

ci ne [9, str. 48].

19


2.2.3 Faktory rıdıcı transformaci

Soucastı procesu generalizace je mnozstvı generalizacnıch operatoru, ktere se

zamerujı na ruzne problemy a resı se ruznymi algoritmy. Poradı techto operatoru,

jejich algoritmy a vstupnı parametry majı velky vliv na vysledek transformacı behem

generalizace [9, str. 48–51].

2.3 Prostorove a atributove transformace

Prostorove a atributove transformace provadı generalizacnı operatory a modi-

fikujı tak vstupnı data. Oba typy transformacı nemusı byt nezavisle, ale mohou

byt naopak velmi provazane [9, str. 51]. Geograficka generalizace se zabyva geome-

trickymi manipulacemi s prostorovymi informacemi prvku, at’ uz v rastrovem nebo

vektorovem formatu. Statisticka generalizace zahrnuje jak klasifikaci, tak symboli-

zaci [9, str. 53]. Dalsı cast teto kapitoly se soustredı na vektorova data, i kdyz popi-

sovane operatory mohou mıt urcity ekvivalent tez v rastrovem modelu [9, str. 54].

V digitalnım prostredı je nezbytnym krokem pred zahajenım samotne genera-

lizace vyber prvku, na ktere budou pouzity prostorove a atributove transformace.

Behem generalizacnıho procesu muze dochazet i k dalsım vyberum.

2.3.1 Prostorove transformace

Operatory prostorovych transformacı menı prvky z pohledu geografickeho nebo

topologickeho [9, str. 54]. Kdyz dochazı ke zmensenı merıtka mapy, snızı se i velikost

prostoru pro umıstenı prvku mapoveho obrazu, a proto je nutne upravit jejich vzhled

nebo je uplne odstranit tak, aby byla zachovana citelnost mapy. K tomu slouzı tyto

prostorove transformace [9, str. 54–63]:

• Zjednodusenı – snızenı poctu bodu reprezentujıcıch tvar prvku pri zachovanı

jeho vyznamnych charakteristik.

• Vyhlazenı – zlepsenı estetickeho vzhledu.

• Agregace – nahrazenı vıce bodovych prvku polygonem.

20


• Amalgamace – spojenı vıce polygonu blızko u sebe do jedineho.

• Slucovanı – nahrazenı dvou liniı blızko sebe jedinou liniı, ktera lezı priblizne

mezi nimi.

• Prostorova redukce – prevod polygonu na bod nebo linii.

• Procistenı – odstranenı prılis malych ci nepodstatnych prvku.

• Kresba pres mıru – zvetsenı casti prvku.

• Posun – zmena polohy prvky tak, aby se zabranilo konfliktu nebo aby byly

zachovany logicke vztahy.

Vyzkum prostorovych operatoru stale probıha a zatım nepanuje shoda o jejich

rozdelenı a funkcıch. Vyse uvedeny vycet vsak muze slouzit pro zakladnı prehled.

2.3.2 Atributove transformace

Shea a McMaster [9, str. 63–66] identifikujı dva typy atributovych transformacı,

klasifikaci a symbolizaci. Pri klasifikaci se jednotlive prvky rozdelujı do kategoriı

podle hodnoty sveho atributu s procesem symbolizace se prvkum priradı vhodne

graficke reprezentace.

21

CVUT v Praze 3. SKELETONIZACE

3 Skeletonizace

Jednou z geometrickych struktur, ktere lze pouzıt pro popis tvaru polygonoveho

prvku, je skeleton. K definici podstaty skeletonu muzeme pristupovat ze dvou hle-

disek [10, str. 146]. Prvnı prıstup vnıma skeleton jako urcitou medialnı strukturu,

tedy entitu, ktera existuje vzdy uvnitr prvku a je v kazdem svem bode ekvidistantnı

k hranici tohoto prvku. Tyto skeletony se nazyvajı geometricke a zachovavajı prosto-

rove charakteristiky prvku [10, str. 146]. Postupy, jak zıskat geometricky skeleton,

lze rozdelit do ctyr kategoriı podle metody, kterou pouzıvajı [10, str. 147]:

• extrakce skeletonu z Voronoiovych diagramu,

• simulace vypalovanı travy,

• topologicke smrst’ovanı,

• extrakce skeletonu z mapy vzdalenostı.

Z jine perspektivy muzeme skeleton chapat jako explicitnı reprezentaci toho,

jak jsou na sebe navazany zakladnı komponenty tvaru tak, aby vytvorily celek.

Jedna se pak o topologicky skeleton, pri jehoz vzniku se prvek nejdrıve rozlozı

na zakladnı casti, ze kterych se sklada. Podle soucasnych vyzkumu stejny postup

probıha v prvnıch fazıch kognitivnıho procesu, kdyz clovek vnıma zrakem [10, str.

146].

3.1 Skeleton jako kartograficky operator

Skeleton se casto pouzıva jako jeden z operatoru pri prostorovych transfor-

macıch v kartografii. Jelikoz geometricky skeleton ve vysoke mıre zachovava vztahy

k puvodnımu tvaru prvku, v mnoha prıpadech je mozne pouze na zaklade skele-

tonu prvek zpetne zrekonstruovat, nabızı se jeho vyuzitı pri generalizaci technikou

redukce prostorove dimenze. V nasledujıcım prehledu budou popsany pouze vek-

torove formy operatoru skeletonizace, protoze prace se primarne zabyva vyuzitım

geometricke struktury straight skeleton pro generalizaci polygonu vodnıch toku a

stojatych vod.

22


3.1.1 Medial axis

Medial axis, neboli strednı osa, uzavreneho, ohraniceneho regionu C v R2 je

definovana jako mnozina bodu, ktere majı alespon dva nejblizsı body na hranici

regionu C [11]. Konkretneji:

”Medial axis M mnoziny C oznacovana jako M(C) predstavuje takovou mnozinu

bodu q, pro ktere existujı nejmene dva ruzne body pi, pj na hranici C takove, ze

vzdalenost d(q, pi) = d(q, pj) a obe vzdalenosti jsou minimalnı vzdalenostı mezi bo-

dem q a hranicı C.“ [12, str. 6] Bod q je oznacovan jako bod skeletonu.

Nejznamejsı popis strednı osy, tzv. Medial Axis Transform (MAT) uvedl v roce

1967 Blum [13]. Jeho prıstup operuje s predstavou ohne, ktery zacına ve vsech bodech

hranice oblasti ve stejnou chvıli a izotropne se sırı konstantnı rychlostı smerem

dovnitr prvku. Mısta, kde dojde ke kolizi cel pozaru, tvorı medial axis. Medial axis

uzavrene oblasti si take muzeme predstavit jako mnozinu stredu vsech kruznic, ktere

se dotykajı hranic teto oblasti alespon ve dvou bodech a zaroven lezı uvnitr teto

oblasti [14, str. 22].

Obr. 3.1: Prıklad medial axis

23


V euklidovskem prostoru dimenze k, Rk, ma strednı osa obecne dimenzi k − 1,

tedy dimenzi o jednu mensı nez oblast, ze ktere vznikla. Pro polygony rovine v R2

se medial axis sklada z prımych liniı a parabolickych oblouku, ktere jsou generovany

nekonvexnımi vrcholy. V kazdem konvexnım vrcholu polygonu koncı jedna hrana

strednı osy [10, str. 148].

Medial axis ma hladky a plynuly vzhled, coz je jeden z duvodu, proc byva

pouzıvana v kartografii. Fakt, ze muze byt tvorena nejen liniemi, ale i parabolickymi

oblouky, je ale nevyhodny pro jejı aplikaci v digitalnım prostredı, proto casto dochazı

k aproximaci medial axis strukturou, ktera se sklada pouze z prımych liniovych seg-

mentu [15, str. 170]. Strednı osa reprezentuje tvar polygonu, zaroven je ale velmi

citliva i na drobne zmeny polohy ve vstupnı mnozine vrcholu polygonu.

Obr. 3.2: Ukazka velke citlivosti medial axis na zmeny v topologii

24


3.1.2 Chordal axis

Pro uzavrene utvary v R2, jejichz hrany jsou reprezentovany useckami, lze zkon-

struovat skeleton Delaunay triangulacı se vstupnı podmınkou nebo konformnı Delau-

nay triangulacı [15, str. 171]. Ze zıskane triangulace lze extrahovat tzv. chordal axis,

jez se sklada jen z usecek. Poprve ji v roce 1997 popsal Prasad [16]. Zakladnı postup

platny pro oba prıstupy k triangulaci muze byt popsan zhruba takto:

a) Pro kazdy trojuhelnık, ktery ma jednu spolecnou hranu s polygonem, se hrana

skeletonu zkonstruuje spojenım stredu zbylych dvou hran trojuhelnıku.

b) Trojuhelnıky, jez nemajı zadnou spolecnou hranu s polygonem, se musı zpra-

covat zvlastnım postupem. Obvykle tyto trojuhelnıky generujı tri hrany ske-

letonu, jez vzniknou spojenım teziste trojuhelnıku se stredy jeho stran.

Obr. 3.3: Ukazka chordal axis zıskane pomocı Delaunay triangulace

Vpravo je videt nevhodny vybezek.

25


Za pravdepodobne nejvetsı nevyhodou skeletonu nalezeneho pomocı Delaunay

triangulace se da povazovat moznost vzniku nechtenych vybezku v mıstech trojuhel-

nıku, ktere nemajı zadnou spolecnou hranu s polygonem [17]. Ukazka takoveto situ-

ace je videt na obrazku 3.3. Tento problem lze resit nastavenım dalsıch pravidel, jak

tento typ trojuhelnıku zpracovavat, coz muze byt komplikovane v prıpadech, kdy

spolu sousedı vıce takovychto trojuhelnıku.

3.1.3 Straight skeleton

Tento typ skeletonu pro polygony v rovine predstavili v roce 1995 Aichholzer a

kol. [18]. Velkou vyhodou straight skeletonu je oproti drıve objevene medial axis, ze

se sklada, jak uz jeho nazev naznacuje, pouze z prımych liniovych segmentu. Pro

konvexnı polygony jsou medial axis a straight skeleton totozne [18, str. 752].

Proces vzniku straight skeletonu je mozne si predstavit jako postupne smrst’ovanı

polygonu konstantnı rychlostı. Behem tohoto smrst’ovanı se kazdy vrchol daneho po-

lygonu posunuje po ose uhlu prilehlych stran polygonu, dokud nedojde ke zmene to-

pologie hranice. Aichholzer a kol. uvadı dve mozne zmeny topologie [18, str. 752–753]:

Edge event – hrana polygonu se smrstı na nulovou velikost, cımz se stanou

jejı sousednı strany prilehlymi.

Split event – hrana polygonu je rozdelena, pokud se pri procesu smrst’ovanı

setka s nekonvexnım vrcholem, cımz je rozdelen cely polygon. Pri teto situaci

vznikajı nove dvojice prilehlych stran mezi rozdelovanou stranou a hranami

prıslusejıcımi k danemu nekonvexnımu vrcholu. Kdyz majı nove casti polygonu

vznikle jeho rozdelenım v dusledku split event plochu vetsı nez nula, proces

smrst’ovanı v nich nezavisle pokracuje dal.

Vysledny straight skeleton je slozen z castı os uhlu, po kterych se pohybovaly

vrcholy behem procesu smrst’ovanı. Skeleton generuje rozdelenı polygonu na poly-

gonalnı plochy, pricemz kazde hrane polygonu je prirazena prave jedna. Polygony

vznikle tımto delenım jsou monotonnı 1.

1

”Mnohouhelnık P je monotonnı vzhledem prımce q, prave kdyz kazda prımka t⊥q protne P

nejvyse dvakrat“ [19, str. 15]

26


Plochy vznikle rozdelenım polygonu pomocı straight skeletonu mohou reprezen-

tovat roviny konstantnıho spadu 45 ◦. Tyto roviny si je pak mozne predstavit jako

casti strechy a spojenım bodu se stejnou vyskou dostavame linii vyjadrujıcı offset

polygonu.

Nejpouzıvanejsı implementaci algoritmu pro nalezenı straight skeletonu kon-

vexnıch i nekonvexnıch polygonu vcetne polygonu s dırami predstavili v roce 1998

Felkel a Obdrzalek [20].

Obr. 3.4: Prıklad straight skeletonu

27


3.1.4 Linear axis

Pokud se v polygonu nachazı vyrazne nekonvexnı uhel, vzhled jeho straight skele-

tonu odporuje intuitivnı predstave, jak by skeleton takoveho polygonu mel vypadat.

Toto chovanı je zpusobeno tım, ze pri smrst’ovanı se nekonvexnı vrcholy pohybujı

po svych prıslusnych osach uhlu rychleji nez konvexnı vrcholy.

Tento problem vedl Tanase a Veltkampa [21] k tomu, aby v roce 2004 navrhli

novy typ skeletonu, ktery nazvali linear axis. Princip zıskanı linear axis je obdobne

jako u straight skeletonu zalozen na procesu smrst’ovanı s tım rozdılem, ze umoznuje

zmensit nesoulad v rychlosti pohybu vrcholu v jakekoli zvolene mıre, ackoli jej nelze

snızit az na nulu.

K dosazenı tohoto cıle autori pouzıvajı tzv. skryte hrany, ktere majı nulovou

delku a vkladajı se do nekonvexnıch vrcholu, pricemz jejich pocatecnı a koncovy

bod majı stejne souradnice jako vrchol, do nejz se vlozı.

Formalneji lze tento postup popsat nasledovne [10, str. 163]: Necht’ {v1, v2, . . . , vn}

oznacuje vrcholy polygonu P a necht’ k = (k1, k2, . . . , kn) je posloupnost prirozenych

cısel. Pokud je vi konvexnı vrchol P , pak ki = 0, a pokud je vi nekonvexnı vrchol,

pak ki ≥ 0. Necht’ je P κ(0) polygon vznikly z P nahrazenım kazdeho nekonvexnıho

uhlu viki + 1 identickymi vrcholy, koncovymi body ki hran o nulove delce (skryte

hrany) prıslusnym vrcholu vi. Smery skrytych hran jsou voleny tak, ze nekonvexnı

vrchol vi polygonu P je v novem polygonu P κ(0) nahrazen ki+1 konvexnımi vrcholy

se shodnym vnitrnım uhlem.

Polygon s novymi vrcholy P κ(0) se pak pouzije k stejnemu smrst’ovacımu pro-

cesu jako u straight skeletonu. Casti os uhlu vychazejıcı z vrcholu vlozenych hran

nejsou soucastı linear axis. Protoze osy uhlu prıslusne nekonvexnım vrcholu byly

odstraneny, zıskana linear axis v danem mıste aproximuje medial axis a zustava

slozena pouze z usecek. Cım vıce skrytych hran se vlozı do nekonvexnıho vrcholu,

tım presnejsı se zıska aproximace medial axis. Pri praktickem pouzitı se ukazuje,

ze pro dosazenı pomerne presne aproximace je dostacujı vlozit do vrcholu pouze

nekolik malo hran.

28

CVUT v Praze 4. MODIFIKOVANY STRAIGHT SKELETON

4 Modifikovany straight skeleton

Pro generalizaci vodnıch toku technikou redukce prostorove dimenze se straight

skeleton obecne jevı jako vhodna struktura, protoze dobre popisuje puvodnı tvar

polygonoveho prvku pred jeho redukcı na prvek liniovy a zaroven ma oproti medial

axis tu vyhodu, ze se sklada pouze z usecek. Problematicke ovsem mohou byt si-

tuace, kdy generalizovany polygon obsahuje jeden nebo vıce nekonvexnıch vrcholu,

jelikoz takoveto vrcholy zasahujı do vysledneho tvaru skeletonu mnohem vıce nez

vrcholy konvexnı. Pri generalizaci vodnıho toku jako plosneho prvku na linii by tato

linie mela vest jeho osou, pricemz se muze stat, ze pri pouzitı straight skeletonu

jako generalizacnıho operatoru nebude toto pravidlo dodrzeno v dusledku prılisneho

vlivu nekonvexnı vrcholu na tvar skeletonu.

Obr. 4.1: Prıklad modifikovaneho straight skeletonu

29


Tato prace se snazı resit vyse uvedeny problem navrzenım nove geometricke

struktury modifikovany straight skeleton, ktera vyuzıva obdobny prıstup jako linear

axis. Do nekonvexnıch vrcholu vychozıho polygonu jsou vlozeny tzv. nulove hrany,

tedy hrany o nulove delce. Souradnice jejich pocatecnıho a koncoveho bodu jsou

shodne se souradnicemi nekonvexnıho vrcholu. Na rozdıl od linear axis je do kazdeho

nekonvexnıho vrcholu vlozena pouze jedna nulova hrana a jejı smer je kolmy na osu

nekonvexnıho uhlu pri danem vrcholu.

4.1 Implementace straight skeletonu podle Felkel

& Obdrzalek

Pri implementaci generalizacnıho algoritmu pro prostorovou redukci vodstva byla

vyuzita implementace stragiht skeletonu, kterou navrhli Felkel a Obdrzalek [20]. Je-

jich algoritmus vychazı z principu konstrukce strechy postupnym smrst’ovanım poly-

gonu, ale mısto toho, aby se pro kazdy prusecık os uhlu konstruoval stav smrst’ovaneho

polygonu v tomto bode, pracuje se pouze s ukazateli na hrany puvodnıho polygonu.

Behem smrst’ovanı dochazı ke zmenam v topologii polygonu, tedy k edge events

nebo split events, jak byly popsany v predchozı kapitole.

Zakladnı datova struktura, kterou algoritmus vyuzıva, je set kruhovych seznamu

aktivnıch vrcholu SLAV (set of circular lists of active vertices), v nemz jsou ulozeny

cykly vrcholu na vnejsı hranici polygonu a na hranicıch der v polygonu a cykly

vrcholu polygonu, ktere vznikly rozdelenım polygonu behem vypoctu straight ske-

letonu. Jednotlive seznamy vrcholu LAV (list of active vertices) jsou ulozeny ve

SLAV. V prıpade konvexnıho polygonu obsahuje SLAV pouze jeden LAV. Kazdy

vrchol v LAV si udrzuje informaci o vrcholech, ktere s nım v LAV sousedı.

30


Obr. 4.2: Konstrukce straight skeletonu smrst’ovanım – krok 1 (edge event)

Obr. 4.3: Konstrukce straight skeletonu smrst’ovanım – krok 2 (split event)

31




32


4.1.1 Vypocet straight skeletonu konvexnıho polygonu

Pri konstrukci straight skeletonu S(P) konvexnıho polygonu P dochazı pouze k

edge events, protoze split event je zpusobena nekonvexnım vrcholem. Nasledujıcı

popis kroku vypoctu predpoklada, ze vrcholy a hrany polygonu jsou orientovany

proti smeru hodinovych rucicek a vnitrek polygonu se pak nachazı po leve strane

hranice polygonu [20].

Algoritmus pro vypocet straight skeletonu konvexnıho polygonu [20]:

1. Inicializace:

a) Vloz dane vrcholy V1, V2 . . . , Vn do jednoho dvojite propojeneho kru-

hoveho seznamu aktivnıch vrcholu (LAV) ulozeneho v SLAV. V tomto

okamziku jsou vsechny vrcholy v LAV aktivnı.

b) Kazdemu vrcholu Vi v LAV pridej ukazatele na jeho dve prilehle hrany

ei−1 = Vi−1Vi a ei = ViVi+1 a vypocıtej osu uhlu, ktery svırajı tyto dve

hrany, tzv. bisektor (poloprımku) bi.

c) Pro kazdy vrchol Vi vypocıtej nejblizsı prusecık jeho bisektoru bi s bi-

sektory sousednıch vrcholu bi−1 a bi+1, ktere zacınajı ve vrcholech Vi−1

a Vi+1. Pokud takovyto prusecık existuje uloz ho do prioritnı fronty na

zaklade jeho vzdalenosti od prımky L(ei), na ktere lezı hrana ei. Pro

kazdy prusecık Ii uloz take dva ukazatele na vrcholy Va a Vb, v nichz

majı pocatek bisektory, jejichz protnutım prusecık Ii vznikl. Tyto uka-

zatele jsou nezbytne k nalezenı spravnych hran pro vypocet bisektoru

v nasledujıcıch krocıch algoritmu.

2. Dokud prioritnı fronta nenı prazdna:

a) Vezmi prusecık I na zacatku prioritnı fronty.

b) Pokud jsou vrcholy Va a Vb, na nez ukazuje I, oznaceny jako zpracovane,

preskoc ke kroku 2. V opacnm prıpade se hrana e mezi vrcholy Va a Vb

smrstı na nulovou velikost, dojde k edge event.

33


c) Pokud je predchudce predchudce Va roven Vb (vrchol strechy), pak pridej

do straight skeletonu tri hrany VaI, VbI a VcI, pricemz Vc je predchudce

Va a zaroven nasledovnık Vb v LAV , a preskoc ke kroku 2.

d) Pridej do straight skeletonu dve hrany VaI a VbI.

e) Uprav seznam aktivnıch vrcholu:

– Oznac vrcholy Va a Vb za zpracovane.

– Vytvor novy vrchol V o souradnicıch prusecıku I.

– Vloz tento novy vrchol V do LAV a propoj jej s predchudcem Va a

naslednıkem Vb v LAV.

– Propoj novy vrchol V s prıslusnymi hranami ea a eb, na nez ukazujı

vrcholy Va a Vb.

f) Pro novy vrchol V vytvoreny z I spocıtej:

– novou osu uhlu sevreneho hranami ea a eb bisektor b,

– prusecıky tohoto bisektoru b s bisektory zacınajıcımi v sousednıch

vrcholech v LAV stejnym zpusobem jako v kroku 1c.

– Pokud nejaky existuje, uloz blizsı prusecık do prioritnı fronty.

V krocıch 1c a 2f se do prioritnı fronty ukladajı duplicitnı prusecıky, jez jsou ale

odstraneny v kroku 2b.

4.1.2 Vypocet straight skeletonu nekonvexnıho polygonu

Princip vypoctu straght skeletonu nekonvexnıho polygonu je obdobny jako pro

konvexnı polygon. Vypoctene nove prusecıky se ukladajı do prioritnı fronty, ale na

rozdıl od predchozıho postupu majı atribut, ktery oznacuje, jestli vznikly pri edge

event nebo split event.

Nekonvexnı vrchol polygonu muze zpusobit jak edge event, tak split event. Vrchol

straight skeletonu, ktery vznikne pri split event, si pro ucely dalsıho popisu oznacıme

B. Bod B muzeme definovat jako bod, ktery ma stejnou kolmou vzdalenost od

prımky prochazejıcı hranou, jez je”protilehlou“ k vrcholu V , a od obou prımek

prochazejıcıch hranami, ktere zacınajı ve vrcholu V [20]. Abychom urcili souradnice

34


bodu B, musıme najıt tuto”protilehlou“ hranu tak, ze otestujeme vsechny hrany e

puvodnıho polygonu.

Obr. 4.6: Ukazka edge event a split event

V bode A zpusobil nekonvexnı vrchol split event a v bode B split event.

Vsechny konvexnı vrcholy zpusobily edge event.

Vrchol V musı lezet uvnitr trojuhelnıku tvoreneho testovanou hranou ei a bi-

sektory bi a bi+1, ktere zacınajı v jejıch vrcholech. Algoritmus testuje, zda exis-

tuje prusecık mezi prımkou prochazejıcı hranou ei a bisektorem, ktery zacına ve

vrcholu V . Kdyz je prusecık nalezen, urcı se potencialnı bod Bi jako prusecık bi-

sektoru z vrcholu V a bisektoru vychazejıcıch z prusecıku testovane hrany ei a prod-

louzenych hran prilehlych vrcholu V (obr. 4.7). Vysledny bod B se vybere ze vsech

potencialnıch bodu Bi jako ten, ktery lezı nejblıze vrcholu V .

Kdyz dojde k split event, polygon se rozpadne na dve casti a je tedy nutne

rozdelit i LAV a do obou novych LAV vlozit nove vznikly vrchol o souradnicıch

bodu B. Algoritmus pracuje i se specialnım prıpadem, kdy dojde k vıcenasobnemu

rozdelenı hrany polygonu v dusledku split event.

35


Obr. 4.7: Ukazka urcenı bodu B pri split event

Algoritmus pro vypocet straight skeletonu nekonvexnıho polygonu [20]:

1. Inicializace:

a) Vytvor LAV stejne jako v prıpade konvexnıho polygonu a uloz ho do

SLAV.

b) Spocıtej bisektory pro jednotlive vrcholy stejne jako v prıpade konvexnıho

polygonu.

c) Spocıtej prusecıky s bisektory predchazejıcıch a nasledujıcıch vrcholu

stejne jako v prıpade konvexnıho polygonu a pro nekonvexnı vrcholy

spocıtej navıc potencialnı prusecıky s”protilehlou“ hranou. Nejblizsı pru-

secık z techto trı uloz do prioritnı fronty vcetne jeho typu, edge event nebo

split event.

36


2. Dokud prioritnı fronta nenı prazdna:

a) Vezmi prusecık I na zacatku prioritnı fronty stejne jako v prıpade kon-

vexnıho polygonu. Pokud jde o prusecık typu edge event, pokracuj kroky

2b az 2g algoritmu pro konvexnı polygony. V opacnem prıpade (prusecık

typu split event) pokracuj v tomto algoritmu.

b) Pokud prusecık ukazuje na vrchol oznaceny jako zpracovany, preskoc ke

kroku 2 jako v prıpade konvexnıho polygonu.

c) Pridej do straight skeletonu hranu V I, pricemz V je vrchol, na ktery

ukazuje prusecık I.

d) Modifikuj strukturu SLAV:

– Oznac vrchol V za zpracovany.

– Vytvor dva nove vrcholy V1 a V2 o stejnych souradnicıch jako ma

prusecık I.

– Najdi ve SLAV protilehlou hranu.

– Rozdel dany LAV na dve casti a vloz oba nove vrcholy do SLAV.

Vrchol V1 bude zapojen mezi predchudce vrcholu V a vrchol, ktery

je koncovym bodem protilehle hrany. Vrchol V2 bude zapojen mezi

naslednıka vrcholu V a vrchol, ktery je pocatecnım bodem protilehle

hrany.

– Propoj nove vrcholy V1 a V2 s prıslusnymi hranami.

e) Pro vrchol V1 a V2:

– Spocıtej nove osy uhlu sevreneho hranami, ktere jsou napojene na

dany vrchol.

– Spocıtej prusecıky techto bisektoru s bisektory, jez zacınajı v sou-

sednıch vrcholech v ramci jednotlivych LAV, stejnym zpusobem jako

v kroku 1c.

– Mohou se objevit prusecıky obou typu a nejblizsı z nich uloz do

prioritnı fronty.

37


Vyse uvedeny algoritmus pro nalezenı straight skeletonu nekonvexnıho polygonu

umı vypocıtat take straight skeleton polygonu s dırami, pokud jsou hranice polygonu

a der ulozeny do SLAV v samostatnych LAV se spravnou orientacı tak, aby se

vnitrek polygonu nachazel vzdy nalevo od jeho hran [20]. Vrcholy vnejsı hranice

polygonu jsou tedy orientovany proti smeru hodinovych rucicek a vrcholy der po

smeru hodinovych rucicek.

Implementace algoritmu pro vypocet straight skeletonu nekonvexnıho polygonu

s dırami, jak ji navrhli Felkel a Obdrzalek [20], ma casovou slozitost O(nm+n log n),

kde n oznacuje pocet konvexnıch vrcholu polygonu a m pocet nekonvexnıch. Nejvıce

casu pri vypoctu zabıra testovanı nekonvexnıch vrcholu a nakladanı s moznymi split

events. Obecne je slozitost algoritmu O(n2) (O(mn)) [20].

38


4.1.3 Datove struktury pouzite v implementaci algoritmu

V teto kapitole jsou popsany nejdulezitejsı datove struktury pouzite v imple-

mentaci algoritmu pro vypocet straight skeletonu v programovacım jazyce C++ od

autoru Felkel a Obdrzalek [20].

Struktura Vertex

Vertex, vrchol puvodnıho nebo smrsteneho polygonu, je definovan ukazatelem

na bod (point), na jehoz souradnicıch se nachazı, ukazatelem na jeho predchudce

(prev) a nasledovnıka (next) v polygonu, bisektorem (axis), kterym z nej vychazı,

levou (leftLine) a pravou (rightLine) prilehlou hranou (axis je osou uhlu jimi

sevreneho), ukazatelem na vrchol (higher) vznikly pri zaniku tohoto vrcholu, uka-

zatelem na vrcholy (leftVertex, rightVertex), jejichz zanikem tento vrchol vznikl,

ukazatelem na sousednı vrcholy v LAV (prevVertex, nextVertex), prıznakem (done),

zda uz byl vrchol zpracovan, identifikatorem (ID) a ukazatelem na hrany skele-

tonu (leftSkeletonLine, rightSkeletonLine, advancingSkeletonLine), kterych

je soucastı.

struct Vertex

{

Vertex (void) : ID (-1) { } // Bezparametricky konstruktor kvuli STL

Vertex (const Point &p, const Point &prev = Point (),

const Point &next = Point ())

: point (p), axis (angleAxis (p, prev, next)),

leftLine (p, prev), rightLine (p, next),

higher (NULL),

leftVertex (NULL), rightVertex (NULL),

nextVertex (NULL), prevVertex (NULL),

done (false), ID (-1),

leftSkeletonLine (NULL), rightSkeletonLine (NULL),

advancingSkeletonLine (NULL) { }

Vertex (const Point &p, Vertex &left, Vertex &right);

Vertex *highest (void) { return higher ? higher -> highest () : this; }

bool atContour (void) const {return leftVertex == this && rightVertex == this;}

bool operator == (const Vertex &v) const { return point == v.point; }

39


// kvuli STL, jinak se nepouziva

bool operator < (const Vertex &) const { assert (false); return false; }

// data

Point point; // souradnice vrcholu

Ray axis; // bisektor

Ray leftLine, rightLine; // leva a prava hranicni usecka, axis je jejich osou

Vertex *leftVertex, *rightVertex; // 2 vrcholy, jejich zaniknutim vzikl tento

Vertex *nextVertex, *prevVertex; // vrchol sousedici v LAV

Vertex *higher; // vrchol vznikly pri zaniknuti tohoto

bool done; // priznak aktivity

int ID; // cislo automaticky pridelovane pri vkladani do LAV

// Pouzivano pri konstrukci kostry z okridlenych hran

SkeletonLine *leftSkeletonLine, *rightSkeletonLine, *advancingSkeletonLine;

};

Struktura VertexList

Struktura VertexList prestavuje SLAV a je definovana jako seznam (list) objektu typu

Vertex. Jednotlive LAV v nı zahrnute jsou udrzovane pomocı ukazatelu nextVertex a prevVertex.

class VertexList : public list <Vertex>

{

public:

VertexList (void) { }

iterator prev (const iterator &i)

// => cyklicky

{iterator tmp (i); if (tmp == begin ()) tmp = end (); tmp --; return tmp;}

// => cyklicky

iterator next (const iterator &i)

{iterator tmp (i); tmp ++; if (tmp == end ()) tmp = begin (); return tmp;}

void push_back (const Vertex& x)

{

assert (x.prevVertex == NULL ||

facingTowards (x.leftLine, x.prevVertex -> rightLine));

assert (x.nextVertex == NULL ||

facingTowards (x.rightLine, x.nextVertex -> leftLine));

((Vertex &)x).ID = size (); // automaticke cislovani

40


list <Vertex> :: push_back (x);

}

};

Struktury SkeletonLine a SkeletonPoint

Hrana skeleton (SkeletonLine) je urcena pocatecnım a koncovym bodem typu (SkeletonPoint).

SkeletonPoint je definovan ukazatelem na vrchol (vertex) a levou (left) a pravou (right) hra-

nou skeletonu, ktere z nej vychazı. SkeletonLine je definovana pocatecnım (lower) a koncovym bo-

dem (higher) a identifikatorem (ID). Pro ucely teto prace byla definice SkeletonLine rozsırena o

stav linie (status), ktery muze nabyvat hodnot EAR\_EDGE, FRESH, OPEN, CLOSED a B\_TREE, o uka-

zatele na predchudce (p), jednoho naslednıka (suc\_l) a druheho naslednıka (suc\_r), vzdalenost

od korene (d), rodice v binarnım stromu (par), delku vetve v binarnım stromu (length), vahu

vetve (weight) a prıznak (processed), zda byla zpracovana.

struct SkeletonLine

{

SkeletonLine (void) : ID (-1) { }

SkeletonLine (const Vertex &l, const Vertex &h) : lower (l), higher (h),

ID (-1), processed (false),

status (EAR_EDGE), p (NULL), d (-1), suc_l(NULL), suc_r(NULL), par (NULL),

length (dist(lower.vertex->point,higher.vertex->point)), weight (-1) { }

// Jen pro ladeni

operator Segment (void) { return Segment (lower.vertex -> point,

higher.vertex -> point); }

struct SkeletonPoint

{

SkeletonPoint (const Vertex &v = Vertex (),

SkeletonLine *l = NULL, SkeletonLine *r = NULL)

: vertex (&v), left (l), right (r) { }

const Vertex *vertex; // ukazatel na vrchol (obsahuje souradnice)

SkeletonLine *left, *right; // kridla

int leftID (void) const { if (!left) return -1; return left -> ID; }

int rightID (void) const { if (!right) return -1; return right -> ID; }

int vertexID (void) const { if (!vertex) return -1; return vertex -> ID; }

} lower, higher; // dva body typu SkeletonPoint

bool operator == (const SkeletonLine &s) const

41


{ return higher.vertex -> ID == s.higher.vertex -> ID

&& lower.vertex -> ID == s.lower.vertex -> ID ; }

// kvuli STL, jinak se nepouziva

bool operator < (const SkeletonLine &) const { assert (false); return false; }

int ID; // Cislo automaticky pridelovane pri vkladani do kostry

// MODIFICATION FOR BFS

int d;

SkeletonLine *p;

status_types status;

SkeletonLine *suc_l;

SkeletonLine *suc_r;

// MODIFICATION FOR BINARY TREE

SkeletonLine *par;

double length;

double weight;

bool processed;

};

Struktura Skeleton

Struktura Skeleton prestavuje mnozinu hran straight skeletonu a je definovana jako seznam

(list) objektu typu SkeletonLine.

class Skeleton : public list <SkeletonLine>

{

public:

void push_back (const SkeletonLine &x)

{

((SkeletonLine &)x).ID = size (); // automaticke cislovani

list <SkeletonLine> :: push_back (x);

}

};

42


4.2 Modifikace algoritmu pro vypocet

straight skeletonu

Modifikace struktury straight skeleton vytvorena v teto praci, vklada do kazdeho nekonvexnıho

vrcholu polygonu, na jehoz zaklade se skeleton vytvarı, jednu hranu nulove delky. Souradnice jejıho

pocatecnıho a koncoveho vrcholu jsou shodne se souradnicemi nekonvexnıho vrcholu, do ktereho

je vkladana, a je kolma na osu nekonvexnıho uhlu pri danem vrcholu. Formalnejsı vyjadrenı:

Necht’ {V1, V2, . . . , Vn} oznacuje vrcholy polygonu P a necht’ k = {0, 1} oznacuje pocet vr-

cholu pridanych do polygonu ve vrcholu vi. Pokud Vi je konvexnı vrchol P , pak ki = 0, a pokud

je Vi nekonvexnı vrchol, pak ki = 1. Necht’ je Pκ(0) polygon vznikly z P nahrazenım kazdeho

nekonvexnıho vrcholu Vi 2 identickymi vrcholy, koncovymi body 1 hrany o nulove delce prıslusne

vrcholu Vi. Smer kazde skryte hrany je voleny tak, ze nekonvexnı vrchol Vi polygonu P je v novem

polygonu Pκ(0) nahrazen 2 vrcholy se shodnym vnitrnım uhlem.

Obr. 4.8: Ukazka principu vlozenı hrany nulove delce

Pro vypocet modifikovaneho straight skeletonu byla pouzita implementace algoritmu pro urcenı

straight skeletonu v programovacım jazyce C++, kterou vytvorili Felkel a Obdrzalek [20], do-

plnena o funkci pro vlozenı nulove hrany do nekonvexnıho vrcholu, jez upravuje kruhovy seznam

aktivnıch vrcholu LAV hned po jeho inicializaci, nez dojde k vytvorenı prioritnı fronty prusecıku.

LAV pred modifikacı umoznuje identifikovat nekonvexnı vrcholy polygonu a zjistit bisektory z nich

43


vychazejıcı, ktere jsou nezbytne pro urcenı smeru vkladane nulove hrany a vypocet novych bisek-

toru.

Algoritmus pro vlozenı nulove hrany do nekonvexnıho vrcholu

Pro kazdy vrchol Vi ve SLAV:

1. Urci uhel α pri vrcholu Vi.

2. Pokud je α konvexnı uhel, jdi na dalsı vrchol. V opacnem prıpade (α je nekonvexnı uhel)

pokracuj v tomto algoritmu.

3. Vytvor novy vrchol V0 o souradnicıch shodnych s Vi.

4. Nastav predchudce V0 rovno Vi−1 (predchudce Vi)

5. Nastav naslednıka V0 rovno Vi

6. Vypocıtej orientovany uhel ϕr, ktery svıra prımka prochazejıcı nulovou hranou V0Vi a prvnı

souradnicova osa. Necht’ je β uhel, ktery svıra osa uhlu pri vrcholu Vi (bisektor bi) a prvnı

souradnicova osa, potom ϕr = β– π2 .

7. Vloz V0 do SLAV pred Vi a vypocıtej z nej vychazejıcı bisektor b0 (osa uhlu sevreneho

hranami Vi−1V0 a V0Vi)

8. Nastav predchudce Vi rovno V0.

9. Vypocıtej orientovany uhel ϕl, ktery svıra prımka prochazejıcı nulovou hranou ViV0 a prvnı

souradnicova osa. Necht’ je β uhel, ktery svıra osa uhlu pri vrcholu Vi (bisektor bi) a prvnı

souradnicova osa, potom ϕl = β + π2 .

10. Vypocıtej novy bisektor bi pro vrchol Vi (osa uhlu sevreneho hranami V0Vi a ViVi+1)

Implementace funkce pro vlozenı nulove hrany do nekonvexnıho vrcholu

// Add zero edge to reflex vertices

void addZeroEdge (VertexList &vl)

{

// Initiation of ID of a vertex in the vertex list

int id_count = 0;

VertexList :: iterator i;

// For all vertices in the vertex list

44


for (i = vl.begin (); i != vl.end (); i++)

{

// Compute an angle at vertex

double av = (*i).leftLine.angle - (*i).rightLine.angle;

normalizeAngle (av);

// If the angle is reflex

if (av < 0.0)

{

// Create a new vertex with the same coordinates

// as the vetrex with reflex angle

Vertex zero((*i).point,(*i).prevVertex->point,(*i).point);

// Set its previous vertex same as

// the previous vertex of the vetrex with reflex angle

zero.prevVertex = (*i).prevVertex;

// Set its next, left and right vertex to

// the vetrex with reflex angle

zero.nextVertex = &(*i);

zero.leftVertex = &(*i);

zero.rightVertex = &(*i);

// Compute a right line angle - it is perpendicular to axis angle

double k = (*i).axis.angle - M_PI / 2;

normalizeAngle(k);

// Set a right line angle to the new vertex

zero.rightLine.angle = k;

// Compute an axis angle

double left = zero.leftLine.angle;

if (left < zero.rightLine.angle) left = left - 2*M_PI;

double axis = (left + zero.rightLine.angle) / 2;

normalizeAngle(axis);

45


// Set an axis angle to the new vertex

zero.axis.angle = axis;

// Set the new vertex ID

zero.ID = id_count;

// Increase the ID

id_count++;

// Insert a first vertex of a zero edge to the vertex list

vl.insert(i,zero);

// Decrease the iterator to get to the new vertex

--i;

// Connect its precedessor to the vertex

(*vl.prev(i)).nextVertex = &(*i);

// Increase the iterator to get to the last vertex of the zero edge,

// the original vertex with reflex angle

++i;

// Connect it to the newly inserted vertex

(*i).prevVertex = &(*vl.prev(i));

// Compute a left line angle - it is perpendicular to axis angle

double l = (*i).axis.angle + M_PI / 2;

normalizeAngle(l);

// Set the new left line angle to the vertex

(*i).leftLine.angle = l;

// Compute an axis angle

double right = (*i).rightLine.angle;

if ((*i).leftLine.angle < right)

(*i).leftLine.angle = (*i).leftLine.angle - 2*M_PI;

double axis_2 = ((*i).leftLine.angle + right) / 2;

46


normalizeAngle(axis_2);

// Set the new axis angle to the vertex

(*i).axis.angle = axis_2;

}

// Set new ID to a vertex

(*i).ID = id_count;

// Increase the ID

id_count++;

}

}

47

CVUT v Praze 5. EXTRAKCE LINIE ZE SKELETONU

5 Extrakce linie ze skeletonu

Aby mohl byt modifikovany straight skeleton popsany v predchozı kapitole vyuzit pro ge-

neralizaci vodstva technikou redukce prostorove dimenze, musı se zjednodusit na nerozvetvenou

lomenou caru s jednım pocatecnım a jednım koncovym bodem, ktera by mela vhodne aproximovat

osu generalizovaneho vodnıho toku.

Pri extrakci linie z modifikovaneho straight skeletonu muzeme vyuzıt jeho vlastnostı jako grafu.

Nedegenerovany straight skeleton polygonu bez der predstavuje binarnı strom tvoreny n–2 uzly a

2n–3 hranami [12]. Toto tvrzenı platı i pro modifikovany straight skeleton, jak dokazujı Tanase a

Veltkamp [21]:

”Pokud ma kazdy nekonvexnı vrchol vj s vnitrnım uhlem αj ≥ 3π

2 vlozenu alespon jednu skry-

tou hranu, pak linear axis Lκ(P ) je acyklicky graf.“ [21]

Pro ucely teto prace extrakcie linie z modifikovaneho straight skeletonu probıha ve trech

krocıch. Nejdrıve se skeleton prohleda do sırky a pote se vytvorı jeho zjednodusena grafova re-

prezentace jako binarnıho stromu, z nejz jsou postupne orezavany listy, dokud se nezıska jedina,

nerozvetvena linie. Postup je podrobneji popsan v nasledujıcıch kapitolach.

Obr. 5.1: Prıklad modifikovaneho straight skeletonu, z nejz bude extrahovana linie

48


5.1 Prohledavanı do sırky

Prohledanı grafu je systematicka prohlıdka vsech uzlu a hran [22]. Jednu z jeho zakladnıch va-

riant predstavuje prohledavanı do sırky (BFS – breadth-first search). Cılem algoritmu je pro zadany

graf G a jeho libovolny uzel s nalezt vsechny uzly, ktere jsou dosazitelne z uzlu s. Pri prohledavanı

do sırky se hranice mezi objevenymi a dosud neobjevenymi uzly rovnomerne posouva po cele sve

sırce, coz znamena, ze vsechny uzly ve vzdalenosti k od vychozıho uzlu s budou objeveny drıv nez

jakykoli uzel ve vzdalenosti k + 1. Protoze se behem prohledavanı zaroven stanovuje vzdalenost

kazdeho uzlu od uzlu s, zıska se jako vedlejsı produkt tohoto postupu strom nejkratsıch cest z uzlu

s do vsech z nej dosazitelnych uzlu.

Na zacatku algoritmu jsou vsechny uzly grafu oznaceny jako neobjevene (FRESH) krome uzlu s,

ktery je oznacen jako otevreny (OPEN). Otevrene uzly se ukladajı fronty. Z fronty se vzdy vezme

prvnı uzel a vsechny jeho dosud neobjevene sousednı uzly se otevrou a pridajı do fronty. Uzel,

jehoz vsichni sousedi uz byli prozkoumani, se uzavre (CLOSED) a odebere z fronty. Kazdy uzel je

objeven prave jednou a ma tedy jedineho predchudce.

Obr. 5.2: Modifikovany straight skeleton bez hran vychazejıcıch z vrcholu polygonu

Pro ucely teto prace hrany modifikovaneho straight skeletonu reprezentujı uzly grafu, protoze

pri tvorbe skeletonu algoritmem od autoru Felkel a Obdrzalek [20], jsou jim nastaveny informace

o sousednıch hranach, cehoz se vyuzıva v algoritmu pro prohledavanı do sırky. Z grafu jsou vy-

louceny hrany skeletonu, ktere vychazı z jeho vrcholu, a jsou oznaceny jako EAR EDGE. Protoze

49


je nedegenerovany modifikovany straight skeleton polygonu bez der binarnım stromem, muze mıt

maximalne dva naslednıky. Skeleton je v prubehu extrakce linie prohledavan vıcekrat, a proto se

uvazuje, ze vstupem algoritmu pro prohledavanı do sırky muze byt i uz drıve prohledany graf.

Skeleton musı byt spojity graf, pokud je tedy v prubehu BFS zjisteno, ze skeleton je nespojity,

prohledavanı se ukoncı a zıskany skeleton se oznacı za neplatny.

Algoritmus prohledavanı modifikovaneho straight skeletonu do sırky

BFS (skeleton S, pocatecnı vrchol s)

1. Pro vsechny hrany v S:

a) Pokud je stav hrany CLOSED,

– zmen jej na FRESH,

– odeber jı predchudce,

– odeber jı jednoho naslednıka,

– odeber jı druheho naslednıka,

– vynuluj jı vzdalenost od korene stromu.

b) Pokud hrana zacına v s,

– zapamatuj si ji jako hranu r (koren stromu).

2. Zmen stav r na OPEN.

3. Zmen vzdalenost r od korene na 0.

4. Pridej r do fronty.

5. Dokud nenı fronta prazdna:

a) Vezmi prvnı hranu e z fronty.

b) Pro vsechny sousednı hrany v hrany e, ktere majı stav FRESH:

– Zmen stav v na OPEN.

– Nastav v predchudce rovno e (p(v) = e).

– Nastav e hranu v jako naslednıka. (suc(e) = v).

– Nastav v vzdalenost rovno vzdalenosti e+ 1 (d(v) = d(e) + 1).

– Uloz v do fronty.

c) Odeber e z fronty.

d) Zmen stav e na CLOSED.

50


Obr. 5.3: Ilustrace principu prohledavanı do sırky (1) - vychozı stav

Obr. 5.4: Ilustrace principu prohledavanı do sırky (2)

51




52



Implementace funkce pro prohledavanı skeletonu do sırky

// Broad first search of a graph of a skeleton (only interior edges)

vector <SkeletonLine> SkeletToLine::bfs

(vector <SkeletonLine> &line_vec, int start_id)

{

// An input graph to be searched

vector <SkeletonLine> graph = line_vec;

// Initiation of the ID of a root

int first_id = -1;

// For all skeleton edges

for (int i = 0; i < graph.size(); i++)

{

// If the edge is CLOSED

if (graph[i].status == 3)

{

// Turn it to FRESH

graph[i].status = FRESH;

53


// Set its parent a successors to NULL

graph[i].p = NULL;

graph[i].suc_l = NULL;

graph[i].suc_r = NULL;

// Set its distance from a root to -1

graph[i].d = -1;

}

// Find a line with a lower vertex ID equal to the start ID

if (graph[i].lower.vertexID() == start_id)

{

// Set the ID of the root

first_id = graph[i].ID;

}

}

// Open the root edge

graph[first_id].status = OPEN;

// Set the distance of root edge to 0

graph[first_id].d = 0;

// A queue of open edges

queue <SkeletonLine*> bfs_queue;

bfs_queue.push(&graph[first_id]);

// Do until the queue is empty

while (!bfs_queue.empty())

{

// The first line in the queue

SkeletonLine* line = bfs_queue.front();

// If the line have a higher left neighbour

if (line->higher.left)

{

54


SkeletonLine* higher_left = &graph[line->higher.left->ID];

// And the neighbour is FRESH

if (higher_left->status == 1)

{

// Set its status to OPEN, set its distance, parent

higher_left->status = OPEN;

higher_left->d = line->d + 1;

higher_left->p = line;

// Add it to the queue

bfs_queue.push(higher_left);

// Set it as the successor of its parent

line->suc_l = higher_left;

}

}

// Graph is unconnected

else

{

graph.clear();

return graph;

}

// If the line have a higher right neighbour

if (line->higher.right)

{

SkeletonLine* higher_right = &graph[line->higher.right->ID];


if (higher_right->status == 1)

{


higher_right->status = OPEN;

higher_right->d = line->d + 1;

higher_right->p = line;

55



bfs_queue.push(higher_right);


line->suc_r = higher_right;

}

}


else

{

graph.clear();

return graph;

}

// If the line have a lower left neighbour

if (line->lower.left)

{

SkeletonLine* lower_left = &graph[line->lower.left->ID];


if (lower_left->status == 1)

{


lower_left->status = OPEN;

lower_left->d = line->d + 1;

lower_left->p = line;


bfs_queue.push(lower_left);


line->suc_l = lower_left;

}

}

56



else

{

graph.clear();

return graph;

}

// If the line have a lower right neighbour

if (line->lower.right)

{

SkeletonLine* lower_right = &graph[line->lower.right->ID];


if (lower_right->status == 1)

{


lower_right->status = OPEN;

lower_right->d = line->d + 1;

lower_right->p = line;


bfs_queue.push(lower_right);


line->suc_r = lower_right;

}

}


else

{

graph.clear();

return graph;

}

// Set the line status to closed

line->status = CLOSED;

57


// Remove the line from the queue

bfs_queue.pop();

}

// Return searched graph

return graph;

}

58


5.2 Reprezentace skeletonu jako binarnıho stromu

Jak uz bylo uvedeno, nedegenerovany modifikovany straight skeleton polygonu bez der je

binarnım stromem. Obsahuje tedy pouze vrcholy prvnıho az tretıho stupne. Jeho graf muzeme

pro ucely extrakce linie za skeletonu zjednodusit tak, ze propojenı kombinacı vrcholu prvnıho a

tretıho stupne pres vrcholy druheho stupne nahradıme prımym spojenım. Tımto zpusobem se graf

skeletonu obvykle vyrazne zjednodusı, cımz se i snızı doba trvanı nasledujıcıch vypoctu.

Z grafu jsou opet vylouceny hrany skeletonu, ktere vychazı z jeho vrcholu, oznacene jako

EAR EDGE. Za koren vznikleho zjednoduseneho binarnıho stromu muzeme zvolit jakykoli vr-

chol prvnıho stupne, v teto praci se pouzil prvnı vrchol vlozeny do skeletonu, ktery zaroven nenı

vrcholem polygonu. Zjednodusenı grafu skeletonu provadı rekurzivnı algoritmus pro nalezenı jed-

notlivych vetvı noveho binarnıho stromu. Dulezite je spravne urcenı pocatecnıho a koncoveho bodu

novych vetvı tak, aby na sebe navazovaly, protoze jednotlive hrany skeletonu se mohou dotykat

bud’ koncovym a pocatecnım bodem, nebo pocatecnımi body, anebo koncovymi body. Delka nove

vetve se urcı jako soucet delek jednotlivych hran, ktere nahrazuje.

Algoritmus nalezenı vetvı zjednoduseneho binarnıho stromu

findNode (hrana skeletonu e, predchazejıcı hrana binarnıho stromu bi−1, vytvareny binarnı stromB)

1. Nastav poslednı nalezenou hranu skeletonu t rovno e.

2. Nastav pocatecnı bod objevovane hrany binarnıho stromu bi rovno bodu, ktery majı spo-

lecny e a bi−1.

3. Zvys delku bi o delku t (l(bi) = l(t)).

4. Dokud hrana nema dva naslednıky:

a) Pokud ma jednoho naslednıka s:

– Nastav t rovno s.

– l(bi) = l(bi) + l(t).

b) Pokud nema zadneho naslednıka:

– Ukonci cyklus.

5. Nastav koncovy bod bi rovno bodu, ktery nemajı spolecny t a jejı predchudce.

6. Nastav bi rodice rovno bi−1 (par(bi) = bi−1).

7. Pokud ma t dva naslednıky:

a) findNode(sl(t), B, bi)

b) findNode(sr(t), B, bi)

59


Obr. 5.8: Prevod grafu skeletonu na zjednoduseny binarnı strom – krok 1


60




61


Implementace funkce pro nalezenı vetvı zjednoduseneho binarnıho stromu

void SkeletToLine::findNode

(SkeletonLine &line, vector<SkeletonLine> &btree, SkeletonLine &prev)

{

SkeletonLine edge;

// Initiation of a length of an edge

double sum_length = 0;

// Last found part of a binary tree edge

SkeletonLine* temp;

// Initiatin of last found part

temp = &line;

// Find the first node of a new edge

// (a point shared with parent has to be a lower point of a new edge)

if (temp->p)

{

if ((temp->p->lower.vertexID() == temp->lower.vertexID())

|| (temp->p->higher.vertexID() == temp->lower.vertexID()))

{

edge = *temp;

}

else

{

edge.ID = temp->ID;

edge.lower = temp->higher;

edge.higher = temp->lower;

}

}

else

{

edge = *temp;

}

62


// Increase the length of the edge

sum_length = sum_length + temp->length;

// Do until the last part of the edge has two successor

// (is a node of binary tree)

while (!((temp->suc_l) && (temp->suc_r)))

{

// Has a left successor

if (temp->suc_l)

{

// Change the last part

temp = temp->suc_l;



}

// Has a right successor

else if (temp->suc_r)

{

// Change the last part

temp = temp->suc_r;



}

// Has no succesor - is a leaf node

else if (!(temp->suc_l) && !(temp->suc_r))

{

break;

}

}

// Set the last point of the edge

// (a point not shared with parent has to be a higher point of a new edge)

63


if (temp->p)

{

if ((temp->p->lower.vertexID() == temp->lower.vertexID())

|| (temp->p->higher.vertexID() == temp->lower.vertexID()))

{

edge.higher = temp->higher;

}

else

{

edge.higher = temp->lower;

}

}

// Set the edge a status, ID and succcessors

edge.status = B_TREE;

edge.ID = btree.size();

edge.suc_l = NULL;

edge.suc_r = NULL;

// Set the edge a parent (par)

if (line.p)

{

edge.p = temp;

edge.par = &btree[prev.ID];

edge.d = prev.d + 1;

}

else

{

edge.par = NULL;

}

// Set the edge the length

edge.length = sum_length;

// Add the edge to the binary tree

64


btree.push_back(edge);

// If the new edge has successors

if ((temp->suc_l) && (temp->suc_r))

{

// Find a binary tree edges for its successors

findNode(*temp->suc_l, btree, edge);

findNode(*temp->suc_r, btree, edge);

}

}

65


5.3 Orezavanı zjednoduseneho binarnıho stromu

Jedinou linii je mozne zıskat postupnym orezavanı vetvı zjednoduseneho binarnıho stromu,

ktery reprezentuje modifikovany straight skeleton. Odrezana muze byt pouze vetev, ktera bud’

nema zadne nasledovnıky, list stromu, nebo nema rodice, koren stromu. Odrezana je vzdy vetev

s nejnizsı vahou. V teto praci se vaha urcuje pouze na zaklade normalizovane delky dane vetve, ale

je mozne zavest dalsı kriteria jako naprıklad plochu casti skeletonu, ktera je reprezentovana danou

vetvı [23]. Vyhodou postupneho odrezavanı je, ze tento postup lze zastavit v kterekoli fazi, takze

by bylo mozne stanovit naprıklad maximalnı delku orezavane hrany.

Nez se zacne orezavat, tak je nutne rodicum spravne nastavit nasledovnıky. Kazda hrana ma

prave dva nebo zadneho nasledovnıka a prave jednoho nebo, v prıpade korene, zadneho rodice.

Po odrezanı vetve je nutne upravit topologii zbyvajıcıch hran. Rodic odrezavane vetve se sloucı

s neodrezavanym naslednıkem daneho rodice. Pokud se odrezava koren stromu, otestujı se jeho

nasledovnıci. Kdyz oba nasledovnıci majı take nasledovnıky, nenı mozne koren odrezat, jelikoz by

strom prestal byt souvisly. Koren se proto pouze oznacı jako zpracovany, ale zustane rodicem svych

potomku. Kdyz alespon jeden z nasledovnıku odrezavaneho korene nema nasledovnıka, stane tento

nasledovnık novym korenem.

Obr. 5.12: Orezanı zjednoduseneho binarnıho stromu – krok 1

66





67




68


Algoritmus pro orezavanı binarnıho stromu

Pruning (zjednoduseny binarnı strom B)

1. Nastav vychozı pocet hran, ktere majı zustat v orezanem strome, m = 1.

2. Nastav vychozı pocet hran v orezavanem strome n = |B|.

3. Dokud je n > m:

a) Ze vsech nezpracovanych hran urci hodnotu nejdelsı delky lmax a nejmensı delky lmin.

b) Urci vahu w kazde hrany e:

– Pokud je hrana e zpracovana:

w = −1.

– Pokud hrana e nenı zpracovana:

w = l(e)−lmin

lmax−lmin.

c) Vyber hranu edel s nejmensı nezapornou vahou.

d) Pokud ma edel rodice pdel:

– Pokud sl(pdel) 6= edel:

Spoj pdel s sl(pdel).

Oznac edel za zpracovanou.

Oznac sl(pdel) za zpracovaneho.

– Pokud sr(pdel) 6= edel:

Spoj pdel s sr(pdel).


Oznac sl(pdel) za zpracovaneho.

– n = n− 2.

d) Pokud edel nema rodice:

– Pokud sl(edel) ma nasledovnıky a sr(edel) ma nasledovnıky:


Zmen status edel na EAR EDGE.

n = n− 1.

m = m+ 1.

– Pokud sr(edel) nema nasledovnıky:

Spoj sl(edel) s sr(edel).

Nastav, ze sl(edel) nema zadneho rodice (novy koren).

69



Oznac sr(edel) za zpracovaneho.

n = n− 2.

– Pokud sl(edel) nema nasledovnıky:

Spoj sr(edel) s sl(edel).

Nastav, ze sr(edel) nema zadneho rodice (novy koren).


Oznac sl(edel) za zpracovaneho.

n = n− 2.

70


Implementace funkce pro orezavanı binarnıho stromu

vector <SkeletonLine> SkeletToLine::pruning (vector <SkeletonLine> &btree)

{

// Connect succestors to its parents

for (int i = 0; i < btree.size(); i++)

{

SkeletonLine l = btree[i];

if (l.par)

{

if (!(btree[l.par->ID].suc_l))

{

btree[l.par->ID].suc_l = &btree[i];

}

else if (btree[l.par->ID].suc_l)

{

btree[l.par->ID].suc_r = &btree[i];

}

}

}

// Initiation of the number of binary tree edges left after pruning

int m = 1;

// Initiation of the number of binary tree edges before pruning

int n = btree.size();

while (n > m)

{

// Sort edges using their length

sort (btree.begin(), btree.end(), SkeletToLine::longer);

// Initiation of maximal length, minimal length and index

double min_l = -1;

double max_l = -1;

int index = 0;

71


// Go from the begining of the sorted vector

// until the first unprocessed (unpruned) leaf edge or root edge is found

// and set its length as minimum

while (min_l < 0)

{

if (!btree[index].processed)

{

if (!btree[index].par)

{

min_l = btree[index].length;

}

else if (!btree[index].suc_l)

{

min_l = btree[index].length;

}

else

{

index++;

}

}

else

{

index++;

}

}

// Invalid skeleton

if (min_l == INFINITY)

{

vector <SkeletonLine> empty;

empty.clear();

return empty;

}

72


// Set the index to the end of the vector

index = btree.size() - 1;

// Go from the end of the sorted vector

// until the first unprocessed (unpruned) leaf edge or root edge is found

// and set its length as maximum

while (max_l < 0)

{

if (!btree[index].processed)

{

if (!btree[index].par)

{

max_l = btree[index].length;

}

else if (!btree[index].suc_l)

{

max_l = btree[index].length;

}

else

{

index--;

}

}

else

{

index--;

}

}

// Invalid skeleton

if (max_l == INFINITY)

{

vector <SkeletonLine> empty;

empty.clear();

73


return empty;

}

// Set diffenrence between minimal and maximal length

double dl = max_l - min_l;

// Set a weight of each edge


{

// Compute weight for unprocessed edge

if (!btree[i].processed)

{

btree[i].weight = (btree[i].length - min_l)/dl;

}

// Set weight of processed edge to -1

else

{

btree[i].weight = -1;

}

}

// Sort edges using their weight

sort (btree.begin(), btree.end(), SkeletToLine::weight);

// Inititation of ID of an edge to be pruned

int del = -1;

// Find the unprocessed edge with minimal weight


{

if (btree[i].weight >= 0)

{

// Set an ID of the edge with minimal weight to be pruned

del = btree[i].ID;

break;

}

74


}

// Sort edges using their ID

sort (btree.begin(), btree.end(), SkeletToLine::sort_id);

// Preserve topology, if the pruned edge has a parent

if (btree[del].par)

{

// A parent of the pruned edge

SkeletonLine* par = &btree[btree[del].par->ID];

// A left successor of the parent of the pruned edge

SkeletonLine* suc_l = &btree[par->suc_l->ID];

// A right successor of the parent the pruned edge

SkeletonLine* suc_r = &btree[par->suc_r->ID];

// Merge the parent with the other edge than the pruned edge

if (suc_l->ID != del)

{

// Set both successor as processed

btree[del].processed = true;

btree[suc_l->ID].processed = true;

// Set a new length to a parent

par->length = par->length + suc_l->length;

// Set a correct first and last vertex of merged edge

if (par->lower.vertexID() == suc_l->lower.vertexID())

{

par->lower = suc_l->higher;

}

else if (par->lower.vertexID() == suc_l->higher.vertexID())

{

par->lower = suc_l->lower;

}

75


else if (par->higher.vertexID() == suc_l->lower.vertexID())

{

par->higher = suc_l->higher;

}

else if (par->higher.vertexID() == suc_l->higher.vertexID())

{

par->higher = suc_l->lower;

}

// Set a new successor to the parent

// if the merged successor has a successor

if (suc_l->suc_l)

{

par->suc_l = suc_l->suc_l;

suc_l->suc_l->par = par;

}

else

{

par->suc_l = NULL;

}



if (suc_l->suc_r)

{

par->suc_r = suc_l->suc_r;

suc_l->suc_r->par = par;

}

else

{

par->suc_r = NULL;

}

}

76


// Merge the parent with the other edge than the pruned edge

else if (suc_r->ID != del)

{

// Set both successor as processed


btree[suc_r->ID].processed = true;

// Set a new length to a parent

par->length = par->length + suc_r->length;

// Set a correct first and last vertex of merged edge

if (par->lower.vertexID() == suc_r->lower.vertexID())

{

par->lower = suc_r->higher;

}

else if (par->lower.vertexID() == suc_r->higher.vertexID())

{

par->lower = suc_r->lower;

}

else if (par->higher.vertexID() == suc_r->lower.vertexID())

{

par->higher = suc_r->higher;

}

else if (par->higher.vertexID() == suc_r->higher.vertexID())

{

par->higher = suc_r->lower;

}



if (suc_r->suc_l)

{

par->suc_l = suc_r->suc_l;

77


suc_r->suc_l->par = par;

}

else

{

par->suc_l = NULL;

}



if (suc_r->suc_r)

{

par->suc_r = suc_r->suc_r;

suc_r->suc_r->par = par;

}

else

{

par->suc_r = NULL;

}

}

// Decrease the number of active edges

n = n - 2;

}

// Preserve topology, if the pruned edge is a root

else

{

// A left successor of the root

SkeletonLine* suc_l = &btree[btree[del].suc_l->ID];

// A right successor of the root

SkeletonLine* suc_r = &btree[btree[del].suc_r->ID];

// If the root successors have succesors

if (suc_l->suc_l && suc_r->suc_l)

{

// Set the root as processed

78



// Set the root status to EAR_EDGE

btree[del].status = EAR_EDGE;

// Set successors parents as the root to keep them connected

suc_l->par = &btree[del];

suc_r->par = &btree[del];

// Decrease a number of active edges

n = n - 1;

// Increase the number of binary tree edges left after pruning

// because successors form a new edge

// even though there are two edges in the vector

m = m + 1;

}

// A left successor is a new root

else if (!suc_r->suc_l)

{

// Set the root and its right successor as processed


btree[suc_r->ID].processed = true;

// Make a new root from the left successor

suc_l->par = NULL;

// Connect the left successor to the right successor

if (suc_l->lower.vertexID() == suc_r->lower.vertexID())

{

suc_l->lower = suc_r->higher;

}

else if (suc_l->lower.vertexID() == suc_r->higher.vertexID())

{

suc_l->lower = suc_r->lower;

79


}

if (suc_l->higher.vertexID() == suc_r->lower.vertexID())

{

suc_l->higher = suc_r->higher;

}

else if (suc_l->higher.vertexID() == suc_r->higher.vertexID())

{

suc_l->higher = suc_r->lower;

}

// Set a new length to the new root

suc_l->length = suc_l->length + suc_r->length;


n = n - 2;

}

// A right successor is a new root

else if (!suc_l->suc_l)

{

// Set the root and its left successor as processed


btree[suc_l->ID].processed = true;

// Make a new root from the left successor

suc_r->par = NULL;

// Connect the right successor to the left successor

if (suc_r->lower.vertexID() == suc_l->lower.vertexID())

{

suc_r->lower = suc_l->higher;

}

else if (suc_r->lower.vertexID() == suc_l->higher.vertexID())

80


{

suc_r->lower = suc_l->lower;

}

if (suc_r->higher.vertexID() == suc_l->lower.vertexID())

{

suc_r->higher = suc_l->higher;

}

else if (suc_r->higher.vertexID() == suc_l->higher.vertexID())

{

suc_r->higher = suc_l->lower;

}

// Set a new length to the new root

suc_r->length = suc_r->length + suc_l->length;


n = n - 2;

}

}

}

return btree;

}

81


5.4 Prevod extrahovane linie na seznam bodu

V binarnım strome zustanou po orezanı nejvyse dve hrany, u kterych zname pouze jejich

pocatecnı a koncovy bod. Abychom zjistili prubeh extrahovane linie, pouzijeme opet prohledavanı

do sırky. Algoritmem BFS prohledame grafovou reprezentaci skeletonu, pricemz vychozı hranou s

je takova hrana skeletonu, ktera zacına v pocatecnım bode analyzovane hrany orezaneho binarnıho

stromu a nevychazı z vrcholu polygonu.

V nove prohledanem skeletonu se nalezne hrana, ktera zacına v koncovem bode analyzovane

hrany orezaneho binarnıho stromu a nevychazı z vrcholu polygonu. Od teto hrany postupujeme po

rodicıch hran, dokud se nedostaneme zpatky do pocatecnıho bodu analyzovane hrany orezaneho

binarnıho stromu, a jednotlive lomove body linie se ukladajı do seznamu. Pokud je rodicem ana-

lyzovane hrany orezaneho binarnıho stromu odrezany koren, postupuje se po rodicıch hran, jen

dokud nebyl do seznamu lomovych bodu linie vlozen koncovy bod odrezaneho korene.

Obr. 5.18: Vysledna extrahovana linie

82


Algoritmus pro prevod hrany orezaneho binarnıho stromu na seznam

bodu

1. Pokud ma hrana orezaneho binarnıho stromu bi rodice (koren):

a) Nastav pocatecnı bod vs jako pocatecnı bod rodice bi

b) Nastav koncovou bod ve jako koncovy bod bi.

c) Nastav koncovy bod korene vr jako koncovy bod rodice bi.

2. Pokud nema hrana orezaneho binarnıho stromu bi rodice:

a) Nastav pocatecnı bod vs jako pocatecnı bod rodice bi

b) Nastav koncovou bod ve jako koncovy bod bi.

3. BFS(skeleton S, pocatecnı bod vs)

4. Pokud je ve poslednı vrchol pridany do skeletonu S:

a) Najdi v S hranu ee, ktera ma koncovy bod roven ve.

a) Pokud ve nema predchudce:

– Pridej do seznamu V pocatecnı a koncovy bod ve.

a) Pokud ve ma predchudce:

– Pridej do seznamu V pocatecnı a koncovy bod ve ve spravnem poradı.

– Dokud ma ee rodice nebo poslednı bod vlozeny do seznamu nenı roven vr:

ee = p(ee).

Pridej do seznamu V krajnı bod ee, ktery v nem jeste nenı.

5. Pokud nenı ve poslednı vrchol pridany do skeletonu S:

a) Najdi v S hranu ee, ktera ma pocatecnı bod roven ve.

a) Pokud ve nema predchudce:

– Pridej do seznamu V pocatecnı a koncovy bod ve.

a) Pokud ve ma predchudce:

– Pridej do seznamu V pocatecnı a koncovy bod ve ve spravnem poradı.

– Dokud ma ee rodice nebo poslednı bod vlozeny do seznamu nenı roven vr:

ee = p(ee).

Pridej do seznamu V krajnı bod ee, ktery v nem jeste nenı.

83


Implementace funkce pro prevod hrany orezaneho binarnıho stromu na

seznam bodu

vector <const Vertex*> SkeletToLine::lineToVertices

(SkeletonLine &pruned, vector <SkeletonLine> &graph, int vertex_list_size)

{

vector <const Vertex*> vert_vec;

// Initiation of the start and end ID of the derived skeleton line

int start_id = -1;

int end_id = -1;

// The first and last vertex of the derived skeleton line

int lower_id = pruned.lower.vertex->ID;

int higher_id = pruned.higher.vertex->ID;

// Initiation of the last vertex of root

// It is used in case that a root was pruned and there is no new root

int end_root = -1;

// The derived line has a parent - a pruned root

if (pruned.par)

{

// Set the first and last vertex of the pruned root

int par_lower_id = pruned.par->lower.vertex->ID;

int par_higher_id = pruned.par->higher.vertex->ID;

// Set topologically correctly start_id, end_id and end_root

if (par_lower_id == lower_id)

{

start_id = par_higher_id;

end_root = par_lower_id;

end_id = higher_id;

}

else if (par_lower_id == higher_id)

{

start_id = par_higher_id;

84


end_root = par_lower_id;

end_id = lower_id;

}

else if (par_higher_id == lower_id)

{

start_id = par_lower_id;

end_root = par_higher_id;

end_id = higher_id;

}

else if (par_higher_id == higher_id)

{

start_id = par_lower_id;

end_root = par_higher_id;

end_id = lower_id;

}

}

// Single derived line

else

{

// Set topologically correctly start_id and end_id

if (lower_id < higher_id)

{

start_id = lower_id;

end_id = higher_id;

}

else

{

start_id = higher_id;

end_id = lower_id;

}

}

// Do broad first search starting in vertex with start ID

85


vector <SkeletonLine> pruned_graph = SkeletToLine::bfs(graph,start_id);

// For all edges of the skeleton

for (int i = 0; i < pruned_graph.size(); i++)

{

// If the end vertex is the last vertex added to the skeleton

if (end_id == vertex_list_size - 1)

{

// Find an edge which higher vertex ID equal to end_id

// and its status is not EAR EDGE

if ((pruned_graph[i].higher.vertexID() == end_id)

&& (pruned_graph[i].status != 0))

{

// A skeleton edge

SkeletonLine* line = &pruned_graph[i];

// Clean a vector of vertices

vert_vec.clear();

// If the skeleton edge has no parent,

// then the derived line is a single line

if (!line->p)

{

// Add edge vertices to vector

vert_vec.push_back(line->lower.vertex);

vert_vec.push_back(line->higher.vertex);

}

// If the skeleton has a parent

else

{

// Add edge vertices to vector topologically correctly

if ((line->lower.vertexID() == line->p->lower.vertexID())

|| (line->lower.vertexID() == line->p->higher.vertexID()) )

{


86



}

else if ((line->higher.vertexID() == line->p->lower.vertexID())

|| (line->higher.vertexID() == line->p->higher.vertexID()))

{



}

// Go line by line, until the line has no parent

// or the ID of the last vertex in the vector

// is equal to the end_root

while (line->p && vert_vec.back()->ID != end_root)

{

// Process a parent of the edge

line = line->p;

// Add a new vertex to the vector

if (vert_vec.back()->ID == line->lower.vertexID())

{


}

else

{


}

}

}

}

}

// If the end vertex is not the last vertex added to the skeleton

else

{

87


// Find an edge which lower vertex ID equal to end_id

if (pruned_graph[i].lower.vertexID() == end_id)

{

// A skeleton edge

SkeletonLine* line = &pruned_graph[i];

// Clean vector of vertices

vert_vec.clear();

// Add edge vertices to vector topologically correctly

if ((line->lower.vertexID() == line->p->lower.vertexID())

|| (line->lower.vertexID() == line->p->higher.vertexID()) )

{



}

else if ((line->higher.vertexID() == line->p->lower.vertexID())

|| (line->higher.vertexID() == line->p->higher.vertexID()))

{



}

// Go line by line, until the line has no parent

// or the ID of the last vertex in the vector

// is equal to the end_root

while (line->p && vert_vec.back()->ID != end_root)

{

// Process a parent of the edge

line = line->p;

// Add a new vertex to the vector

if (vert_vec.back()->ID == line->lower.vertexID())

{


}

else

88


{


}

}

}

}

}

// Return vector of vertices

return vert_vec;

}

89

CVUT v Praze 6. PROGRAM COLLAPSE POLYGONS TO LINES

6 Program Collapse Polygons to Lines

V ramci teto diplomove prace vznikl program pro generalizaci polygonu technikou redukce

prostorove dimenze vyuzıvajıcı novou geometrickou strukturu straight skeleton. Implementace byla

provedena v programovacım jazyce C++ ve vyvojovem prostredı QT Creator [24] pod Ubuntu

12.04. Program byl zkompilovan take pod Windows 7 64-bit v prostredı Code Blocks [25]. Pro

zjednodusenı prace s tımto programem byla v prostredı Model Builder [26] pripravena sada nastroju

Collapse/Partial Collapse of Polygons pro export vstupnıch dat ze software ArcGIS [27], pro import

vystupu z programu do prostredı ArcGIS a pro vytvorenı castı polygonu, ktere nebudou prevedeny

na linie.

6.1 Predzpracovanı vstupnıch dat

Pro dosazenı lepsıch vysledku je vhodne nejdrıve provest predzpracovanı polygonu, ktere se

majı generalizovat. Algoritmus neumı pracovat s polygony s dırou, je tedy nutne dıry v polygonech

nejdrıve vyplnit (v ArcGIS napr. nastroj Eliminate Polygon Part) nebo polygony vhodne rozdelit.

Hranice polygonu by nemely obsahovat nadbytecne body, predevsım jde o vrcholy, jejichz vnitrnı

uhel se pohybuje okolo 180◦. Platı take, ze cım vıce vrcholu ma polygon, tım delsı je vypocet

vzhledem ke kvadraticke zavislosti doby behu algoritmu na poctu jeho vrcholu. Generalizaci hranic

polygonu lze provest napr. v ArcGIS pomocı nastroje Simplify Polygon s vhodne zvolenou metodou

generalizace a tolerance.

6.2 Vstupnı data

Program umı nacıst textovy soubor obsahujıcı vrcholy generalizovane mnoziny polygonu ve

specifickem formatu. Kazdy vrchol je v souboru zapsan na jednom radku a urcen souradnicı X,

souradnicı Y a cıslem polygonu, do ktereho nalezı. Tyto informace jsou oddeleny mezerou. Cıslo

polygonu musı byt unikatnı v ramci polygonu uvedenych v nahravanem souboru. Polygony jsou

v souboru zapsany za sebou vzestupne podle sveho cısla. Nejnizsı mozne cıslo polygonu je 1. Na

prvnım radku musı byt uvedeno nejvyssı cıslo polygonu v souboru. Poradı vrcholu muze byt po

smeru hodinovych rucicek nebo proti smeru hodinovych rucicek, ale je dulezite, aby uzivatel tuto

informaci znal. Souradnice vrcholu musı byt uvedeny s desetinnou teckou a ne desetinnou carkou.

Za topologickou spravnost vstupnıch dat zodpovıda uzivatel.

90


2

-738006.38000000 -1052972.06000000 1

-737994.19000000 -1052960.08000000 1

-737984.44000000 -1052955.69000000 1

-737970.87000000 -1052943.31000000 1

-737956.68000000 -1052939.96000000 1

-737943.40000000 -1052944.21990000 1

-737932.56000000 -1052950.11000000 1

-737919.39320000 -1052953.89400000 1

-738892.86510000 -1052109.64020000 2

-738890.61870000 -1052114.71080000 2

-738873.12000000 -1052101.44000000 2

-738848.56000000 -1052090.37000000 2

-738791.67000000 -1052068.63000000 2

-738778.53000000 -1052068.94000000 2

-738767.52000000 -1052074.63000000 2

Tab. 6.1: Ukazka vstupnıho textoveho souboru

6.2.1 Nastroj pro prıpravu vstupnıch dat

Prıpravu vstupnıch dat je mozne provest nastrojem Polygons to Points ze sady nastroju

Collapse/Partial Collapse of Polygons. Vrcholy polygonu ze zvolene polygonove vrstvy se prevedou

na body v bodove vrstve nastrojem Feature Vertices to Points a pote jsou exportovany do noveho

textoveho souboru se zadanym nazvem pomocı nastroje Export Feature Attribute to ASCII. Uzivatel

volı atributovy sloupec, ve kterem je pro kazdy vrchol uvedeno cıslo polygonu, do nejz nalezı. Takto

zıskany textovy soubor je jeste pred nactenım do programu nutne upravit. Na prvnı radek souboru

se doplnı nejvyssı cıslo polygonu a souradnice vrcholu musı byt uvedeny s desetinnou teckou.

91


Obr. 6.1: Uzivatelske rozhranı nastroje Polygons to Points

Obr. 6.2: Model nastroje Polygons to Points

92


Obr. 6.3: Popis nastroje Polygons to Points

93


6.3 Prace s programem

Collapse Polygons to Lines

Program lze spustit pomocı prıkazove radky ze souboru Collapse_Polygons_To_Lines.exe.

Aby program fungoval pod Windows 7 64 bit, je treba mıt ve slozce s programem ulozeny knihovny

libgcc\_s\_dw2-1.dll a libstdc++-6.dll.

Po spustenı programu musı uzivatel zadat cestu k textovemu souboru se vstupnımi daty. Po-

kud se data uspesne nacetla, musı uzivatel specifikovat, zda jsou vrcholy zpracovavanych polygonu

uvedeny v poradı proti smeru hodinovych rucicek tak, aby se vnitrek polygonu nachazel nalevo od

hranice polygonu. Stiskem klavesy n potvrzuje uzivatel, ze vrcholy jsou orientovany proti smeru

hodinovych rucicek. Pokud jsou orientovany po smeru hodinovych rucicek, musı uzivatel stisk-

nout klavesu y a vrcholy pak budou zpracovavany v obracenem poradı, protoze algoritmus pro

vypocet modifikovaneho straight skeletonu predpoklada orientaci proti smeru hodinovych rucicek.

Dale uzivatel uvede cestu k adresari, do ktereho se ulozı vystupnı soubory. Cestu je nutne uvest

vcetne lomıtka na konci.

COLLAPSE POLYGONS TO LINES

Insert a name of the text file with polygons:

G:\input.txt

Inverse order of vertices? y/n

y - Convert from clockwise to counter-clockwise

n - Input is already counter-clockwise

n

Insert a path for the output files (directory):

G:\output\

Processing polygon n. 1

Writing output skelet line to:

G:\output\skelet_1.txt

Tab. 6.2: Ukazka vystupu programu do konzole

94


Program behem sveho behu informuje, ktery polygon prave zpracovava, a kdyz najde linii

reprezentujıcı polygon, zapıse ji do textoveho souboru skelet cıslo polygonu. Pro kazdy polygon je

vytvoren soubor, kde jsou po radcıch zapsany souradnice x, souradnice y lomoveho bodu linie a

cıslo linie, do nız patrı.

Pokud se algoritmu nepodarı zkonstruovat pro dany polygon modifikovany straight skeleton,

program skoncı a uzivatel je upozornen. Pote je treba odstranit tento problematicky polygon ze

vstupnıho souboru a program spustit znova, aby se zpracovaly ostatnı polygony. Kdyz je behem

vypoctu zjisteno, ze zıskany skeleton je chybny, uzivatel je o tom informovan a pro dany polygon

se nevytvorı vystup, ale program pokracuje dal.

44.574990 140.477892 1

45.112180 140.583614 1

53.715241 136.848247 1

63.181750 129.535831 1

74.014398 115.721119 1

85.616545 109.631521 1

93.919947 111.445455 1

108.020923 121.890346 1

109.897384 122.140768 1

126.371956 103.527619 1

126.718273 101.976440 1

136.028048 90.432062 1

145.581358 94.178699 1

156.304859 105.968886 1

Tab. 6.3: Ukazka vystupnıho textoveho souboru

95


6.3.1 Implementace funkce pro nacıtanı polygonu

Funkce pro nactenı vstupnı mnoziny vrcholu polygonu pracuje s polem polygonu, ktere po-

stupne plnı vrcholy, jak cte jednotlive radky vstupnıho souboru.

void loadPoints(const char *filename)

{

points_vector.clear();

// Read lines

try

{

// Open file

FILE *fi=fopen(filename,"r");

for (;fgets(buffer,BUFF,fi);)

{

// Pointer to new node

double coordinates[3]={0,0};

// Delimitation of line to coordinates x,y and number of polygons

int i; char *p;

for (i=0,p=strtok(buffer,"\r\n\t ");p!=0;p=strtok(0,"\r\n\t "),i++)

{

// Convert char to number

coordinates[i]=atof(p);

}

// Load a number of polygons

if (i==1)

{

// A number of polygons

n_polygons = (int)coordinates[0];

// Create the new field of polygons

polygons = new Contour[ n_polygons ];

}

// Set integer coordinates of vertices of polygons

96


if (i==3)

{

polygons[(int)coordinates[2]-1].

push_back(Point(coordinates[0],coordinates[1]));

}

}

// Close file

fclose(fi);

}

catch(...)

{

// Exception

cout << "Error" << "\n"<<"Can not read the file!"<<endl;

}

}

6.3.2 Implementace funkce pro zapis vystupnıch dat

Funkce pro zapis vystupnıch dat postupne zapisuje ze vstupnıho vektoru jednotlive lomove

body liniı do vystupnıho textoveho souboru o zadanem nazvu. Pokud je vstupnı vektor prazdny,

zapıse se do souboru pouze slovo Empty.

void outLines (const char *filename, vector <VertexLine> export_vec)

{

// Open the file

FILE * ofile = fopen (filename,"w");

// The input vector is empty

if (export_vec.empty())

{

fprintf(ofile, "Empty");

}

// Lines in input vector

97


else

{

// For all lines in the vector for export

for (int i =0; i < export_vec.size(); i++)

{

// A vector of vertices of a line

VertexLine out = export_vec[i];

// For every point of the line write its coordinates to the file

for (int j = 0; j < out.size(); j++)

{

fprintf(ofile, "%f\t %f\t %d\n",

out[j]->point.x, out[j]->point.y, i+1);

}

}

}

// Close the file

fclose(ofile);

}

6.3.3 Nastroj pro import vystupu z programu do ArcGIS

Textove soubory vytvorene programem Collapse Polygons to Lines lze hromadne importovat

do geodatabaze v prostredı ArcGIS pomocı nastroje Collapse Output to Lines ze sady nastroju

Collapse/Partial Collapse of Polygons. V zadanem adresari jsou nalezeny vsechny soubory koncıcı

.txt a nacteny nastrojem Make XY Event Layer. Dulezite je, aby soubory mely zachovanou struk-

turu vystupnıho souboru z programu Collapse Polygons to Lines. V uzivatelem definovane geoda-

tabazi se pak nejprve vytvorı nastrojem Copy Features bodova vrstva lomovych bodu liniı, ktere

se nastrojem Points To Line prevedou na liniove feature class a ulozı do dane geodatabaze.

98


Obr. 6.4: Uzivatelske rozhranı nastroje Collapse Polygons to Lines

Obr. 6.5: Model nastroje Collapse Polygons to Lines

99


Obr. 6.6: Popis nastroje Collapse Polygons to Lines

100


6.4 Nastroj pro castecnou redukci prostorove

dimenze

Casti polygonu, ktere zustanou zachovany pri castecne redukci prostorove dimenze, lze zıskat

nastrojem Polygons Parts After Collapse ze sady nastroju Collapse/Partial Collapse of Polygons.

Na zaklade zvolene minimalnı sırky polygonu, ktery ma byt jeste zobrazen jako polygonovy prvek,

se nejprve nastrojem Buffer vypocte buffer1 zadanych polygonu ve vzdalenosti rovne mınus polo-

vine minimalnı sırky, tedy smerem dovnitr polygonu. Pri tomto kroku jsou casti nekterych prvku

eliminovany nebo nektere polygony mohou zaniknout uplne. Casti, ktere nebudou prevedeny na

linie, se zıskajı zpetnou rekonstrukcı ze zredukovanych castı nastrojem Buffer, jenz okolo nich

vytvorı buffer ve vzdalenosti rovne polovine minimalnı sırky.

Obr. 6.7: Ukazka polygonu pred castecnou redukcı prostorove dimenze

Obr. 6.8: Ukazka polygonu po castecne redukci prostorove dimenze

1

”geometricky objekt, ktery obsahuje vsechny prıme polohy, jejichz vzdalenost od specifiko-

vaneho geometrickeho objektu je mensı nebo rovna dane vzdalenosti“ [28]

101


Obr. 6.9: Uzivatelske rozhranı nastroje Polygons to Points

Obr. 6.10: Model nastroje Polygons to Points

102


Obr. 6.11: Popis nastroje Polygons to Points

103


6.5 Zhodnocenı vysledku programu

Program Collapse Polygons to Lines byl testovan na trech vybranych mapovych listech pro

prvky vodnıch ploch z polohopisne casti dat ZABAGED2, ktera vytvarı a poskytuje Cesky urad

zememericky a katastralnı (CUZK). Kvuli velke podrobnosti dat byl vypocet velmi dlouhy a casto

se v nem objevovaly chyby.

Lepsıch vysledku bylo dosazeno pri generalizaci datove sady Vodnı plocha z datoveho produktu

Uzemne analyticke podklady vytvarene a poskytovane Institutem planovanı a rozvoje hlavnıho

mesta Prahy (IPR). Tato data jsou mene podrobna, hranice polygonu tedy obsahujı mene bodu a

vypocet potom trva kratsı dobu a objevuje se mene chyb.

Predzpracovanım dat lze dosahnout jeste mensı chybovosti, pokud jsou odstraneny problema-

ticke vrcholy s vnitrnım uhlem blızıcım se 180◦. Mensı chybovost byla zaznamenana pro protahle

polygony, jejichz delka je vyrazne vetsı nez jejich sırka. Naopak polygonum, ktere byly z casti uzke

a protahle a skokove prechazeli do radove vetsıch tvaru s mnohem mensım rozdılem mezi delkou

a sırkou polygonu, se casto nepodarilo urcit modifikovany straight skeleton vubec nebo byl chybny.

Obr. 6.12: Ukazka chybneho skeletonu

2

”Zakladnı baze geografickych dat Ceske republiky (ZABAGEDr) je digitalnı geograficky mo-

del uzemı Ceske republiky (CR). Polohopisnou cast ZABAGEDrtvorı v soucasne dobe 123 typu

geografickych objektu sıdel, komunikacı, rozvodnych sıtı a produktovodu, vodstva, uzemnıch jed-

notek a chranenych uzemı, vegetace a povrchu, terennıho reliefu a vybrane udaje o geodetickych

bodech. Objekty jsou reprezentovany dvourozmernou vektorovou prostorovou slozkou a popisnou

slozkou, obsahujıcı kvalitativnı a kvantitativnı informace o objektech.“ [29]

104


Linie extrahovana z modifikovaneho straight skeletonu ma hladsı a plynulejsı prubeh nez li-

nie zıskana ze straight skeletonu. Ve vetsine prıpadu se vizualne vıce blızı tomu, co by intuitivne

nakreslil clovek. Vliv nekonvexnıch uhlu na tvar skeletonu je vyznamne snızen. Dıky temto vlast-

nostem je geometricka struktura modifikovany straight skeleton vhodna pro pouzitı v kartografii

pri generalizaci vodnıch toku.

Obr. 6.13: Porovnanı – linie z modifikovaneho straight skeletonu

Obr. 6.14: Porovnanı – linie ze straight skeletonu

105


Obr. 6.15: Ukazka kombinace castecne a uplne redukce prostorove dimenze

Obr. 6.16: Ukazka uplne redukce prostorove dimenze

106

CVUT v Praze ZAVER

Zaver

Generalizace je velmi slozitym procesem a mnoho faktoru, ktere rozhodujı o kvalite vysledneho

mapoveho produktu, lze formalizovat v digitalnım prostredı jen velmi obtızne nebo vubec ne. I kdyz

je mozne, ze nikdy nebude dosazeno plne automatizovaneho procesu generalizace, vznikajıcı gene-

ralizacnı algoritmy dosahujı stale lepsıch vysledku.

V teto praci byla navrzena nova geometricka struktura modifikovany straight skeleton, ktera

na rozdıl od straight skeletonu snizuje prılisny vliv nekonvexnıch uhlu na vysledny tvar skeletonu.

Tato nova struktura byla pouzita v algoritmu pro generalizaci vodnıch toku technikou redukce pro-

storove dimenze, jehoz cılem je prevest polygonove prvky na nerozvetvenou linii, k cemuz vyuzıva

vlastnostı modifikovaneho straight skeletonu, ze pro polygony bez der je tento skeleton binarnım

stromem.

Linie reprezentujıcı vodnı toky zıskane tımto algoritmem majı hladsı prubeh a pusobı vıce

prirozene, nez kdyz se obdobny postup provede se straight skeletonem. Lepsıch vysledku dosahuje

algoritmus u vyrazne protahlych polygonu a prave jejich dimenzi chceme casto pri generalizaci re-

dukovat. Pred pouzitım algoritmu je vhodne odstranit nadbytecne a nepodstatne body nachazejıcı

se v hranici polygonu. Algoritmus lze pouzıt prostrednictvım programu Collapse Polygons to Lines,

ktery je doplnen o sadu nastroju pro software ArcGIS Collapse/Partial Collapse of Polygons.

Algoritmus nabızı moznosti dalsıho vyvoje. Naprıklad extrakce linie za skeletonu by mohla

probıhat na zaklade vıce parametru, vysledna linie reprezentujıcı polygon by mohla byt rozvetvena,

pokud by se stanovila kriteria, podle nichz by se bylo mozne rozhodnout, zda dana cast linie bude

zachovana nebo odstranena.

107

CVUT v Praze POUZITE ZDROJE

Pouzite zdroje

[1] Mezinarodnı kartograficka asociace Multilingual Dictionary of Technical Terms in Cartogra-

phy.Wiesbaden: Franz Steiner, 1973.

[2] CSN 73 0402. Znacky velicin v geodezii a kartografii. Praha: Urad pro technickou normalizaci,

metrologii a statnı zkusebnictvı, 2010.

[3] CSN 73 0401. Nazvoslovı v geodezii a kartografii. Praha: Vydavatelstvı norem, 1990.

[4] VEVERKA, Bohuslav a Ruzena ZIMOVA. Topograficka a tematicka kartografie. Prvnı vydanı.

Praha: Vydavatelstvı CVUT, 2008. ISBN 978-80-01-04157-4.

[5] PLANKA, Ladislav. Kartografie a zaklady GIS. Prvnı vydanı. Brno, 2006.

[6] STANEK, Karel. Zjednodusovanı a zhlazovanı liniovych prvku v automatizovane kartograficke

generalizaci. Brno, 2000. Disertacnı prace. MU Brno.

[7] HASEK, Ales. Soubor topografickych map pro sluzebnı potrebu. Vyzkumna zprava c. 344. Prvnı

vydanı. Praha: Vyzkumny ustav geodeticky, topograficky a kartograficky, 1969.

[8] POPELINSKY, Jan. Automatizovana kartograficka generalizace rıcnıch sıtı. Brno, 2011. Di-

plomova prace. MU Brno. Vedoucı prace Mgr. Karel Stanek, Ph.D.

[9] MCMASTER, Robert B. a K. Stuart SHEA. Generalization in Digital Cartography. Washing-

ton: Association of American Geographers, 1992. ISBN 8-89291-209-X.

[10] DEFLORIANI, Leila a Michela SPAGNUOLO. Shape analysis and structuring. Berlin: Sprin-

ger, 2008. ISBN 35-403-3264-2.

[11] LIEUTIER, Andre. Any open bounded subset of Rn has the same homotopy type as its

medial axis. In: Eighth ACM Symposium on Solid Modeling and Applications SM ’03: June

16-20, 2003, Seattle, Washington, USA : proceedings. New York: Association for Computing

Machinery, c2003, s. 65–75. ISBN 1-58113-706-0.

[12] BAYER, Tomas. Topologicka kostra [online]. [cit. 2014-02-08]. Dostupne z URL:

<http://web.natur.cuni.cz/~bayertom/Adk/adk7.pdf>

[13] BLUM, H. A transformation for extracting new descriptors of shape. In: Weiant Wathen-

Dunn, editor, Models for the Perception of Speech and Visual Form. Proc. of a Symposium.

Cambridge MA: MIT Press, 1967.

[14] POPELINSKY, Jan. Topologicka kostra polygonu a jejı vyuzitı pri kartograficke generalizaci.

Praha, 2007. Diplomova prace. UK v Praze. Vedoucı prace Ing. Tomas Bayer, Ph.D.

[15] HAUNERT, Jan-Henrik a Monika SESTER. Area Collapse and Road Centerlines based on

Straight Skeletons. GeoInformatica. 2008, vol. 12, issue 2, s. 169-191. DOI: 10.1007/s10707-

007-0028-x. Dostupne z: http://link.springer.com/10.1007/s10707-007-0028-x

108

http://web.natur.cuni.cz/~bayertom/Adk/adk7.pdf


[16] PRASAD, Lakshman. Morphological Analysis of Shapes.. CNLS Newsletter 139:1, 1997.

[17] PENNINGA, Friso, Edward VERBREE, Wilko QUAK a Peter VAN OOSTEROM. Con-

struction of the planar partition postal code map based on cadastral registration. Pro-

ceedings of the eleventh ACM international symposium on Advances in geographic infor-

mation systems - GIS 2003. New York: ACM Press, 2003, vol. 12, issue 2, s. 134-140. DOI:

10.1145/956676.956694.

[18] AICHHOLZER, Oswin, Franz AURENHAMMER, David ALBERTS, Bernd GARTNER. A

novel type of skeleton for polygons. In: Journal of Universal Computer Science. Institute for

Image Processing and Computer Supported New Media, 1995, vol. 1, no. 12, s. 752–761.

[19] BAYER, Tomas. Uvod do vypocetnı geometrie. Zakladnı vztahy. [online]. [cit. 2014-02-08].

Dostupne z URL:

<http://web.natur.cuni.cz/~bayertom/Adk/adk2.pdf>

[20] FELKEL, Petr a Stepan OBDRZALEK. Straight skeleton implementation. In: Proceedings of

Spring Conference on Computer Graphics Budmerice, Slovakia, 1998, s. 210–218.

[21] TANASE, Mirela a Remco VELTKAMP. A straight skeleton approximating the medial axis.

In: Lecture Notes in Computer Science, Springer-Verlag, 2004, vol. 3221, s. 809–821.

[22] KOLAR, Josef. Teoreticka informatika. 2. vyd. Praha: Ceska informaticka spolecnost, 2000.

ISBN 80-900-8538-5.

[23] WANG, Tao. Extraction of Optimal Skeleton of Polygon Based on Hierarchical Analysis. In:

International Conference on Geo-spatial Solutions for Emergency Management and the 50th

Anniversary of the Chinese Academy of Surveying and Mapping. Beijing, 2009, s. 272–276

[24] Digia. Qt [software]. Dostupne z URL:

<https://qt-project.org/downloads>

[25] CODE::BLOCKS. Code::Blocks[software]. Dostupne z URL:

<http://www.codeblocks.org/>

[26] ESRI. Model Builder [software]. Dostupne z URL:

<http://www.esri.com/software/arcgis/arcgis10/index.html>

[27] ESRI. ArcGIS Desktop verze 10 [software]. Dostupne z URL:

<http://www.esri.com/software/arcgis/arcgis10/index.html>

[28] Vyzkumny ustav geodeticky, topograficky a kartograficky – Terminologicka komise CUZK.

Terminologicky slovnık zememerictvı a katastru [online]. VUGTK 2005–2012 [cit. 2014-02-

08].

Dostupne z URL: <http://www.vugtk.cz/slovnik/>

109

http://web.natur.cuni.cz/~bayertom/Adk/adk2.pdf

https://qt-project.org/downloads

http://www.codeblocks.org/

http://www.esri.com/software/arcgis/arcgis10/index.html

http://www.esri.com/software/arcgis/arcgis10/index.html

http://www.vugtk.cz/slovnik/


[29] Cesky urad zememericky a katastralnı. Zakladnı baze geografickych dat Ceske republiky

(ZABAGEDr) – polohopis – informace o produktu [online]. CUZK 2014 [cit. 2014-02-10].

Dostupne z URL:

<http://geoportal.cuzk.cz>

110

http://geoportal.cuzk.cz

CVUT v Praze SEZNAM PRILOH

Seznam prıloh

A Elektronicke prılohy 112

111

CVUT v Praze A. ELEKTRONICKE PRILOHY

A Elektronicke prılohy

Obsah CD

/dp diplomova prace ve formatu PDF.

/data data pouzita a vytvorena behem zpracovanı diplomove prace.

/tools ArcGIS toolbox Collapse/Partial Collapse of Polygons.

/zdrojove kody zdrojove kody v C++.

112

Date post:	08-Jul-2020
Category:	Documents
Upload:	others
View:	10 times
Download:	0 times

DIPLOMOVA PR ACE -...

Documents