Kazalo

1 Uvod 15

2 Geometrija in osnove algoritmov 25

2.1 Zgodovinska prièakovanja 25

2.1.1 Kompleksnost v klasièni geometriji 25

2.2 Algoritem 25

2.2.1 Algoritem: Izraz in ovrednotenje uèinka 26

2.2.2 Podatkovne strukture 28

2.2.2.1 Podatkovna struktura DCEL 29

2.2.2.2 Odsekova drevesna struktura 30

2.3 Definicije osnovnih geometrijskih elementov 31

3 Mnogokotniki 33

3.1 Definicija mnogokotnika 33

3.2 Triangulacija - razdeljevanje na trikotnike 34

3.2.1 Obstoj izboèenega temena 34

3.2.2 Obstoj diagonale 35

3.2.3 Obstoj triangulacije in njene lastnosti 35

3.2.4 Dualnost triangulacije 36

3.3 Površina mnogokotnika 37

3.3.1 Vektorski produkt 37

3.3.2 Površina konveksnega mnogokotnika 37

3.3.3 Površina štiristranega konveksnega mnogokotnika 38

3.3.4 Površina štiristranega nekonveksnega mnogokotnika 39

3.3.5 Površina mogokotnika, raèunana iz poljubnega centra 40

3.4 Izvedba triangulacije 40

3.4.1 Diagonala - notranja ali zunanja 40

3.4.2 Triangulacija z odstranjevanjem ušes 42

3.5 Razdeljevanje na trapeze 43

3.5.1 Trapezna dekompozicija s pregledovanjem ravnine 44

3.5.2 Inkrementalni algoritem trapezne dekompozicije 46

3.6 Razdeljevanje mnogokotnikov na konveksne površinske elemente 49

3.6.1 Optimalna konveksna razdelitev mnogokotnika 51

3.7 Ravninski elementi v prostoru 51

4 Konveksne lupine v 2D 53

4.1 Algoritem za konstrukcijo lupine v 2D 54

4.1.1 Deterministièen algoritem za konstrukcijo konveksne lupine v 2D 54

4.1.2 Nakljuèni algoritem za konstrukcijo konveksne lupine v 2D 56

4.2 Nekonveksna lupina niza toèk na ravnini 59

5 Konveksne lupine v 3D 61

5.1 Polieder 51

5.2 Inkrementalni algoritem za konstrukcijo konveksne lupine v 3D 64

5.3 Višje dimenzije 66

5.4 Nekonveksna lupina niza toèk v prostoru 68

6 Voronoi diagram 69

6.1 Definicija Voronoi diagrama 69

2. Delaunayeva triangulacija 71

6.2.1 Odnos med Delaunayevo triangulacijo in Voronoi diagramom 72

6.3 Konstrukcija Voronoi diagrama 73

6.3.1 Deterministièen algoritem za konstrukcijo Voronoi diagrama 73

6.3.2 Inkrementalni algoritem za konstrukcijo Voronoi diagrama 75

6.4 Aplikacije povezane z Voronoi diagrami 76

6.4.2 Maksimiziranje najmanjših kotov triangulacije 76

6.4.3 Najveèji prazen krog 77

6.4.4 Najmanjše razvejišèe 79

6.4.5 Problem trgovskega potnika 79

6.5 Posplošitve Voronoi diagrama 79

7 Zajem prostorskih toèk 81

7.1 Mehanski sistem za zajemanje prostorskih toèk 81

7.1.1 Napake pri zajemanju prostorskih toèk 82

7.2 Napajalnik 84

7.3 Analogno digitalni konverter 84

7.3.1 Povezava A/D konverterja z raèunalnikom 84

7.3.2 Komunikacija med raèunalnikom in A/D konverterjem 85

7.4 Doloèanje koordinatnih vrednosti iz geometrije sistema 89

7.5 Zapis zajetih prostorskih toèk v datoteko 90

6. Popaèenje oblike zaradi napake pri odèitavanju 90

8 Rekonstrukcija površin 93

8.1 Triangulacija površine 93

8.2 Delaunayeva triangulacija v 2D 94

8.2.1 Najveèji prazen krog 94

8.2.2 Pregledovanje ravnine 96

8.2.3 Princip tretje toèke 96

8.2.3.1 Raèunanje polmera najveèje prazne toèke 97

8.3 Delaunayeva triangulacija v 3D 97

8.4 Proces rekonstrukcije površine - Delaunayeva triangulacija 97

8.4.1 Podatkovne strukture 98

8.4.2 Algoritem rekonstrukcije površine 98

8.4.3 Zaèetek pregledovanja v prostoru 100

8.4.4 Princip tretje toèke 100

8.4.4.1 Postavljanje lokalnega koordinatnega sistema 101

8.4.5 Raèunanje normale 103

8.5 Vhod in izhod 103

8.5.1 Vhod 103

8.5.2 Izhod 104

8.6 Rekonstrukcija površine 106

8.6.1 Oblika in število toèk 106

8.6.2 Primer in uporaba 107

8.7 Problemi 110

9 Zakljuèek 111

Literatura 113

Dodatek 115

Za vse zgoraj naštete podatke (in tudi ostale neomenjene) velja, da so le redko zbrani v neko urejeno obliko, ki bi že sama po sebi ponujala rešitev, ampak jih je potrebno v urejeno obliko šele spraviti. To velja tudi za podatke, ki se jih dobi z odčitavanjem površine. Ti podatki so ponavadi neurejeni in razpršeni.

Namen je torej, da bi bilo iz vhodnih neurejenih podatkov, ki so lahko ravninski ali prostorski, mogoèe sklepati o geometriji in topologiji površine, oz. z naèrtnim odèitavanjem toèk zagotoviti digitaliziran model površine ali modela, ki bi ga bilo mogoèe uporabiti pri analiziranju ali pri modeliranju veèjih, bolj zahtevnih oblik. Pri tem je ena možnost naèin, pri katerem se ugotavljajo odnosi med podatki, rezultat pa je popis površine s funkcijo (v odvisnosti od kompleksnosti površine) in drugi, ki temelji na razliènih algoritmih raèunske geometrije, in toèke v prostoru povezuje v "dobre" trikotnike, te pa naprej v optimalno trikotniško mrežo.

V raèunski geometriji vsa teorija temelji na konveksnosti. Tako na stopnji lupin na ravnini, kot tudi kasneje pri konstruiranju lupin v prostoru. Veèina algoritmov, ki gotovo rešujejo probleme pri nedvoumni konveksnosti, pri konstrukciji ali rekonstrukciji površine, ki ni nujno konveksna, v popolnosti odpove. Tako je bilo potrebno za rešitev združiti različne naèine reševanja in ideje, ki jih uporabljajo razlièni algoritmi, pri tem pa postaviti tudi nekaj omejitev, ki jih na tej stopnji ni mogoèe preseèi.

Pri ožjem pojmovanju računske geometrije je ta opredeljena kot proces iskanja in razvršèanja preko doloèene množice elementov. Najpreprostejši primer je razvršèanje enodimenzionalnih toèk po koordinatnih vrednostih. Naj bo niz N sestavljen iz n elementov na realni osi R. Pri tem naj R predstavlja enodimenzionalen prostor R1. Naloga je razvrstiti elemente po njihovih koordinatah. Temu ustreza (Slika 1.2):

Slika 1.2 Razvrstitev H(N) predstavlja ureditev toèk pi glede na koordinatno vrednost.

Potrebno je združiti ureditev H'(N) z ureditvijo H(N) tako, da je pri katerikoli dani toèki qÎ R mogoèe doloèiti interval v H(N), ki to toèko vsebuje.

V primeru prostorske triangulacije je ureditev H(N) triangualcija T(N) preko danega niza toèk v R3. Ureditev T(N) enaka D(N), t.j. Delaunayevi triangulaciji, ki je najboljša možna razdelitev, saj maksimizira najmanjše kote trikotnikov (Slika 1.3).

Slika 1.3 D(N); n = 51 niza N v R3.

Problema razvršèanja in iskanja se lahko združita: dan je niz N, sestavljen iz n elementov na osi R. Oblikovati je mogoèe ureditvi H(N) in H'(N). S pomoèjo slednje je mogoèe doloèiti položaj katerekoli točke v H(N).

Razvršèanje toèk na osi R je najpreprostejši primer raèunske geometrje. Pri premiku v višje dimenzije, niz elementov N ni veè niz toèk, temveè niz linijskih segmentov, ploskev, polprostorov, itd., v Rd prostoru.

