Iterativna konstrukcija mekih ćelija
Ključne riječi: meka ćelija, rezanje vrhova, konveksni poligon, iterativni postupak.
1Uvod
Jedan od temeljnih problema geometrije je popločavanje prostora (engl. tiling), tj. kako podijeliti ravninu ili prostor na dijelove, tzv. ćelije, tako da nema ni preklapanja među ćelijama ni praznina u ravnini ili prostoru. Tradicionalno, ravnina se popločava trokutima, kvadratima i šesterokutima, a prostor kockama i drugim poliedrima. Zajednička svojstva su im ravne stranice, plohe i bridovi te oštri vrhovi
Jedno od glavnih pitanja njihovog rada je kako iz klasičnog poliedarskog popločavanja dobiti meko popločavanje. Rješenje koje autori predlažu je algoritam savijanja bridova (engl. edge bending algorithm), meko popločavanje koje nastaje kao glatka deformacija klasičnog popločavanja, pri čemu se ravni bridovi zakrivljuju, a oštri vrhovi zaglađuju, ali se ne mijenja njihova kombinatorna struktura. To zakrivljenje nije proizvoljno, već je određeno uvjetom da se u svakom vrhu svi polutangentni smjerovi bridova međusobno poravnaju, odnosno da se njihove polutangente (engl. half-tangents) poklapaju u zajedničkom smjeru. Drugim riječima, kutovi se pretvaraju u glatke prijelaze, a vrhovi u običnu točku na tom zakrivljenom prijelazu. U ekstremnom slučaju, ako se navedeni postupak provede na svim bridovima i vrhovima, moguće je dobiti tijelo koje uopće nema oštre kutove.
Za razliku od pristupa iz
U tu svrhu opisujemo iterativni postupak kojim se početni poligon postupno transformira prema graničnom obliku čiji se rub sastoji od dvaju glatkih lukova sa zajedničkim krajnjim točkama i zajedničkim tangentnim smjerom u tim točkama. Postupak se temelji na rezanju vrhova, uz posebnu korekciju rubnih dijelova kojom se kontrolira tangentni smjer uz dvije istaknute rubne točke.
Definicija 1. (Meka ćelija) Ravninsku ćeliju C nazivat ćemo mekom ćelijom ako je njezin rub jednostavna zatvorena krivulja koja se može zapisati kao unija dvaju po dijelovima glatkih lukova s istim krajnjim točkama P^{+} i P^{-}. Pretpostavljamo da se ta dva luka sijeku samo u točkama P^{+} i P^{-}. Rub je gladak izvan tih dviju točaka, a u točkama P^{+} i P^{-} pripadni se rubni lukovi susreću tangencijalno. Točke P^{+} i P^{-} nazivat ćemo istaknutim rubnim točkama ćelije.
Definicija
Konstrukciju najprije provodimo za dva luka zadana kao grafovi nad intervalom [0,1], pri čemu parametar \theta\in(0,\pi) određuje njihov zajednički tangentni smjer nakon rotacije. Za proizvoljne pozitivne glatke funkcije \varphi_{1},\varphi_{2}\colon[0,1]\to\mathbb{R} definiramo
\gamma_{k}(x) = \cot\theta\,x(1-x)(1-2x) + (-1)^{k}\varphi_{k}(x)x^{2}(1-x)^{2}, \qquad k=1,2,
gdje je \theta\in\langle 0,\pi\rangle. Budući da vrijedi \gamma_{k}(0)=\gamma_{k}(1)=0, oba grafa imaju zajedničke krajnje točke (0,0) i (1,0). Zbog pozitivnosti funkcija \varphi_{1} i \varphi_{2} te suprotnih predznaka drugog člana vrijednosti \gamma_{1}(x) i \gamma_{2}(x) razlikuju se za svaki x\in\langle 0,1\rangle, pa se grafovi ne sijeku izvan krajnjih točaka.Faktor x^{2}(1-x)^{2}, kao i njegova prva derivacija, iščezava u točkama x=0 i x=1. Stoga drugi član ne utječe na tangentne smjerove u krajnjim točkama, pa za oba grafa vrijedi
\gamma_{k}'(0)=\gamma_{k}'(1)=\cot\theta.
Njihovi su tangentni pravci u objema krajnjim točkama zato paralelni s vektorom (1,\cot\theta).Dobivene grafove zatim rotiramo za kut \theta oko ishodišta. Točka (0,0) pritom ostaje P^{-}=(0,0), dok se točka (1,0) preslikava u P^{+}=(\cos\theta,\sin\theta). Istom se rotacijom vektor (1,\cot\theta) preslikava u vektor paralelan s osi y. Tako dobivamo dva luka sa zajedničkim krajnjim točkama P^{-} i P^{+}, koji se ne sijeku izvan tih točaka i u objema se krajnjim točkama susreću tangencijalno, sa zajedničkim vertikalnim tangentnim pravcem.
Konstrukcija za proizvoljne zadane krajnje točke Q^{-}\neq Q^{+} i propisani zajednički tangentni pravac dobiva se transformacijom ove normalizirane ćelije. Parametar \theta odabire se tako da kut između spojnice P^{-}P^{+} i vertikalnog pravca bude jednak kutu između spojnice Q^{-}Q^{+} i zadanog tangentnog pravca. Normalizirana se ćelija zatim rotira tako da se vertikalni pravac preslika u zadani tangentni pravac, dilatira faktorom \lVert Q^{+}-Q^{-}\rVert i translira tako da se P^{-} preslika u Q^{-}. Iz izbora kuta \theta slijedi da se pritom P^{+} preslikava u Q^{+}.
Ova eksplicitna konstrukcija pokazuje da sama egzistencija ravninske meke ćelije s navedenim svojstvima nije glavni problem kojim se bavimo. Doprinos ovog rada sastoji se u drukčijem, iterativnom pristupu: polazimo od zadanog konveksnog poligona i definiramo modificirani postupak rezanja vrhova kojim se njegov rub postupno transformira prema mekoj ćeliji. Pritom dokazujemo sadržanost svih dobivenih poligonalnih likova u početnom poligonu, konvergenciju rubnih lanaca te njihovo usmjeravanje prema zajedničkom tangentnom smjeru u dvjema istaknutim rubnim točkama.
Iterativna konstrukcija dodatno ovisi o nenul-vektoru smjera v=(v_{1},v_{2}), koji određuje tangentni smjer prema kojem se rubovi uz istaknute rubne točke postupno usmjeravaju.
2Definicija iterativnog postupka
U ovom odjeljku definiramo osnovnu verziju postupka za smjer toka v=(0,-1). Pravce paralelne s vektorom v u nastavku nazivamo vertikalnim pravcima, a njihov smjer vertikalnim smjerom. Postupak za proizvoljan smjer naknadno opisujemo pomoću rotacije koordinatnog sustava.
Poligonalnim lancem nazivamo uređeni konačni niz točaka A=(a_{0},\ldots,a_{m}), zajedno sa segmentima [a_{i-1},a_{i}], i=1,\ldots,m. Rubni lanac poligona jest poligonalni lanac sastavljen od uzastopnih vrhova njegova ruba.
Definicija 2. (Dopušteni konveksni poligon) Neka je C konveksan poligon u ravnini. Kažemo da je poligon C dopušten za vertikalni smjer v=(0,-1) ako vrijede sljedeći uvjeti:
Rubni vrh s najvećom ordinatom označavamo s P^{+}, a rubni vrh s najmanjom ordinatom s P^{-}.
| (1) | Među vrhovima poligona postoji jedinstveni vrh s najvećom ordinatom i jedinstveni vrh s najmanjom ordinatom. Te vrhove nazivamo rubnim vrhovima. |
| (2) | Svaki od dvaju rubnih lanaca između rubnih vrhova sadrži barem jednu unutarnju točku. |
Za proizvoljan nenul-vektor smjera analogni se izbor (i provjera jedinstvenosti) istaknutih rubnih točaka dobiva promatranjem projekcija vrhova na taj smjer. U nastavku, međutim, radimo u vertikalnom slučaju, pa su P^{+} i P^{-} određeni kao jedinstveni najviši i najniži vrhovi početnog poligona.
Definicija 3. (Kompatibilnost s vertikalnim tokom) Neka je C dopušten konveksan poligon za smjer v=(0,-1), s istaknutim rubnim točkama P^{+} i P^{-}. Neka su
A^{0}=(P^{+},a_{1}^{0},\ldots,a_{m-1}^{0},P^{-}) \quad\text{i}\quad B^{0}=(P^{+},b_{1}^{0},\ldots,b_{n-1}^{0},P^{-})
dva početna rubna lanca. Neka su \Pi^{+} i \Pi^{-} ortogonalne projekcije na vertikalne pravce kroz P^{+}, odnosno P^{-}. Kažemo da je C kompatibilan s vertikalnim tokom ako vrijedi
\Pi^{+}(a_{1}^{0}),\ \Pi^{+}(b_{1}^{0}),\ \Pi^{-}(a_{m-1}^{0}),\ \Pi^{-}(b_{n-1}^{0})\in C.
Uvjet kompatibilnosti traži da projekcije prvih i zadnjih unutarnjih točaka obaju lanaca na vertikalne pravce kroz P^{+} i P^{-} ostanu u početnom poligonu C. Geometrijski, to znači da su ti vertikalni pravci sadržani u unutarnjim kutovima poligona kod istaknutih vrhova P^{+} i P^{-}. Nakon ove pretpostavke možemo definirati sam iterativni postupak.
Definicija 4. (Iterativno rezanje vrhova s rubnom korekcijom) Neka je C dopušten konveksan poligon kompatibilan s vertikalnim tokom, s istaknutim rubnim točkama P^{+} i P^{-}. Rub poligona rastavljamo na dva lanca
Položaj reznih točaka uz krajeve lanca dodatno korigiramo:
Potom definiramo novi lanac A^{k+1}:
A^{0}=(a_{0}^{0},a_{1}^{0},\ldots,a_{m_{0}}^{0}), \qquad B^{0}=(b_{0}^{0},b_{1}^{0},\ldots,b_{n_{0}}^{0}),
pri čemu vrijedi a_{0}^{0}=b_{0}^{0}=P^{+}, a_{m_{0}}^{0}=b_{n_{0}}^{0}=P^{-}. Neka je 0\lt \rho\lt 1/2. Jedan korak iterativnog postupka definiramo na lancu
A^{k}=(a_{0}^{k},a_{1}^{k},\ldots,a_{m_{k}}^{k}), \qquad a_{0}^{k}=P^{+},\quad a_{m_{k}}^{k}=P^{-}.
Za svaki unutarnji vrh a_{i}^{k}, i=1,\ldots,m_{k}-1, definiramo rezne točke
l_{i}^{k}=\rho a_{i-1}^{k}+(1-\rho)a_{i}^{k}, \qquad r_{i}^{k}=(1-\rho)a_{i}^{k}+\rho a_{i+1}^{k},
kao konveksne kombinacije susjednih točaka u lancu. Točka l_{i}^{k} nalazi se na bridu koji dolazi u vrh a_{i}^{k}, a točka r_{i}^{k} na bridu koji iz njega izlazi.
(l_{1}^{k})^{\ast}=(1-\rho)l_{1}^{k}+\rho\Pi^{+}(l_{1}^{k}), \qquad (r_{m_{k}-1}^{k})^{\ast} =(1-\rho)r_{m_{k}-1}^{k}+\rho\Pi^{-}(r_{m_{k}-1}^{k}).
Dodatna korekcija predstavlja konveksnu kombinaciju rezne točke na kraju lanca i njezine projekcije na vertikalni pravac kroz susjednu rubnu točku poligona.
Slika 2: Jedan korak iterativnog postupka. Lijevo je prikazano rezanje unutarnjeg vrha a_{i}^{k}: na susjednim bridovima određuju se rezne točke l_{i}^{k} i r_{i}^{k}, koje se zatim spajaju novim segmentom. Desno je prikazana rubna korekcija uz istaknutu točku P^{+}: rezna točka l_{1}^{k} djelomično se projicira prema vertikalnom pravcu kroz P^{+}, čime nastaje korigirana točka (l_{1}^{k})^{\ast}.
A^{k+1}= \bigl( P^{+}, (l_{1}^{k})^{\ast},r_{1}^{k}, l_{2}^{k},r_{2}^{k}, \ldots, l_{m_{k}-1}^{k},(r_{m_{k}-1}^{k})^{\ast}, P^{-} \bigr).
Isto se pravilo primjenjuje na lanac B^{k}, čime se dobiva lanac B^{k+1}. Poligonalni lik C^{k} definiramo kao područje omeđeno lancima A^{k} i B^{k}. Posebno, C^{0}=C.Rubna korekcija ima posebnu ulogu. Obično rezanje vrhova uklanja poligonalne kutove na unutarnjim dijelovima lanaca, ali ne mijenja tangentni smjer stranica početnog poligona u istaknutim rubnim točkama. Djelomična projekcija prve i zadnje rezne točke prema pripadnom vertikalnom pravcu uvodi tu kontrolu: unutarnji dijelovi ruba zaglađuju se standardnim rezanjem, dok se segmenti uz P^{+} i P^{-} postupno usmjeravaju prema zajedničkoj vertikalnoj tangenti.
Postupak se može interpretirati kao idealizirani model zaglađivanja poligonalnog oblika erozijom pod djelovanjem sredstva koje dolazi iz zadanog smjera. Standardno rezanje vrhova opisuje lokalno uklanjanje materijala na istaknutim dijelovima ruba, pri čemu se oštri poligonalni prijelazi postupno zamjenjuju blažima. Smjer djelovanja sredstva posebno utječe na dijelove ruba uz istaknute točke P^{+} i P^{-}: rubna korekcija pomiče krajnje rezne točke prema pravcima paralelnima sa zadanim smjerom, pa se krajnji segmenti tijekom iteracija postupno poravnavaju s tim smjerom. Ovu interpretaciju ne treba shvatiti kao fizikalni model konkretnog erozijskog procesa, nego kao geometrijsku motivaciju za izbor lokalnog pravila rezanja i usmjerene rubne korekcije.
Slika 3: Prvih deset koraka iterativnog rezanja vrhova s rubnom korekcijom. Početni konveksni poligon prikazan je isprekidanom sivom linijom, a poligonalni lik C^{k} dobiven nakon k-tog koraka punom crnom linijom.
Slika 4: Usporedba rezultata iterativnog postupka za različite vrijednosti parametra \rho. Početni poligon prikazan je isprekidanom sivom linijom, a dobiveni poligonalni lik punom crnom linijom. Veće vrijednosti parametra odgovaraju jačem lokalnom rezanju vrhova u jednom koraku.
3Konvergencija prema mekoj ćeliji
U ovom poglavlju pokazujemo da iterativni postupak iz Definicije
Lema 5. (Glatkoća unutarnjih dijelova lanaca) Neka je 0\lt \rho\lt 1/3. Na dijelovima lanaca koji nisu neposredno uz istaknute rubne točke P^{+} i P^{-}, postupak iz Definicije 4 podudara se sa standardnim postupkom rezanja vrhova s fiksnim parametrom \rho. Zato unutarnji dijelovi rubnih lanaca konvergiraju prema glatkim graničnim lukovima.
Dokaz. Rubna korekcija djeluje samo na prve i zadnje rezne točke pojedinog lanca. Na svakom dijelu lanca koji je odvojen od istaknutih rubnih točaka postupak se zato svodi na standardno rezanje vrhova s fiksnim omjerom 0\lt \rho\lt 1/2. Za \rho=1/4 dobiva se Chaikinov postupak, čija je granična krivulja kvadratni B-splajn [3] . Za 0\lt \rho\lt 1/3 konvergencija prema glatkom graničnom luku slijedi iz poznatih rezultata o regularnosti de Rhamovih krivulja [6] .
\ \blacksquare
Za \rho=1/4 granični lukovi imaju eksplicitan zapis kao dijelovi uniformnog kvadratnog B-splajna
Lema 6. (Rubno usmjeravanje) Neka se na rubni lanac
A^{k}=(a_{0}^{k},a_{1}^{k},\ldots,a_{m_{k}}^{k}), \qquad a_{0}^{k}=P^{+},\quad a_{m_{k}}^{k}=P^{-},
primjenjuje iterativno rezanje vrhova s rubnom korekcijom za smjer v=(0,-1). Tada se smjer prvog segmenta lanca uz P^{+} i smjer zadnjeg segmenta lanca uz P^{-} približavaju vertikalnom smjeru.
Dokaz. Promotrimo početak lanca kod P^{+}. Neka je w^{k} vektor smjera prvog segmenta u lancu:
Ortogonalna projekcija na vertikalni pravac kroz P^{+} zadržava y-koordinatu točke l_{1}^{k}, a x-koordinatu zamjenjuje x-koordinatom točke P^{+}. Zato je
Sada iz definicije rubne korekcije slijedi
(1) i (2) dobivamo
Ponavljanjem rekurzivnog opisa iz (3) dobivamo
w^{k}=a_{1}^{k}-P^{+}=(\Delta x^{k},\Delta y^{k}).
Prva rezna točka prije rubne korekcije jednaka je
l_{1}^{k}=\rho P^{+} +(1-\rho)a_{1}^{k},
pa vrijedi
(1)
l_{1}^{k}-P^{+}=(1-\rho)w^{k} = (1-\rho)(\Delta x^{k},\Delta y^{k}).
(2)
\Pi^{+}(l_{1}^{k})-P^{+} = \bigl(0,\,(1-\rho)\Delta y^{k}\bigr).
(l_{1}^{k})^{\ast}-P^{+} = (1-\rho)(l_{1}^{k}-P^{+})+\rho(\Pi^{+}(l_{1}^{k})-P^{+}).
Uvrštavanjem jednakosti
(l_{1}^{k})^{\ast}-P^{+} = (1-\rho) \bigl((1-\rho)\Delta x^{k},\,(1-\rho)\Delta y^{k}\bigr) + \rho \bigl(0,\,(1-\rho)\Delta y^{k}\bigr),
pa je
(\Delta x^{k+1},\Delta y^{k+1}) = (l_{1}^{k})^{\ast}-P^{+} = \bigl((1-\rho)^{2}\Delta x^{k},\,(1-\rho)\Delta y^{k}\bigr).
Prema tome, za prvi segment u sljedećem koraku vrijedi
(3)
\frac{\Delta x^{k+1}}{\Delta y^{k+1}} = \frac{(1-\rho)^{2}\Delta x^{k}}{(1-\rho)\Delta y^{k}} = (1-\rho)\frac{\Delta x^{k}}{\Delta y^{k}}.
\frac{\Delta x^{k}}{\Delta y^{k}} = (1-\rho)^{k}\frac{\Delta x^{0}}{\Delta y^{0}}.
Kako je 0\lt \rho\lt 1/2, vrijedi (1-\rho)^{k}\to 0, pa omjer \Delta x^{k}/\Delta y^{k} teži nuli. Stoga normirani vektor smjera prvog segmenta konvergira prema vektoru paralelnom s v=(0,-1), odnosno smjer segmenta približava se vertikalnom smjeru. Dokaz za P^{-} provodimo analogno.
\ \blacksquare
Propozicija 7. (Sadržanost u početnom poligonu) Neka je C konveksan poligon kompatibilan s vertikalnim tokom. Tada svi poligonalni likovi C^{k} dobiveni postupkom iz Definicije 4 leže u početnom poligonu C.
Dokaz. Bez smanjenja općenitosti dokaz provodimo za lanac A. Neka je
Za k=0 sve točke početnog lanca pripadaju rubu poligona C, pa pripadaju i samom poligonu. Zbog kompatibilnosti (Definicija3 ), projekcija prve unutarnje točke početnog lanca na vertikalni pravac kroz P^{+} te projekcija zadnje unutarnje točke početnog lanca na vertikalni pravac kroz P^{-} također pripadaju C, tj.
Pretpostavimo da tvrdnja vrijedi u k-tom koraku. Obične rezne točke imaju oblik konveksnih kombinacija
Time je korak indukcije dokazan. Sve točke svih konačnih lanaca pripadaju C. Kako je C konveksan, i svi segmenti između uzastopnih točaka tih lanaca pripadaju C. Zato svaki poligonalni lik C^{k} leži u početnom poligonu C.
A^{k}=(a_{0}^{k},a_{1}^{k},\ldots,a_{m_{k}}^{k}), \qquad a_{0}^{k}=P^{+},\quad a_{m_{k}}^{k}=P^{-}.
Pokazat ćemo indukcijom da sve točke lanca A^{k} pripadaju poligonu C, te da projekcija prve unutarnje točke na vertikalni pravac kroz P^{+} i projekcija zadnje unutarnje točke na vertikalni pravac kroz P^{-} također pripadaju C.Za k=0 sve točke početnog lanca pripadaju rubu poligona C, pa pripadaju i samom poligonu. Zbog kompatibilnosti (Definicija
\Pi^{+}(a_{1}^{0})\in C, \qquad \Pi^{-}(a_{m-1}^{0})\in C.
Time je dokazana baza indukcije.Pretpostavimo da tvrdnja vrijedi u k-tom koraku. Obične rezne točke imaju oblik konveksnih kombinacija
l_{i}^{k}=\rho a_{i-1}^{k}+(1-\rho)a_{i}^{k}, \qquad r_{i}^{k}=(1-\rho)a_{i}^{k}+\rho a_{i+1}^{k}.
Po pretpostavci indukcije sve točke a_{i}^{k} pripadaju C. Budući da je C konveksan, sve točke l_{i}^{k} i r_{i}^{k} također pripadaju C. Preostaje provjeriti rubnu korekciju. Kod P^{+} prva rezna točka prije korekcije je
l_{1}^{k}=\rho P^{+} +(1-\rho)a_{1}^{k}.
Budući da je ortogonalna projekcija na vertikalni pravac afina, vrijedi
\Pi^{+}(l_{1}^{k}) = \rho P^{+} +(1-\rho)\Pi^{+}(a_{1}^{k}).
Po pretpostavci indukcije vrijedi \Pi^{+}(a_{1}^{k})\in C, dok je P^{+}\in C po definiciji. Iz konveksnosti C slijedi da je konveksna kombinacija tih točaka, \Pi^{+}(l_{1}^{k}), također u C. Tada i djelomično projicirana točka
(l_{1}^{k})^{\ast} = (1-\rho)l_{1}^{k}+\rho\Pi^{+}(l_{1}^{k})
pripada C, jer je i ona tada konveksna kombinacija dviju točaka iz C. Ta je točka nova prva unutarnja točka lanca A^{k+1}. Osim toga,
\Pi^{+}\bigl((l_{1}^{k})^{\ast}\bigr)=\Pi^{+}(l_{1}^{k}),
pa projekcija nove prve unutarnje točke ponovno pripada C. Isti argument vrijedi na kraju lanca kod P^{-}, koristeći projekciju \Pi^{-}.Time je korak indukcije dokazan. Sve točke svih konačnih lanaca pripadaju C. Kako je C konveksan, i svi segmenti između uzastopnih točaka tih lanaca pripadaju C. Zato svaki poligonalni lik C^{k} leži u početnom poligonu C.
\ \blacksquare
Lema 8. (Odvojenost rubnih lanaca) Neka je C dopušten konveksan poligon kompatibilan s vertikalnim tokom. Neka su A^{0} i B^{0} dva početna rubna lanca od P^{+} do P^{-}, označena tako da je A^{0} lijevi, a B^{0} desni lanac. Tada se, za svaki k\geq 0, lanci A^{k} i B^{k} sijeku samo u zajedničkim krajnjim točkama P^{+} i P^{-}.
Dokaz. Dokaz provodimo indukcijom po k. Za k=0 tvrdnja vrijedi jer su A^{0} i B^{0} dva rubna lanca istog konveksnog poligona, pa se sijeku samo u zajedničkim krajnjim točkama P^{+} i P^{-}.
Pretpostavimo da tvrdnja vrijedi u k-tom koraku. Razdvojimo ponašanje postupka na unutarnje i rubne dijelove lanaca. Unutarnjim dijelom lanca nazivamo dio koji potječe od početnog podlanca između prve i zadnje unutarnje točke, tj. između a_{1}^{0} i a_{m-1}^{0} na lancu A^{0}, odnosno analogno na lancu B^{0}. Na tim se dijelovima postupak podudara sa standardnim rezanjem vrhova, bez rubne korekcije. Budući da ti početni podlanci pripadaju rubu konveksnog poligona C, standardno rezanje vrhova na njima čuva poredak točaka i ostaje unutar konveksne ljuske početnog podlanca, što je osnovno svojstvo postupaka rezanja vrhova[5] . Posljedično, zbog disjunktivnosti konveksnih ljuski početnih unutarnjih podintervala, lijevi i desni lanac se na unutarnjim podlancima ne sijeku.
Preostaju rubni dijelovi, tj. dijelovi lanca koji nastaju uz P^{+} prije prve unutarnje točke i uz P^{-} nakon zadnje unutarnje točke. Na tim dijelovima dolazi do primjene rubne korekcije, pa se ondje pojavljuje konkavnost u odnosu na početni poligon. Međutim, ti su dijelovi po konstrukciji vezani uz vertikalne pravce kroz istaknute rubne točke.
Prema Definiciji3 , projekcije relevantnih početnih rubnih točaka na te pravce pripadaju C, pa vertikalni pravci kroz P^{+} i P^{-} određuju lokalne separatore između dvaju rubnih dijelova. Rubna korekcija je djelomična projekcija prema odgovarajućem separatoru: korigirana rezna točka nalazi se na segmentu između nekorigirane rezne točke i njezine projekcije na taj pravac. Zato se točka s jedne strane pomakne prema separatoru, ali ga ne prelazi. Budući da se ista konstrukcija primjenjuje i na drugi lanac, s druge strane separatora, rubna korekcija ne može prebaciti jedan lanac preko separatora, pa ni preko drugoga lanca.
Dakle, na unutarnjim dijelovima odvojenost se čuva standardnim rezanjem konveksnih rubnih podlanaca, a na rubnim dijelovima čuva se činjenicom da rubna korekcija pomiče krajnje rezne točke prema vertikalnim separatorima, ali ih ne prebacuje preko njih. Prijelaz iz A^{k},B^{k} u A^{k+1},B^{k+1} zato ne uvodi novo sjecište između lanaca. Indukcijom slijedi da se za svaki k\geq 0 lanci A^{k} i B^{k} sijeku samo u P^{+} i P^{-}.
Pretpostavimo da tvrdnja vrijedi u k-tom koraku. Razdvojimo ponašanje postupka na unutarnje i rubne dijelove lanaca. Unutarnjim dijelom lanca nazivamo dio koji potječe od početnog podlanca između prve i zadnje unutarnje točke, tj. između a_{1}^{0} i a_{m-1}^{0} na lancu A^{0}, odnosno analogno na lancu B^{0}. Na tim se dijelovima postupak podudara sa standardnim rezanjem vrhova, bez rubne korekcije. Budući da ti početni podlanci pripadaju rubu konveksnog poligona C, standardno rezanje vrhova na njima čuva poredak točaka i ostaje unutar konveksne ljuske početnog podlanca, što je osnovno svojstvo postupaka rezanja vrhova
Preostaju rubni dijelovi, tj. dijelovi lanca koji nastaju uz P^{+} prije prve unutarnje točke i uz P^{-} nakon zadnje unutarnje točke. Na tim dijelovima dolazi do primjene rubne korekcije, pa se ondje pojavljuje konkavnost u odnosu na početni poligon. Međutim, ti su dijelovi po konstrukciji vezani uz vertikalne pravce kroz istaknute rubne točke.
Prema Definiciji
Dakle, na unutarnjim dijelovima odvojenost se čuva standardnim rezanjem konveksnih rubnih podlanaca, a na rubnim dijelovima čuva se činjenicom da rubna korekcija pomiče krajnje rezne točke prema vertikalnim separatorima, ali ih ne prebacuje preko njih. Prijelaz iz A^{k},B^{k} u A^{k+1},B^{k+1} zato ne uvodi novo sjecište između lanaca. Indukcijom slijedi da se za svaki k\geq 0 lanci A^{k} i B^{k} sijeku samo u P^{+} i P^{-}.
\ \blacksquare
Teorem 9. (Granična meka ćelija u vertikalnom slučaju) Neka je C dopušten konveksan poligon kompatibilan s vertikalnim tokom i neka je 0\lt \rho\lt 1/3. Tada iterativno rezanje vrhova s rubnom korekcijom generira niz poligonalnih likova C^{k}\subseteq C čiji rubovi konvergiraju prema jednostavnoj zatvorenoj krivulji koja je glatka izvan istaknutih rubnih točaka P^{+} i P^{-}. U točkama P^{+} i P^{-} dva se granična luka susreću tangencijalno, sa zajedničkim vertikalnim tangentnim smjerom. Granični oblik je zato ravninska meka ćelija sadržana u početnom poligonu C.
Dokaz. Prvo pokazujemo da postupak doista određuje granične rubne lukove. Na unutarnjim dijelovima lanaca postupak se podudara sa standardnim postupkom rezanja vrhova, pa konvergencija tih dijelova slijedi iz poznatih rezultata o postupku rezanja vrhova [3, 4, 5] . Rubna korekcija mijenja samo prve i zadnje rezne točke svakog lanca, i to afinom djelomičnom projekcijom prema fiksnim vertikalnim pravcima kroz P^{+} i P^{-}. Ta korekcija ne narušava kontraktivni karakter rezanja vrhova na rubnim dijelovima, nego dodatno smanjuje horizontalnu komponentu krajnjih segmenata. Stoga i oba cijela rubna lanca konvergiraju prema graničnim lukovima s krajnjim točkama P^{+} i P^{-}.
Po Propoziciji7 , svi poligonalni likovi C^{k} sadržani su u početnom poligonu C. Budući da je C zatvoren, granična krivulja dobivena kao limes tih aproksimacija ostaje u C.
Na unutarnjim dijelovima dvaju rubnih lanaca postupak se podudara sa standardnim postupkom rezanja vrhova. Prema Lemi5 , ti dijelovi konvergiraju prema glatkim graničnim lukovima. Preostaje provjeriti ponašanje u istaknutim rubnim točkama. Po Lemi 6 , prvi segmenti uz P^{+}, kao i zadnji segmenti uz P^{-}, približavaju se vertikalnom smjeru. Isti zaključak vrijedi za oba rubna lanca, pa se granični lukovi u P^{+} i P^{-} susreću tangencijalno, sa zajedničkim vertikalnim tangentnim smjerom.
Jednostavnost granične krivulje slijedi iz odvojenosti lanaca. Po Lemi8 , za svaki konačni korak k lanci A^{k} i B^{k} sijeku se samo u zajedničkim krajnjim točkama P^{+} i P^{-}. Budući da postupak na svakom lancu čuva poredak točaka, a granični lukovi nastaju kao limesi tih poligonalnih lanaca, ni u limesu ne nastaje novo sjecište između dvaju lukova. Granična krivulja je zato jednostavna zatvorena krivulja.
Granična krivulja je glatka izvan točaka P^{+} i P^{-}, dok se u tim dvjema točkama pripadni rubni lukovi susreću tangencijalno. Prema Definiciji1 , granični oblik je ravninska meka ćelija. Budući da granična krivulja leži u konveksnom skupu C, i područje koje omeđuje sadržano je u C.
Po Propoziciji
Na unutarnjim dijelovima dvaju rubnih lanaca postupak se podudara sa standardnim postupkom rezanja vrhova. Prema Lemi
Jednostavnost granične krivulje slijedi iz odvojenosti lanaca. Po Lemi
Granična krivulja je glatka izvan točaka P^{+} i P^{-}, dok se u tim dvjema točkama pripadni rubni lukovi susreću tangencijalno. Prema Definiciji
\ \blacksquare
Korolar 10. (Proizvoljan smjer toka) Neka je v\neq 0 i 0\lt \rho\lt 1/3. Odaberimo rotaciju R takvu da
4 ) na R(C), a zatim vraćanjem rezultata rotacijom R^{-1}. Dobiveni granični oblik je meka ćelija sadržana u početnom poligonu C, a zajednički tangentni pravci u istaknutim rubnim točkama paralelni su sa smjerom v.
Rv=(0,-\Vert v\Vert ).
Ako je R(C) dopušten i kompatibilan u vertikalnom smjeru, tada se algoritam za smjer v dobiva primjenom vertikalnog algoritma (Definicija
Dokaz. Rotacije čuvaju konveksnost, jednostavnost krivulje, glatkoću, tangencijalnost i sadržanost [7, 8] . Zato se Teorem 9 može primijeniti na rotirani poligon R(C). Nakon primjene vertikalnog postupka, rotacija R^{-1} vraća dobiveni oblik u početni položaj i čuva sva navedena svojstva.
\ \blacksquare
Slika 5: Primjena postupka za proizvoljan smjer toka. Lijevo je prikazan početni poligon s odabranim smjerom v. U sredini je poligon rotiran tako da se vektor v preslika u vertikalni smjer (0,-\Vert v\Vert ); u tom se položaju provodi iterativno rezanje vrhova s rubnom korekcijom. Desno je dobivena meka ćelija vraćena u početni koordinatni sustav inverznom rotacijom.
Korolar
4Zaključak
U ovom radu opisujemo iterativni postupak kojim početni konveksni poligon transformiramo u ravninsku meku ćeliju.
U prvom dijelu rada definiramo preduvjete koje početni poligon mora zadovoljiti, objašnjavamo sâm algoritam te analiziramo njegovu složenost. Algoritam definiramo za vertikalni smjer toka, koji modelira djelovanje vanjskog erozivnog procesa. Zahtijevamo da početni konveksni poligon posjeduje jedinstveni najviši vrh P^{+} i najniži vrh P^{-}, uz barem jednu unutarnju točku u svakom od dvaju rubnih lanaca. Dodatno zahtijevamo kompatibilnost s tokom, kojom osiguravamo da vertikalni pravci koji prolaze kroz vrhove P^{+} i P^{-} budu sadržani unutar unutarnjih kutova poligona u tim točkama.
Standardnim rezanjem vrhova zaglađujemo unutarnje dijelove lanca, dok rubnom korekcijom, zasnovanom na ortogonalnoj projekciji reznih točaka uz P^{+} i P^{-} na odgovarajuće vertikalne pravce, postupno usmjeravamo granične segmente prema zajedničkoj vertikalnoj tangenti. Konačni rezultat algoritma jest nestanak klasičnog oštrog kuta i stvaranje zaglađenog šiljka u kojem se rubovi spajaju bez vidljivog prijeloma. Algoritam sadrži parametar \rho, koji određuje intenzitet lokalnog rezanja. Broj točaka koje opisuju rub ćelije raste eksponencijalno te nakon k iteracija iznosi O(2^{k}); no vizualno stabilne i glatke rezultate ipak postižemo već nakon malog broja koraka.
U drugom dijelu rada dokazujemo da algoritam proizvodi iterativni niz poligonalnih likova koji konvergiraju prema geometrijskom obliku što zadovoljava definiciju meke ćelije. Pokazujemo da unutarnji dijelovi rubnih lanaca konvergiraju prema glatkim lukovima, a da se smjerovi segmenata uz istaknute točke približavaju vertikali, čime jamčimo tangencijalnost graničnih lukova u P^{+} i P^{-}. Također dokazujemo da svi generirani likovi C^{k} ostaju sadržani u početnom konveksnom poligonu te garantiramo odvojenost rubnih lanaca kroz sve iteracije. Posljedično, granična krivulja ostaje jednostavna i zatvorena. Središnji rezultat poglavlja potvrđuje da je granični oblik, omeđen graničnom krivuljom, ravninska meka ćelija – glatka izvan P^{+} i P^{-}, dok se u tim točkama rubni lukovi susreću tangencijalno, odnosno kompatibilna je s izvornom geometrijom popločavanja.
Na kraju proširujemo algoritam na proizvoljan smjer toka primjenom rotacije koordinatnog sustava, čime svaki dopušteni konveksni poligon možemo transformirati u meku ćeliju čiji su šiljci uvijek usmjereni paralelno s v.
Budući da su meke ćelije kao formalni matematički objekt uvedene tek nedavno
Bibliografija