Rd predstavlja d-dimenzionalen prostor. Razvrstitev H(N) tako predstavlja ureditev vsega ali samo del prostora Rd, v katerem je niz N. H(N) se imenuje tudi geometrijski kompleks. Pod tem se razume zbir razèlenjenih nizov, razliènih dimenzij, skupaj z medsebojnimi povezavami v prostoru Rd. Najpreprostejši primer je planarni graf, ki je sestavljen iz temen, robov in ploskev ter povezav med njimi. Element, v geometrijskem kompleksu, dimenzije j se imenuje j-ploskev. 0-ploskev ali nièdimenzionalna ploskev je teme, 1-ploskev ali enodimenzionalna ploskev je rob, itd. V tem primeru je terminologija prilagojena planarnemu grafu.

Z razliènimi postavitvami in naèini združevanja teh toèk je mogoèe oblikovati ravninske in prostorske elemente. Na ravnini so to linijski segmenti in iz njih sestavljeni mnogokotniki. Mnogokotniki so obmoèja na ravnini, ki so od okolice razmejeni z nizom linijskih segmentov. Linijski segmenti ali robovi se med seboj dotikajo v temenih. Temena so lahko vboèena ali izboèena, kar vpliva na obliko mnogokotnika in na možnost postavitve diagonale med dve temeni. S postavljanjem diagonal v mnogokotnik se doseže triangulacija ali razdeljevanje na trikotnike. Mogoèi so še drugi naèini razdeljevanja mnogokotnikov: na trapeze, na konveksne površinske elemente. Razdeljevanje mnogokotnikov na površinske podelemente je izvedljivo s pomoèjo algoritmov. Na Sliki 1.4 je prikazan mnogokotnik z osemnajstimi temeni, preko katerega je izvedena triangulacija.

Zgoraj povedano velja za konveksne lupine. Pri lupinah, ki niso nujno konveksne, navedeni opisi odpovejo, saj gre lupina lahko tudi skozi toèke, ki niso ekstremne, zaradi tega opisani naèin ovijanja ovoja okoli niza toèk N za nekonveksne lupine odpove. V nekonveksnih temenih je notranji kot > p . V tem primeru je potrebno lupino graditi na medsebojnih odnosih najbližjih si točk in upoštevati doloèene omejitve. Na Sliki 1.5 je prikazana nekonveksna lupina niza toèk N in konveksna lupina, kakršna bi nastala iz istega niza toèk N po naèinu ovijanja ovoja okoli vseh skrajnih toèk.

Na ravnini je lupina sestavljena iz robov, ki povezujejo med seboj pare toèk. V prostoru je lupina sestavljena iz površinskih elementov: trikotnikov (Slika 1.6), kvadratov ali drugih mnogokotnikov. Površinske elemente se prilagaja namenu uporabe modela doloèenega telesa. Vrsti uporabljenih površinskih elementov je potrebno prilagoditi naèin odèitavanja toèk z modela. Pri trikotniških mrežah je možnosti postavitev trikotnikov več, vendar le ena daje najboljšo možno rekonstrukcijo površine. Na Sliki 1.7 je prikazano, kako postavitev trikotnikov med istimi štirimi točkami vpliva na površino. V tem primeru izbira vpliva tudi na konveksnost površine.

V 7. poglavju je predstavljen sistem za zajemanje prostorskih toèk. Narejen je bil z namenom, da se pokaže možnost mehanskega zajemanja 3D točk, kar je bistveno ceneje od laserskega 3D skenerja. Uporabljeni elementi so najcenejši možni in prav tako izdelava. Zaradi tega je natanènost razmeroma slaba, a še vedno zadovoljiva za predstavitev delovanja sistema in kasneje za prikaz rekonstrukcije površine iz zajetih prostorskih toèk. Pokazana je prièakovana deformacija oblike zaradi nenatanènosti potenciometrov in v podpoglavju 7.6 dejanska deformacija valjaste oblike (Slika 1.8).

Osnovna motiviranost k reševanju geometrijskih problemov izvira že iz starega Egipta in antične Grèije.

Za reševanje geometrijskih problemov je bil pomemben izum Evklidove strukture, to je sheme, ki na slogovno èist naèin vsebuje prepletanje algoritma in njegovega dokaza. Evklidova shema izpolnjuje vse, kar se zahteva od algoritma: je jasna, nedvoumna, natanèna in predvsem zakljuèena celota, ki da konèni rezultat. Shema je pomembna tudi zato, ker doloèa zbir orodij in operacij, ki se jih sme pri reševanju problemov uporabljati. Vprašanje, ki je v dobi reševanja problemov raèunske geometrije s pomoèjo raèunalnika še vedno aktualno je, ali je z Evklidovimi primitivi moè izpeljati do konca vse geometrijske "raèune". Nove možnosti reševanja so se pokazale, ko je Descartes predstavil koordinate in možnost prikazovanja geometrijskih problemov algebraično [3].

Naj bo S niz elementov predstavljen s podatkovno strukturo in naj bo u poljubni element neke splošne množice, katere podmnožica je niz S. Glavne operacije, ki jih je mogoèe izvesti preko niza S, so:

Èe je { S1, S2, ..., Sk} zbir nizov, katerih medsebojni preseki so prazne množice, potem sta uporabni operaciji:

Struktura DCEL je primerna za predstavitev planarnih grafov na ravnini, kjer je G=(V, E) preslikava temen Vi v toèke na ravnini in Ei v povezave med temi toèkami tako, da se povezave med seboj ne sekajo, razen v svojih krajišèih. Planarni graf je tista oblika, pri kateri so povezave med toèkami ravni linijski elementi - robovi.

Naj bo V={ v1, ..., vn} in E={ e1, ..., en} . Graf predstavlja zaporedni zapis robov in temen, v katerih se robovi sekajo. Vsak rob je predstavljen natanèno enkrat. Primer DCEL podatkovne strukture je prikazan v Tabeli 2.1 in na Sliki 2.1 del planarnega grafa, ki ustreza podatkom v tabeli.

V prvih štirih poljih V1, V2, F1 in F2 so zapisani podatki, v zadnjih dveh poljih P1 in P2 so zapisani kazalci na podatkovna polja. V polju V1 je zapisano zaèetno teme roba, v polju V2 je zapisano konèno teme roba. V poljih F1 in F2 sta zapisani imeni ploskev, ki ležita na levi in desni strani gledano iz V1 proti V2. Kazalec P1 kaže na rob, ki v nasprotni smeri urinih kazalcev z vrtiščem v V1 naslednji sledi robu (V1, V2). Podobno velja za kazalec P2, le da je tu vrtišèno teme V2.

Toèka. Toèko p glede na dimenzijo prostora doloèa (x1, ..., xd) v Ed, pri èemer je Ed d-dimenzionalen evklidov prostor. Prav tako je toèko moè razumeti kot d-dimenzionalen vektor v Ed z vrhom v toèki p.

Premica. Dve razlièni toèki q1 in q2 v Ed doloèata premico v tem prostoru kot linearno kombinacijo

a q1+(1-a )q2; (a Î R).

a 1q1+a 2q2+...+a k-1qk-1+(1-a 1-...-a k-1)qk; (a jÎ R, j=1,...k-1).

Linijski segment. Dve razlièni toèki q1 in q2 v Ed doloèata segment podobno kot premico, le da je potrebno zadostiti dodatnemu pogoju za koeficient a

a q1+(1-a )q2; (a Î R, 0a 1).

Taka kombinacija opisuje ravni linijski segment, ki povezuje toèki q1 in q2. Segment je lahko oznaèen tudi kot neurejen par .

Konveksen niz. Podroèje D v Ed je konveksno, èe je linijski segment med katerimakoli dvema toèkama q1 in q2 v Ed, v celoti v D.

Konveksna lupina. Konveksna lupina niza toèk S v Ed je meja okoli konveksnega niza in povezuje med seboj vse ekstremne toèke tega niza.

Mnogokotnik. V E2 je mnogokotnik doloèen kot konèen niz linijskih segmentov, ki se v parih dotikajo med seboj samo v svojih konènih toèkah. Linijski segmenti so robovi mnogokotnika, konène toèke pa temena mnogokotnika.

Polieder. V E3 je polieder doloèen s konènim nizom mnogokotnikov v prostoru, pri èemer se po dva in dva mnogokotnika med seboj dotikata samo v skupnem robu. Temena in robovi mnogokotnikov so hkrati tudi temena in robovi poliedra.

Naj bodo v0, v1, v2, ..., vn-1 toèke na ravnini, naj bodo e0 = v0v1, e1 = v1v2, ..., ei = vivi+1, ..., en-1 = vn-1v0 linijski segmenti, ki povezujejo toèke na ravnini med seboj. Obojih je n in doloèajo mnogokotnik, èe [8]:

Za dokaz prve postavke je potrebno privzeti mejo d P mnogokotnika P kot pot, po kateri hodi hodec v nasprotni smeri urinih kazalcev. Vsak njegov obrat v levo oznaèuje izboèeno teme mnogokotnika, vsak njegov obrat v desno pa vboèeno teme mnogokotnika. Naj bo L premica, ki teèe skozi najnižje teme mnogokotnika v; najnižje glede na koordinato y. Èe je takih temen veè, naj bo to najbolj desno, najnižje teme. notranjost mnogokotnika P je nad premico L. V temenu v hodec naredi obrat v levo, kar pomeni, da ima vsak mnogokotnik najmanj eno izboèeno teme (Slika 3.2).

Slika 3.2 V najbolj desnem, najnižjem temenu se hodec obrne v levo; teme v je izboèeno.

Naj bosta a in b temeni mnogokotnika P, ki ležita na meji mnogokotnika d P pred in za temenom v. Èe daljica ab meje mnogokotnika d P ne seka, niti se je ne dotika, potem je ab nedvoumno diagonala mnogokotnika. Èe pa se daljica ab dotika ali seka mejo mnogokotnika d P, potem za ta mnogokotnik velja n4, v trikotniku D avb pa je še najmanj eno teme mnogokotnika P, ki ni , ali . Naj bo x teme mnogokotnika P v trikotniku D avb, ki je najbližje temenu v v pravokotni smeri na ab. Tako je teme x prvo teme, ki ga zadane premica L, ko se pomika iz temena v proti daljici ab (L | | ab). V prostoru D avb, ki je omejen s premico L (temno senèeno na sliki), ni nobene toèke meje mnogokotnika d P, razen temena x. Tako je daljica vx gotovo diagonala mnogokotnika P (Slika 3.3).

, in so enotski vektorji v x, y in z smeri. V dvodimenzijskem prostoru velja A2 = B2 = 0, od zgornjega izraza ostane (A0B1 - A1B0)× . Površina trikotnika T(a, b, c) je:

A (T) = 0.5(A0B1 - A1B0),

2A (T) = a0b1 - a1b0 - a1c0 - a0c1 - b0c1 - c0b1

Vsak konveksen mnogokotnik je mogoèe trivialno razdeliti na trikotnike tako, da se eno krajišèe vseh diagonal d pripne v eno teme vk (Slika 3.6).

Slika 3.6 Tiangulacija konveksnega mnogokotnika; vse diagonale imajo eno skupno krajišèe v0.

Površina tako razdeljenega poligona, ki ima temena oznaèena v nasprotni smeri urinih kazalcev z v0, v1, ..., vn-1, je lahko zapisana kot

A (P) = A (v0, v1, v2) + A (v0, v2, v3) + ... + A (v0, vn-2, vn-1).

Slika 3.7 Dve možni triangulaciji štiristranega konveksnega mnogokotnika.

A (Q) = A (a, b, c) + A (a, c, d)

2A (Q) = a0b1 - a1b0 + a1c0 - a0c1 - b0c1 - c0b1 + a0c1 - a1c0 + a1d0 - a0d1 + c0d1 - d0c1,

2A (Q) = a0b1 - a1b0 + c0d1 - d0c1.

Do enakega izraza pripelje raèunanje površine tudi v drugem primeru. Razvidno je, da izraz ne vsebuje segmenta ad, kar pomeni, da postavitev diagonale ne vpliva na konèni rezultat A (Q).

Èe so temena vi štiristranega konveksnega mnogokotnika popisana s koordinatama xi in yi, je splošna enaèba za izraèun dvojne površine mnogokotnika enaka

Pri nekonveksnem štiristranem mnogokotniku (Slika 3.8) je možen en sam način triangulacije. Diagonala ac je izven poligona, ostane le ab. Površina mnogokotnika je

A (Q) = A (a, b, c) + A (a, c, d).

Slika 3.8 Nekonveksen mnogokotnik; senèena površina A (a, c, d) je negativna.

Izkaže se, da je enačba za izraèun površine štiristranih mnogokotnikov splošna in velja tudi za mnogokotnike n5.

Pri posplošitvi omenjenega naèina, pri katerem se seštevajo površine trikotnikov, naj bo izhodišèe toèka , ki je povsem poljubna in naj leži zunaj poligona (ni nujno). Naj bo trikotnik, katerega temena so orientirana v nasprotni smeri urinih kazalcev, naj bo katerakoli toèka na ravnini. Potem velja:

A (T) = A (p, a, b) + A (p, b, c) +A (p, c, a).

Slika 3.9 Površina trikotnika doloèljiva preko dveh zunanjih izhodišènih toèk p1 in p2.

Naj bo izhodišèna toèka p = p1 (Slika 3.9). Potem je prvi èlen enaèbe za izraèun površine A (p1, a, b) negativen zaradi svoje orientiranosti; ostala dva èlena sta pozitivna. Površina A (p1, a, b) predstavlja natanko tisto površino štiristranega mnogokotnika (p1, b, c, a), ki je zunaj trikotnika T. Tako je konèna površina natanèno A (T). Podobno velja tudi za izhodišèno toèko p = p2. Obe površini, A (p2, a, b) in A (p2, b, c) sta zaradi svoje orientiranosti negativni in se od A (p2, c, a), ki je pozitivna, odštejeta. Ostanek je natanèno A (T). Podobno velja za katerokoli poljubno toèko na ravnini, znotaj ali zunaj trikotnika T.

Pri triangulaciji je potrebno najprej poiskati diagonalo mnogokotnika. Diagonala razdeli mnogokotnik na dva dela. Postopek je potrebno ponavljati, dokler mnogokotnik ni razdeljen na same trikotnike. Da je daljica vivj, i¹ j diagonala mnogokotnika P, mora veljati dvoje: da ne seka meje mnogokotnika d P in, da je v vsej svoji dolžini v notranjosti mnogokotnika P. Diagonale mnogokotnika se med seboj ne sekajo.

Èe je rob vivi-1 kolinearen z vivj, potem vivj ni diagonala mnogokotnika. Naj bo rob mnogokotnika e = (vi-1, vj) kolinearen z vivj. Mogoèa sta primera, ko je daljica vivj daljša od e; pri j¹ i-1 (Slika 3.10a) in ko je daljica vivj krajša od e (Slika 3.10b), vendar to ni veè enostaven poligon.

Vprašanje notranjosti in zunanjosti je test lokalne narave. Èe je diagonala s = vivj v okolici temen vi in vj v notranjosti mnogokotnika P, potem je v notranjosti mnogokotnika v vsej svoji dolžini. Diagonala v vsej svoji dolžini namreč ne seka meje mnogokotnika d P. Zadostno je testiranje ene same konène toèke diagonale. Èe je diagonala s v okolici toèke vi v notranjosti mnogokotnika, potem je v notranjosti mnogokotnika tudi v okolici toèke vj in obratno. Podobno velja tudi za zunanjost. Test se tako zoži na pregled okolice točke vj. Možna sta primera, ko je teme v vj izboèeno (Slika 3.11a) ali vboèeno (Slika 3.11b).

Slika 3.11 Diagonala s = ij izhaja iz trikotnika doloèenega s temeni vi-1, vi, vi+1: (a) i je izboèeno teme;(b) i je vboèeno vboèeno teme.

Na sliki 3.11a je diagonala ij s krajišèem v izboèenem temenu vi. Jasno je, da je diagonala v notranjosti mnogokotnika P, èe je v notranjosti trikotnika z vrhom v temenu vi. To pomeni, da mora biti teme vi-1 na levi strani diagonale vivj in teme vi+1 ne levi strani vjvi. Ta pogoj se preverja s pomoèjo raèunanja površine med temeni i, j in i-1 ter i, i+1 in j. Èe je površina (raèunana s pomoèjo vektorskega produkta) pozitivnega predznaka, potem predpostavka levega drži, če je negativnega predznaka, predpostavka levega ne drži.

V primeru vboèenosti temena i ta naèin odpove, saj sta lahko temeni i-1 in i+1 hkrati obe na desni strani, hkrati obe na levi strani ali vsako na svoji strani diagonale ij. Podobnost s primerom a je ta, da je notranjost pri izboèenem temenu enaka zunanjosti pri vboèenem temenu. Notrajnost in zunanjost sta zamenjani. Pri drugem primeru torej velja (test po istem naèinu kot pri izboèenem temenu), èe diagonala ni zunanja, potem je notranja. Testira se zunanjost. Pred testiranjem notranjosti oziroma zunanjosti je tako potrebno doloèiti, ali je teme vi izboèeno ali vboèeno. Teme vi je izboèeno, èe je teme vi+1 na levi strani ali na robu vi-1vi. Po dogovoru je teme vi, pri katerem je notranji kot enak , tudi izboèeno.

Hitrejši je naèin, pri katerem se postavlja diagonalo med temeni vi in vi+2, pri èemer mora biti vi+1 izboèeno teme. Imenuje se naèin odstranjevanja ušes mnogokotnika [8]. Po definiciji ima vsak mnogokotnik z n4 vsaj dva neprekrivajoèa se uhlja.

Triangulacija se zaène v izhodišènem temenu v0. Poiskati je potrebno prvo trojico vi, vi+1, vi+2, (uhelj mnogokotnika), t.j. izboèeno teme z vrhom v vi+1. Ko je taka trojica najdena, je daljica vi, vi+2 gotovo diagonala mnogokotnika. Trikotnik vi, vi+1, vi+2 se 'odreže' od preostanka mnogokotnika. Postopek se ponavlja, dokler od mnogokotnika ne ostane samo (zadnji) trikotnik. Triangulacija po načinu odrezovanja ušes je s tem konèana (Slika 3.12). Izhoden podatek je seznam diagonal, ki so definirane z lastnimi krajišèi glede na oznaèevanje vhodnega podatka mnogokotnika (Tabela 3.1).

Naj bo rezultat trapezne dekompozicije H(N). Naj bo Ht(n) presek med polravnino xt in dekompozicijo H(N). Ht(n), ki se med procesom pregledovanja ravnine ves èas spreminja oziroma obnavlja, postane pri x = +¥ enak H(N). Ht(n) se spreminja oziroma obnavlja vsakiè, ko pregledovalna linija L preide kakšno izmed karakteristiènih toèk (krajišèe linijskega segmenta, preseèišèe dveh segmentov). Pregledovalna linija L tako napreduje od x = -¥ proti x = +¥ , od ene karakteristiène toèke do druge. V vsakem trenutku je potrebno vedeti, katera bo naslednja karakteristièna toèka, ki jo bo pregledovalna linija L zadela. Vse karakteristiène toèke so popisane v t.i. popisu dogodkov. Razvršèene so po narašèujoèi koordinati x. Tako je v vsakem trenutku x = t znano, katera karakteristièna toèka je prva na desni strani pregledovalne linije Lt. Preseèišè linijskih segmentov v prvi fazi v tem seznamu ni. Ta so doloèljiva s pomoèjo mejnega seznama. V mejnem seznamu so zapisani vsi linijski segmenti, ki jih v danem trenutku x = t pregledovalna linija Lt seka. Za Sliko 3.14 je mejni seznam { a, b, c, e, d, f, g, } . Do preseèišèa lahko pride le med segmentoma, ki sta si v mejnem seznamu sosednja. Glede na to (Slika 3.14), da se razdalja med segmentoma a in b, ko se pregledovalna linija L približuje presečišèu v, manjša, se lahko naslednje preseèišèe natanèno doloèi vnaprej. Isto velja za vse ostale pare v mejnem seznamu. Ko je preseèišèe doloèeno, se ga pripiše v popis dogodkov. Na zaèetku pregledovanja ravnine sta H(N) in mejni seznam prazna. V popisu dogodkov so krajišèa vseh elementov niza N razvršèena po narašèujoèi koordinati x. Vsakiè, ko pregledovalna linija L preide katero karakteristiènih toèk, se ta v popisu dogodkov zbriše. To pomeni, da se zbriše toèka z najmanjšo vrednostjo x. Ko pregledovalna linija L preide karakteristièno toèko p, se dogaja naslednje (Slika 2.17):

Inkrementalni algoritem trapezne dekompozicije [7] temelji na dodajanju linijskih segmentov v niz N po nakljuènem vrstnem redu. Za vsak na novo dodan linijski segment se dodajo karakteristiène vertikale, ki so del trapezne dekompozicije. Naj bo N niz n linijskih segmentov na ravnini (Slika 3.16) in H(N) konèni rezultat razdelitve na trapeze (Slika 3.17). H(N) nastaja inkrementalno z dodajanjem segmentov iz niza N, enega za drugim po nakljuènem vrstnem redu. V i-tem koraku algoritma je zgrajen H(Ni), pri èemer Ni predstavlja niz prvih i nakljuèno izbranih linijskih segmentov. Na Sliki 3.18 je prikazana trapezna dekompozicija za prve štiri linijske segmente.

Slika 3.18 Trapezna dekompozicija H(N4) za prve štiri linijske segmente.

Slika 3.19 Potovanje vzdolž linijskega segmenta S = S5 od toèke s0 proti toèki s1v razdelitvi H(N4).

Slika 3.20 H'(N4) = H(N5).

Naj bo H(N4) trapezna dekompozicija po štirih dodanih linijskih segmentih. Naj bo toèka s0 eno dveh krajišè linijskega segmenta S = S5. Predpostavimo, da toèka s0 leži v trapezu, ki je v H(N4) že določen. Za doloèitev karakteristiènih toèk je potrebno pregledati vse že doloèene trapeze R0, R1, ... v H(N4), preko katerih gre novododani linijski segment S5. Potrebno je potovati vzdolž linijskega segmenta S = S5 od krajišèa s0 proti krajišèu s1 in pri tem pregledovati obmoèja R0, R1, ... (Slika 3.19). Naj bo f katerikoli trapez v H(Ni), ki ga linijski segment Si+1 seka. V vsakem pregledanem trapezu je potrebno ugotoviti karakteristiène toèke (Slika 3.20) in skozi njih dodati vertikale (za vertikalno dekompozicijo).

Kaj se dogaja, ko linijski segment Si+1 seka že določene trapeze, je prikazano na Sliki 3.21. Èe linijski segment preseka zgornjo ali spodnjo stranico trapeza f, potem je potrebno skozi to preseèišèe postaviti vertikalo, ki je sestavni del trapezne dekompozicije in je na obeh koncih omejena z dvema drugima že postavljenima linijskima segmentoma (na enem koncu se lahko konča v neskonènosti). Èe krajišèe segmenta S leži v notranjosti trapeza f, kot v primeru R0 in R5 na Sliki 3.19, potem je potrebno skozi to krajišèe postaviti vertikalo. Èe novododani segment S seka že postavljeno vertikalo v H(N4), je potrebno to vertikalo odrezati zgoraj, èe je karakteristièna toèka pod S, ali spodaj, èe je karakteristièna toèka nad S. Ko so pregledani vsi trapezi vzdolž segmenta in skozi karakteristiène toèke dodane vse vertikale, je doloèena nova razvrstitev H'(N4) = H(N5). Prikazana je na Sliki 3.20. Sledi dodajanje naslednjega linijskega segmenta iz niza N. Rezultat trapezne dekompozicije je prikazan na Sliki 3.17.

Algoritem je preprost. Najprej je potrebno mnogokotnik P razdeliti na trikotnike in po vrsti odvzemati vse nepomembne diagonale. Na Sliki 3.24 je prikazano vboèeno teme v. Sosednji temeni sta v+ in v-. Levo od v-, v je polravnina H-, desno od v, v+ je polravnina H+. Na polravnini H+ je lahko najveè ena pomembna diagonala. Èe sta diagonali dve, je tista, ki je bližja (v, v+), nepomembna. Njena odstranitev ne povzroèi vboèenosti površinskega elementa v temenu v. Podobno velja tudi za polravnino H-.

Slika 3.24 Pomembne diagonale. Diagonala a je nepomembna, saj diagonala b v polravnini H+ še vedno zagotavlja izboèenost v temenu v. Podobno je tudi c nepomembna diagonala.

toèka v prostoru pi = [ xi, yi, zi] Î R3.

Èe gre pri mnogokotnikih v grobem za razdeljevanje ravnine na dva dela, t.j. na zunanjost in notranjost mnogokotnika, so lupine že bolj kompleksne strukture. Ne samo, da predstavljajo eno osrednjih področij raèunske geometrije, temveè je z njimi mogoèe rešiti tudi velik del ostalih problemov, ki se pojavljajo z razvojem raèunske geometrije.

Loènici med njima sta toèki z najmanjšo in najveèjo vrednostjo koordinate x. Toèke iz niza N je potrebno razporediti po narašèujoèi koordinati x. Glavna ideja je, da se nizu Ni, ki vsebuje prvih i že pregledanih točk, dodajajo naslednje toèke, za katere se preverja, ali ležijo na konveksni lupini ali v njeni notranjosti.

Naj bo Ni niz prvih i toèk, naj bo U(Ni) zgornja veriga, ki je že določena v okviru Ni. Naslednja toèka, ki jo je potrebno pregledati, je p = pi+1. Zadnja, za katero je ugotovljeno, da je del verige U(Ni), naj bo toèka r. Iz toèke r je potrebno potovati po meji U(Ni) v levo in pregledovati že postavljene točke na zgornji verigi. Pri toèki q je pregledovanje konèano, saj leži naslednja toèka s pod linijo pq. Oèitno je, da je v zgornjo verigo U(Ni+1) potrebno pripisati povezavo med toèkama p in q ter zbrisati vse toèke iz že doloèene verige U(Ni), ki so desno od toèke q (Slika 4.2). Enak postopek je potrebno ponoviti še za doloèanje spodnje verige.

Slika 4.2 Dodajanje nove toèke. (a) U(Ni); (b) U(Ni+1).

Slika 4.3 Toèka x je poljubna, ostale so oznaèene glede na narašèujoèi kot ; abcd ... j.

Naslednji korak je pregledovanje že urejenih točk na ravnini. Prvi toèki niza S, ki doloèa konveksne lupine, sta S = (a, b). Naslednja toèka, ki sledi glede na narašèujoèe kote, je toèka c. Konveksnost v vsaki toèki se doloèa z že omenjeno metodo hodca po meji mnogokotnika. Ker hodec po že postavljeni lupini naredi na poti a, b, c v toèki b zavoj v levo, je toèka b gotovo izboèeno teme in toèka c se pripiše nizu S = (a, b, c). Kot naslednjo je potrebno preveriti toèko d. Na poti b, c, d naredi hodec v temenu c zavoj v desno. To pomeni, da je c gotovo vboèeno teme in kot tako ne more biti del meje konveksnega mnogokotnika oz. konveksne lupine. Toèka c se iz niza S izbriše, vpiše se toèka d, S = (a, b, d). Ta postopek je potrebno ponavljati, dokler v nizu S prvi in zadnji element nista enaka; S = (a, b, d, e, g, i, j, a).

Glavni problem je, da ni moè z gotovostjo trditi, da sta toèki a in b na meji konveksnega mnogokotnika oz. na konveksni lupini. Tako bi se v primeru, da nista, postopek preverjanja nadaljeval naprej, kljub temu, da je bil pregledan že ves niz N. Med zaèetkom in koncem niza S ne bi bilo logiène povezave.

Rešitev je, èe se za nakljuèno toèko x izbere najnižjo (po koordinati y) toèko niza N. Èe sta taki toèki dve, naj bo izbrana najbolj desna, najnižja toèka niza N. Zaporedno urejanje po narašèujoèih kotih je enako kot prej omenjeno. Glede na velikost relativnega kota naj bodo toèke zdaj oznaèene s p0, p1, ..., pn-1 v nasprotni smeri urinih kazalcev. V tem primeru je logièno,da so toèke p0, p1 in pn-1 na meji konveksnega mnogokotnika oz. na konveksni lupini. S tem sta odpravljena oba prej omenjena problema. Novo oznaèevanje in urejanje je prikazano na Sliki 3.4.

Prvi nakljuèni algoritem temelji na dodajanju polprostorov Rd, v tem primeru polravnin R2, v ureditev H(N). H(N) predstavlja presek vseh že dodanih polravnin. Polravnina je najosnovnejša konveksna lupina. Presek konveksnih lupin da vedno novo konveksno lupino. Presek polravnin je torej konveksna lupina [7].

Naj bo N niz polravnin in H(Ni) konveksna lupina, t.j. presek vseh polravnin po dodani polravnini S = Si. Naslednji korak je dodajanje (i+1). polravnine S = Si+1 k ureditvi H(Ni) (Slika 4.5).

Slika 4.5 Dodajanje polravnine S = Si+1 k ureditvi H(Ni).

Ureditev H(Ni+1) bo nastala iz H(Ni) po odstranitvi kape i+1, ki je presek H(Ni) Ç , pri èemer je polravnina komplementarna polravnini S. Najprej je potrebno izbrati poljubno teme p Î H(Ni), ki leži na komplementarni ravnini i+1. Èe tako teme ne obstaja, se lahko ravnino S = Si+1 izpusti, saj ne vpliva na H(Ni+1) = H(Ni) Ç Si+1. Èe tako teme obstaja, je potrebno pregledati robove ureditve H(Ni) in ugotoviti preseèišèi (vedno sta dve) med H(Ni) in mejo polravnine Si+1 (oziroma i+1).

Pregledovanje H(Ni) se zaène v temenu p. Naj bo f prvi rob, ki ga je potrebno pregledati. Èe f v celoti leži na polravnini , potem ga je potrebno s pripadajoèima temenoma odstraniti. Prvi rob f, ki leži na samo delno, je hkrati tudi zadnji, ki ga je potrebno pregledati v tej smeri. Na Sliki 4.5 je to rob e1. Ta rob f se razdeli na dva dela tako, da se tisti del, ki leži na polravnini , izbriše, druga polovica pa je hkrati del ureditve H(Ni+1). Pregledovanje je potrebno ponoviti tudi v drugi smeri, da se ugotovi še drugi rob, ki leži hkrati na polravninah in S. Drugi rob na Sliki 4.5 je e2. Od ureditve H(Ni) je potrebno odstraniti kapo, del d Si+1, ki leži med obema odrezanima robovoma f, ki postaneta nova robova ureditve H(Ni+1). Tretji nov rob ureditve H(Ni+1) je rob polravnine Si+1, ki je na obeh koncih omejen z že določenima robovoma e1 in e2.

Osnovna ideja je dodajanje toèk ene za drugo h konveksni lupini, ki jo že doloèa prvih k dodanih toèk oziroma dodajanje toèke k obstojeèi konveksni lupini. Naj bo P = { p0, p1, ..., pn-1} niz toèk na ravnini. Prva konveksna lupina je trikotnik, sestavljen iz toèk konv{ p0,p1,p2} . Naj bo Q = Hk-1 in p = pk. Doloèanje konveksne lupine konv{ Q È p} se razširi na dve možnosti v odvisnosti ali p Î Q ali p Ï Q:

Tangenta, ki povezuje toèko pk z obmoèjem Q, se dotika meje konveksne lupine Q v eni sami toèki. Naj bo pi ena izmed takih toèk. Tudi v tem primeru se toèko lahko doloèi z uporabo predpostavke levega. Na Sliki 4.6 je vidno, da je toèka p levo od smeri pi-1pi in desno oziroma "nelevo" od smeri pipi+1. Za zgornjo tangento velja ravno obratno. Toèka p desno od smeri pj-1pj in levo od smeri pjpj+1. Sledi, da je toèka pj toèka tangente, èe se za dve sosednji toèki dobi drugaèen rezultat predpostavke levega. Ostane še konstrukcija nove konveksne lupine, ki je (p0, p1, ..., pi-1, pi, p, pj, pj+1, ..., pn-1) .

Na ravnini je konveksna lupina doloèena kot ovoj, ki se ga lahko ovije okoli vseh ekstremnih toèk niza N tako, da so vse toèke niza v notranjosti ovoja ali vsaj na njegovi meji (te so ekstremne toèke niza N). Lupina je torej sestavljena iz toèk na ravnini (temen), ki so med seboj povezane z linijskimi segmenti (robovi). Tudi v prostoru je lupina ovoj, ki ga je mogoèe oviti okoli vseh ekstremnih toèk niza N tako, da so vse prostorske toèke v njegovi notranjosti ali vsaj na njegovi meji. V prostoru je lupina sestavljena iz množice toèk (temen), ki so med seboj povezane z linijskimi segmenit (robovi), ti pa med seboj tvorijo ploskve. Temena robov so hkrati tudi temena ploskev. Podobno kot je lupina v 2D doloèena kot presek polravnin R2, je konveksna lupina v 3D doloèena kot presek polprostorov R3.

Meja je torej zaprta in obdaja oziroma omejuje obmoèje prostora. Vsak rob si delita natanèno dve ploskvi, ki se imenujeta sosednji. Za konveksen polieder velja, da je segment, ki povezuje katerikoli toèki poliedra v notranjosti tega poliedra. Konveksnost je popisljiva tudi z notranjimi koti. Notranji kot med dvema sosednjima ploskvama je vedno  in vsota vseh takih kotov okoli vsakega temena je 2.

Iz množice točk je mogoèe doloèiti polieder s pomoèjo inkrementalnega algoritma. Prej opisani algoritem je zadostoval za konstrukcijo konveksne lupine iz množice toèk na ravnini, naslednji pa omogoèa konstruiranje konveksne lupine iz množice toèk v prostoru [8].

Glavna ideja je identièna: pri i-tem dodajanju toèke je potrebno doloèiti Hi Ü konv(Hi-1 È pi). Problem doloèanja se razdeli na dva dela. Naj bo toèka p = pi in Q = Hi-1. Ugotoviti je potrebno, èe velja p Î Q. Èe to drži, se lahko toèko p izpusti, èe ne, je potrebno doloèiti 'stožec', ki je tangenten na Q in ima vrh v toèki p ter skonstruirati novo konveksno lupino. Test p Î Q se izvede podobno kot v dveh dimenzijah. Toèka p je v notranjosti Q, èe je p na pozitivni strani vsake izmed ploskev, ki doloèajo lupino Q. Testiranje predpostavke levega omogoèa volumen tetraedra, kakor to pri dveh dimenzijah omogoèa površina trikotnika. Èe je toèka p v notranjosti lupine Q, morajo imeti vsi volumni enak predznak. Problem nastane, kadar je toèka zunaj lupine Q, saj je potrebno le to spremeniti.

V ravninskem primeru je bilo potrebno poiskati dve tangenti med toèko p in lupino Q. V prostoru pa tangentne linije zamenjajo tangentne ploskve. Te ploskve skupaj oblikujejo stožčasto telo, ki je sestavljeno iz trikotnih ploskev, katerih skupni vrh je v toèki p, osnova pa rob e na lupini Q. Iz toèke p je nekaj ploskev na Q vidnih, nekaj pa nevidnih. Vse tiste ploskve, ki so vidne je potrebno odstraniti pri spreminjanju Q = Hi-1 v Hi. Robovi vidnosti postanejo osnova za konstrukcijo stožca z vrhom v točki p. Rob e na lupini Q je torej tak rob, da je ploskev, ki povezuje e s p, tangenta na Q. Rob e je soseden dvema ploskvama. Ena teh je iz toèke p vidna, druga ne. Rob e je torej na meji med vidnim in nevidnim delom Q.

V nadaljevanju algoritma je potrebno poiskati vse ploskve, ki so vidne iz toèke p. To se ugotovi s pomoèjo volumna, ki ga doloèajo toèke na lupini Q, to je trojica (a, b, c) in toèka p. Èe je ploskev (a, b, c) iz toèke p vidna, potem je volumen tetraedra (a, b, c, p) gotovo negativen. Taka ploskev se odstrani, Hi pa se oblikuje iz nevidnega dela lupine in ploskovne povezave med mejnim robom e in toèko p. V naslednjem koraku se izbere novo toèko p = pi in celoten postopek preverjanja in ponovnega konstruiranja se ponovi, dokler niso pregledane vse toèke niza N v prostoru.

begin pripisati H4 tetraedru (p0,p1,p2,p3);

for za vsako ploskev f stopnje Hi-1 do

vol := vol (f, pi);

izloèiti pi; (* je v notranjosti Hi-1 *)

for za vsak mejni rob e stopnje Hi-1 do

konstrukcija ploskve e,pi;

Popravi Hi;

V višjih dimenzijah postanejo problemi bolj zapleteni in težje predstavljivi. "Hiperprostor" si je najlaže predstavljati, če si znamo predstavljati preskoke iz nièdimenzionalnega prostora v enodimenzionalen in naprej v dvo in trodimenzionalnen prostor.

Predstavljanje prve, druge in tretje dimenzije je preprosto. Problem nastane pri višjih dimenzijah. Najboljši je postopen pristop skozi nižje dimenzije. Točka na številski premici je predstavljena z eno samo številko: je vrednost oziroma lokacija. Lahko se razume kot enodimenziinalen objekt, saj leži na premici, ki je enodimenzionalen element. Točka v dveh dimenzijah je doloèljiva z dvema koordinatama (x, y), v treh dimenzijah pa s tremi (x, y, z). Iz tega sledi, da so za toèko v štirih dimenzijah potrebne štiri koordinate (x, y, z, t). Èe se prve tri koordinate (x, y, z) razumejo kot prostorske koordinate in t kot èas, potem vse štiri skupaj predstavljajo dogodek v prostoru in èasu. Poleg prostor-èasa obstaja še veè možnih izpeljav višjih dimenzij. Ena izmed njih je primer hiperkocke. Nièdimenzionalna kocka je toèka. Enodimenzionalna kocka je daljica. Dvodimenzijska kocka je kvadrat. Tridimenzionalna kocka je normalna kocka v prostoru. Pri tem veljajo naslednji podatki:

Kocka v d dimenzijah je zgrajena iz dveh kock (druga je kopija prve) dimenzije d-1. Èe se enodimenzionalno kocko (toèko) raztegne v drugo dimenzijo, nastane dvodimenzionalna kocka, daljica. Èe se to naprej raztegne v smeri pravokotno sebi, nastane kvadrat. Èe se kvadrat preslika na ravnino, ki je vzporedna prvi, nastane kocka (Slika 5.4). Èe se kocko z osmimi temeni in dvanajstimi robovi preslika v nov položaj in obe kocki poveže z osmimi robovi, nastane t.i. hiperkocka (Slika 5.5). To je kocka v četrti dimenziji. Koordinate temen (vseh je šestnajst) predstavljajo konveksno lupino (Slika 5.6).

Naj bo P = { p1, p1, ..., pn} niz toèk na ravnini. Voronoi diagram V(pi) ravnino razdeli tako, da je diagram V(pi) sestavljen iz vseh toèk, ki so vsaj tako blizu toèki pi, kot so blizu katerikoli drugi toèki pk [8]:

V(pi) = { x: ½ pi - x½ ½ pj - x½ , " j¹ i} .

Naj bosta na ravnini samo dve toèki p1 in p2. Naj bo premica B(p1, p2) = B12, ki pravokotno razdeli segment p1p2 na dva enaka dela. Potem je vsaka toèka x na premici B12 enako oddaljena od toèke p1, kakor tudi od toèke p2. Velja: ½ p1x½ = ½ p2x½ (Slika 6.1).

Slika 6.1 Dve toèki na ravnini: ½ p1x½ = ½ p2x½ .

Èe ležijo na ravnini tri toèke (p1, p2, p3), te definirajo trikotnik. Razpolovnice stranic trikornika B12, B23 in B31 se sekajo v toèki, ki je središèe oèrtanega kroga (Slika 6.2). Ta toèka ni nujno v notranjosti trikotnika.

Iz zgoraj omenjenih primerov je razvidno, da imajo razpolovnice Bij pomembno vlogo pri prouèevanju odnosov med toèkami na ravnini. Naj bo H(pi, pj) zaprta polravnina, ki je omejena z Bij in vsebuje toèko pi. Potem se lahko H(pi, pj) razume kot niz vseh toèk, ki so bliže toèki pi kot toèki pj. Kot že omenjeno, je V(pi) niz toèk, ki so bliže toèki pi, kot katerikoli drugi toèki ali z drugimi besedami, to so toèke, ki so bliže pi kot p1, bliže pi kot p2, bliže pi kot p3, itd. Upoštevaje navedeno je mogoèe napisati enaèbo za Vornoi diagram V(pi):

V(pi) = H(pi,pj),

pri èemer je potrebno upoštevati presek preko vseh i in j, za katere velja i¹ j. Iz enaèbe sledi lastnost Voronoi diagrama: obmoèja Voronoi diagrama so konveksna, ker nastanejo kot preseèišèa veèih polravnin. Kadar so ta obmoèja omejena, so to konveksni poligoni. Robovi se imenujejo Voronoi robovi in temena Voronoi temena. Katerakoli toèka na Voronoi robu ima dve najbližji točki niza toèk na ravnini, Voronoi teme pa ima najmanj tri najbližje take toèke.

Voronoi diagram V(pi) za i = 20 toèk na ravnini bi izgledal kot na Sliki 6.4.

Delaunayeva triangulacija nastane takrat, kadar se med seboj povežejo točke na ravnini, ki imajo skupen Voronoi rob. Delaunayeva triangulacija D(P) in Voronoi diagram V(P) predstavljata dvojnost; isti podatki so predstavljeni na dva razlièna naèina.

Naj bodo toèke na xy ravnini del tridimenzionalnega koordinatnega sistema. Nad vsako toèko naj bo postavljen stožec z nagibom 45o, ki ima vrh v toèki p. V tretji dimenziji je to mogoèe razumeti kot èas. Stožec nad toèko p predstavlja krog, ki se veèa: po èasu t ima radij t. Naj imata toèki p1 in p2 vsaka svoj stožec. Presečišèe teh dveh stožcev je krivulja v prostoru, njena projekcija pa je ravna èrta na xy ravnini (Slika 4.7).

Gledano iz z = - ¥ , bi projekcije vseh prostorskih krivulj, ki so preseèišèa stožcev nad toèkami pi, predstavljale Voronoi diagram na ravnini xy. To lastnost je Fortune uporabil pri svoji metodi. Ravnina se pregleduje s pomoèjo ravnine p , ki je proti ravnini xy nagnjena za 45o. Pregledovalna èrta L je preseèišèe med ravninama p in xy. Naj bo pregledovalna èrta L vzporedna y osi, koordinata x pa naj bo l (Slika 6.8).

Slika 6.8 Stožca presekana s pregledovalno ravnino. Ravnina p in èrta L se pomikata v desno.

Na strani x> l èrte L je od spodaj vidna samo ravnina p . Ta zakriva del stožcev, obenem pa predstavlja del ravnine, ki jo je potrebno še pregledati. Na strani x< l èrte L, je viden Voronoi diagram vse do preseèišèa ravnine p s stožcema. Presečišèe ravnine s stožcem je parabola in tako je tudi presečišèe ravnine p z desno stranjo stožcev parabola. Ta se na ravnino xy (gledano iz z = - ¥ ) projecira kot parabolièno èelo, ki je sestavljeno iz veèih elementarnih parabol (Slika 6.9).

Dve paraboli se stikata v toèki, kjer se ravnina p dotika obeh stožcev. Iz prej navedenih ugotovitev je na tem mestu Voronoi rob. Ker je pregledovalna ravnina p nagnjena pod istim kotom kot stranica stožca, sreča L toèko p v trenutku, ko pregledovalna ravnina zadane ob stožec točke p. Tako Voronoi diagram ne nastaja samo levo od pregledovalne èrte L, ampak ves èas tudi pod ravnino p . Torej: Vornoi diagram nastaja levo od pregledovalne èrte L, navzgor do paraboliènega èela, ki za L nekoliko zaostaja.

Inkrementalni algoritem za konstrukcijo Voronoi diagrama [7] temelji na postopnem dodajanju toèk niza P po nakljuènem vrstnem redu; podobno kot že opisani inkrementalni algoritmi. Naj bo P niz toèk na ravnini in V(P) Voronoi diagram, ki ga te toèke doloèajo. Naj bo Pi niz prvih i nakljuèno izbranih toèk. Na vsaki stopnji i algoritem doloèi Voronoi diagram V(Pi). Diagram V(Pi+1) nastane iz V(Pi) kot je prikazano na Sliki 6.10.

Slika 6.10 (a) V(Pi); (b) V(Pi+1); (b) obmoèje Si+1.

Naj bo S= Si+1 i+1 toèka, ki je na ravnino dodana nakljuèno. Najprej je potrebno poiskati toèko v V(Pi), ki leži v Voronoi območju toèke S. V tem primeru je S bližja točki p kot katerikoli drugi sosednji toèki v V(Pi). Jasno je, da toèka p ne bo veè del diagrama V(Pi+1) . V vsakem trenutku dodajanja i+1 je možnih več toèk p, vendar zadostuje ena sama, ki je izbrana nakljuèno. Ostale toèke (temena Voronoi diagrama), ki so v obmoèju S, je moè poiskati v diagramu V(Pi). Iskanje se zaène v toèki p in je preprosto izvedljivo, saj so sosednja temena med seboj povezana z Voronoi robovi. Robovi, ki so temenom p sosednji, se skrajšajo ali odstranijo. Èe ima Voronoi rob obe krajišèi v toèkah p, se odstrani, èe pa je toèka p samo eno krajišèe, se rob skrajša. Na koncu je potrebno doloèiti še robove Voronoi obmoèja dodane toèke S. Ti robovi povezujejo med seboj krajišèa odrezanih robov v krožnem vrstnem redu. Mesta, kjer se robovi odrežejo, so določljiva z razpolavljanjem povezav med toèko S in ostalimi sosednjimi toèkami. Tako dobljen diagram je V(Pi+1).

Problem najbližjega soseda je iskalne narave. Potrebno je poiskati najbližjega soseda določeni toèki oziroma poiskati najbližjega soseda vsaki izmed toèk niza P. S tem problemom se ukvarjajo na razliènih podroèjih: biologija, ekologija, geografija, fizika, itd.

b je najbližji sosed a-ja, èe | a - b| minc¹ a | a - c| , pri cÎ P. Lahko se tudi zapiše a® b ali najbližji sosed a-ja je b. Ta trditev ni simetrièna, saj ni nujno, da hkrati velja tudi b¬ a (Slika 6.11).

Pri analiziranju kompleksnejših oblik se uporabljajo metode konènih elementov (pri naèrtovanju avtomobilskih lupin). Stabilnost numeriènega postopka je odvisna od kvalitete razdelitve. Izkaže se, da spada Delaunayeva triangulacija med dobre razdelitve. Naj bo P niz toèk, preko katerih je izvedena triangulacija. Linijski segmenti se med seboj sekajo (v svojih krajišèih) samo v toèkah niza P. Konveksna lupina je razdeljena na trikotnike. Z vidika konènih elementov je dobra tista razdelitev, ki uporablja "debele" trikotnike. Izogniti se je potrebno trikotnikom z majhnimi koti. Iz tega sledi postopek maksimiziranja najmanjših kotov. Natanèen odgovor na to je Delaunayeva triangulacija. Naj bo T triangulacija niza P, zapis kotov te triangulacije naj bo (a 1, a 2,...,a 3t), razvršèenih od najmanjšega do najveèjega, pri èemer je t število trikotnikov v T. Število T je konstantno za vsak niz P. Med dvema triangulacijama istega niza P je doloèljivo razmerje T T' glede na njuno 'debelost', èe velja: a 1> a 1' ali a 1= a 1' in a 2> a 2' ali a 1= a 1', a 2= a 2' in a 3> a 3' itd. Iz tega vsega sledi, da je Delaunayeva triangulacija T=D(P) najveèja glede na velikost kotov v odnosu T T' glede na katerokoli razdelitev T' preko niza toèk P.

Potrebno je poiskati najveèji prazen krog, èigar center je v notranjosti konveksne lupine, ki jo doloèa niz toèk S. Prazen v tem smislu, da v njegovi notranjosti ne leži nobena točka niza S in najveèji, da ne obstaja noben tak krog, ki bi imel veèji radij. V praksi je to primerljivo z iskanjem lokacije za postavitev jedrskega reaktorja, ki naj bo zgrajen èim bolj stran od naseljenih krajev. Naj bo f(p) polmer najveèjega praznega kroga s centrom v toèki p. Poiskati je potrebno maksimum te funkcije preko vseh p-jev v konveksni lupini S, H=H(S). Navidezno obstaja neskonèno možnosti za toèko ekstrema. Izkaže pa se, da jih je konèno mnogo.

Naj bo nekje v notranjosti H prazen krog s središèem v p, ki se mu lahko poveèuje polmer. V nekem trenutku bo ta krog zadel ob eno izmed toèk na ravnini S = { s1,...,sn} in imel pri tem vrednost f(p). Èe krog zadane samo ob eno toèko, npr. s1, potem je jasno, da f(p) ni najveèja možna vrednost. Èe se toèka p po premici iz p1 pomakne stran od s1 v toèko p', potem je f(p') > f(p) (Slika 6.12).

Recimo, da pri razdalji f(p) krog zadane ob natanèno dve toèki s1 in s2. Tudi v tem primeru f(p) ne more biti najveèja možna vrednost. Toèko p je mogoèe po razpolovnici S1S2 pomakniti stran od s1 in s2 v toèko p'. Potem velja f(p')> f(p) (Slika 6.12). Iz tega sledi, da funkcija f(p) doseže maksimum samo v primeru, če krog v enem trenutku zadane ob najmanj tri toèke hkrati. Vsako premikanje toèke p bi v tem primeru pomenilo približevanje k neki točki in s tem manjšanje f(p). Èe je torej center p najveèjega praznega kroga v notranjosti lupine H(S), potem mora p sovpadati z Voronoi temenom. Èe p leži na lupini H(S), potem mora toèka p ležati na Voronoi robu. S tem je doloèenih konèno število možnih toèk. Med vsemi je potrebno poiskati tisto, ki ima f(p)= max. Algoritem za najveèji prazen krog:

Problem trgovskega potnika je eden bolj prouèevanih v raèunski geometriji. Je povsem praktiène narave in ga je moè uporabiti pri številnih primerih. Glavno vprašanje je, po kateri poti naj hodi trgovski potnik, da bo obiskal vsa mesta in da bo pot najkrajša možna. Ali, kako z neprekinjeno črto povezati med seboj vse toèke niza M tako, da bo ta èrta najkrajša možna.

Lastnosti Voronoi diagrama omogoèajo posplošitve v veèih smereh, kar se izkaže kot zelo uporabno na razliènih praktiènih podroèjih. Voronoi diagram je v svoji osnovi doloèen kot niz toèk, za katere velja, da ima vsaka najmanj dve najbližji toèki iz niza toèk P. Ena izmed posplošitev je sistem srednjih osi. Srednje osi so skup toèk v notranjosti P, ki imajo najmanj dve najbližji točki na meji d P mnogokotnika P. V tem primeru prej omenjene toèke zamenja meja mnogokotnika d P. Srednje osi pravokotnika so prikazane na Sliki 6.13. Vsaka toèka horizontalnega segmenta v kvadratu je enako oddaljena od zgornjega in spodnjega roba mnogokotnika P. Vsaka toèka na diagonalnem segmentu je enako oddaljena od toèk na sosednjih robovih mnogokonika P. Bolj kompleksen primer je prikazan na Sliki 6.14. Srednje osi imajo drevesno strukturo. Vsaka toèka na srednjih oseh je središèe kroga, ki se meje mnogokonika d P dotika v najmanj dveh toèkah.

Proces modeliranja v prostoru je mogoè tudi na osnovi modelov, ki so dobljeni z zajemom toèk v prostoru. Tako dobljene površine je mogoèe vkljuèiti v že obstojeèa stanja ali jih uporabiti kot osnovo za nove modele. Zajem in modifikacija obstojeèega stanja je pomemben naèin modeliranja na podroèjih, kjer so površine kompleksne in za katere popis površine ne obstaja. Vhodne koordinate toèk so lahko urejene in popisujejo skupine površin, ali pa so neurejena množica točk, za katere površine niso opredeljene. V splošnem so površine kompleksne.

Digitalizirane prostorske toèke je mogoèe z uporabo algoritmov raèunske geometrije združiti v mnogokotniške mreže, ki tvorijo površine. Za zahtevne površine je najbolj uporabna trikotniška mreža.

Na sliki 7.1 je prikazan mehanski sistem za zajemanje prostorskih toèk. Sestavljen je iz treh palic (1, 2 in 3) in treh potenciometrov, ki omogoèajo vrtenje v treh vrtišèih (A, B in C). Na koncu tretje palice je pritrjeno tipalo. Konico tipala je potrebno postaviti na tisto toèko v prostoru, ki se ji želi odčitati koordinatne vrednosti.

Do napak pri zajemanju prostorskih toèk pride v veèji meri zaradi zraènosti v potenciometrih in spojih, zanemarljivo majhen del pa prispeva netogost palic. Zraènost v spojih je mogoèe s primerno izvedbo zmanjšati, medtem ko se na zraènost v potenciometrih ne da vplivati. Zaradi naštetega izmerjene vrednosti odstopajo od realnih, kar vpliva na popaèenje oblike modela, ki se ga želi posneti. Na Sliki 7.2 so prikazane štiri razliène postavitve modela na koordinatno mizo in na Sliki 7.3 štiri predvidena popaèenja oblike zaradi zraènosti v vrtišèih. Senèeno podroèje predstavlja možna odstopanja oblike za kocko, ki je bila uporabljena kot model.

Za pretvarjanje podatkov iz analogne oblike v digitalno se uporablja 8-bitni analogno digitalni konverter ADC0838 [1] s serijskim I/O vhodom in možnostjo uporabe do osmih kanalov. Pri tem se lahko uporablja vsak kanal posebej (rezultat je absolutna vrednost) ali v parih (rezultat je diferenca vrednosti na obeh kanalih).

Signal s na CLK je invertiran, zato je za postavitev CLK na niè potrebno postaviti (hkrati tudi na niè):

outportb( oport, b &= 0xFE ); /* prižge bit 0 */

a = (( ~ inportb( iport ) & 0x80 ) > > 7 ) ½ ( a< < 1);

d = l2 * cos - l3 * cos(,

x = d * cos,

y = d * sin,

z = l1 - l2 * sin - l3 * sin(.

A -  [ -1/6p , +1/6p ] ,

B -  [ -1/12p , +1/12p ] ,

C -  [ 1/12p , 1/2p ] .

Podan je prostorski model, ki se mu želi digitalizirati površino. Osnovni podatek so prostorske točke

pi = [ xi, yi, zi] Î R3, i = 1,...,n

Naèeloma odèitane toèke niso urejene in same po sebi ne doloèajo površine, èe pa že, ta razdelitev ni nujno najboljša. Z delnim urejanjem pri odèitavanju toèk je mogoèe razširiti možnosti rekonstruiranja in celo izboljšati kvaliteto rekonstruirane površine. S tem je mišljena uporaba Delaunayeve triangulacije, ki je že sama po sebi najboljša, vendar je njen rezultat s primernim odčitavanjem toèk mogoèe še izboljšati. Pri urejenem odèitavanju se lahko doloèi osnovni rob telesa, ki se ga želi rekonstruirati ali pa se doloèi meja površine, ki predstavlja samo del površine celega telesa. O ostalih toèkah površine, ki jo je potrebno rekonstruirati, v veèini primerov ni nobenih podatkov. Ne o sosednosti, ne katerih koli drugih podatkov o povezanosti, naklonih in podobno.

pi = [ xi, yi, zi] Î R3, i = 1, ..., n.

ei = pipj za i¹ j.

Ti = [ pi, pj, pk] za i ¹ j ¹ k ali Ti = [ ei, ej, ek] za i ¹ j ¹ k.

Z množico trikotnikov je mogoče rekonstruirati celotno ali samo delno površino modela (Slika 8.1).

Za odnos med Voronoi diagramom in Delaunayevo triangulacio, ki se jo želi doseči, veljajo lastnosti, kot so opisane v podpoglavju 4.2.1.

Delaunyjev trikotnik Ti = [ pi, pj, pk] je tako mogoèe doloèiti iz nekega roba ei = pipj in tiste tretje toèke pk, skozi katero gre najveèji prazen krog, ki gre hkrati tudi skozi obe krajišèi roba pi in pj.

Slika 8.4 Pregledovalni rob potuje preko ravnine in se prilagaja že izgrajeni triangulaciji.

Uporabljene podatkovne strukture so podobne strukturi DCEL, ki je opisana v podpoglavju 2.2.2.1, vendar so zaradi specifiènosti problema nekoliko poenostavljene. Osnovni podatek so toèke v prostoru. Vrednosti koordinat xi, yi in zi so shranjene v polju

int T[ STT] [ 3] ,

int PR[ stPR] [ 2] ,

int NPR[ stNPR] [ 2] ,

int TRIK[ stTRIK] [ 3] ,

Druge strukture so enake osnovnim in so uporabljene za dodatne podatke. Niz vseh robov triangulacije - KN[ stKN] [ 2] , lupina osnovne ploskve telesa, ki leži na ravnini z = 0 - OP[ stOP] [ 2] , normale za posamezne trikotnike - NOPR[ stPR] [ 3] in NONPR[ stNPR] [ 3] ter novo nastala robova trikotnika za vsak rob PR - R1[ 2] in R2[ 2] .