Po částech lineární pokračování

Zjednodušené pokračovánínebo po částech lineární pokračování (Allgower a Georg),^[1]^[2] je jeden parametr metoda pokračování který je vhodný pro malé a střední mezery. Algoritmus byl zobecněn tak, aby vypočítal vícerozměrná potrubí od (Allgower a Gnutzman)^[3] a (Allgower a Schmidt).^[4]

Algoritmus pro kreslení obrysů je zjednodušený pokračovací algoritmus, a protože je snadno vizualizovatelný, slouží jako dobrý úvod do algoritmu.

Obrysové vykreslování

Problémem obrysového vykreslování je najít nuly (obrysy) ${displaystyle f (x, y) = 0,}$ ( ${displaystyle f (cdot),}$ hladká skalární funkce) ve čtverci ${displaystyle 0leq xleq 1,0leq yleq 1,}$ ,

Příklad obrysů Obrysy, trojrozměrný pohled

Čtverec je rozdělen na malé trojúhelníky, obvykle zavedením bodů v rozích pravidelné čtvercové sítě ${displaystyle ih_ {x} leq xleq (i + 1) h_ {x},}$ , ${displaystyle jh_ {y} leq yleq (j + 1) h_ {y},}$ , vytvoření tabulky hodnot ${displaystyle f (x_ {i}, y_ {j}),}$ na každém rohu ${displaystyle (i, j),}$ a poté rozdělíte každý čtverec na dva trojúhelníky. Hodnota ${displaystyle f (x_ {i}, y_ {j}),}$ v rozích trojúhelníku definuje jedinečný lineární interpolant Piecewise ${displaystyle lf (x, y),}$ na ${displaystyle f (cdot),}$ přes každý trojúhelník. Jeden způsob psaní tohoto interpolantu na trojúhelník s rohy ${displaystyle (x_ {0}, y_ {0}), ~ (x_ {1}, y_ {1}), ~ (x_ {2}, y_ {2}),}$ je jako množina rovnic

{displaystyle (x, y) = (x_ {0}, y_ {0}) + (x_ {1} -x_ {0}, y_ {1} -y_ {0}) s + (x_ {2} -x_ { 0}, y_ {2} -y_ {0}) t,}

{displaystyle 0leq s,}

{displaystyle 0leq t,}

{displaystyle s + tleq 1,}

{displaystyle lf (x, y) = f (x_ {0}, y_ {0}) + (f (x_ {1}, y_ {1}) - f (x_ {0}, y_ {0})) s + (f (x_ {2}, y_ {2}) - f (x_ {0}, y_ {0})) t,}

První čtyři rovnice lze vyřešit ${displaystyle (s, t),}$ (toto mapuje původní trojúhelník na trojúhelník pravé jednotky), pak zbývající rovnice dává interpolovanou hodnotu ${displaystyle f (cdot),}$ . Po celé síti trojúhelníků je tento po částech lineární interpolant spojitý.

Příklad triangulace a označených vrcholů Lineární interpolant, trojrozměrný pohled

Obrys interpolantu na jednotlivém trojúhelníku je úsečka (je to interval na průsečíku dvou rovin). Rovnici pro přímku lze nalézt, avšak body, kde čára protíná okraje trojúhelníku, jsou koncovými body úsečkového segmentu.

Unikátní lineární interpolant na simplexu a jeho nulová množina Obrys lineárního interpolantu nad trojúhelníkem

Obrys po částech lineárního interpolantu je sada křivek vytvořených z těchto úseček. Jakýkoli bod na okraji se připojuje ${displaystyle (x_ {0}, y_ {0}),}$ a ${displaystyle (x_ {1}, y_ {1}),}$ lze psát jako

{displaystyle (x, y) = (x_ {0}, y_ {0}) + t (x_ {1} -x_ {0}, y_ {1} -y_ {0}) ,,}

s ${displaystyle t,}$ v ${displaystyle (0,1),}$ a lineární interpolant přes okraj je

{displaystyle fsim f_ {0} + t (f_ {1} -f_ {0}),}

Takže nastavení ${displaystyle f = 0,}$

{displaystyle t = -f_ {0} / (f_ {1} -f_ {0}),}

a

{displaystyle (x, y) = (x_ {0}, y_ {0}) - f_ {0} * (x_ {1} -x_ {0}, y_ {1} -y_ {0}) / (f_ { 1} -f_ {0}),}

Protože to záleží pouze na hodnotách na hraně, každý trojúhelník, který sdílí tuto hranu, vytvoří stejný bod, takže kontura bude spojitá. Každý trojúhelník lze testovat samostatně, a pokud jsou všechny zaškrtnuty, lze najít celou sadu obrysových křivek.

Kusové lineární pokračování je podobné obrysovému vykreslování (Dobkin, Levy, Thurston a Wilks),^[5] ale ve vyšších dimenzích. Algoritmus je založen na následujících výsledcích:

Lemma 1

Pokud F (x) mapuje ${displaystyle mathbb {R} ^ {n}}$ do ${displaystyle mathbb {R} ^ {n-1}}$ , existuje jedinečný lineární interpolant na '(n-1)' - rozměrné simplexní což souhlasí s hodnotami funkcí na vrcholech simplexu.

An '(n-1)' - rozměrný simplex má n vrcholů a funkce F každému přiřadí 'n'-vektor. Simplex je konvexní a jakýkoli bod v simplexu je a konvexní kombinace vrcholů. To je:

Pokud je x ve vnitřku (n-1) -dimenzionálního simplexu s n vrcholy ${displaystyle v_ {i}}$ , pak existují pozitivní skaláry ${displaystyle 0$ takhle

{displaystyle mathbf {x} = součet _ {i} alfa _ {i} mathbf {v} _ {i}}

{displaystyle sum _ {i} alpha _ {i} = 1.,}

Pokud jsou vrcholy simplexu lineárně nezávislé nezáporné skaláry ${displaystyle alpha}$ jsou pro každý bod x jedinečné a nazývají se barycentrické souřadnice z x. Určují hodnotu jedinečnosti interpolant podle vzorce:

{displaystyle LF = součet _ {i} alfa _ {i} F (mathbf {v} _ {i})}

Lemma 2

Lze otestovat (n-1) -dimenzionální simplex, abychom zjistili, zda obsahuje počátek.

V zásadě existují dva testy. Ten, který byl poprvé použit, označuje vrcholy simplexu vektorem znamének (+/-) souřadnic vrcholu. Například vrchol (.5, -. 2,1.) Bude označen (+, -, +). Je povolen simplex úplně označeno pokud existuje vrchol, jehož štítek začíná řetězcem znaků „+“ o délce 0,1,2,3,4, ... n. Úplně označený simplex obsahuje sousední oblast původu. To může být překvapivé, ale základem tohoto výsledku je, že pro každou souřadnici zcela označeného simplexu existuje vektor s „+“ a další s „-“. Jinými slovy, nejmenší kostka s hranami rovnoběžnými s osami souřadnic, která pokrývá simplex, má dvojice ploch na opačných stranách 0. (tj. „+“ A „-“ pro každou souřadnici).

Druhý přístup se nazývá vektorové označení. Je založen na barycentrických souřadnicích vrcholů simplexu. Prvním krokem je najít barycentrické souřadnice počátku a poté test, který simplex obsahuje počátek, je prostě to, že všechny barycentrické souřadnice jsou kladné a součet je menší než 1.

Lemma 3

Existuje triangulace (Coxeter-Freudenthal-Kuhnova triangulace [1]), která je neměnná pod operací otočení ${displaystyle P_ {v_ {i}} (v_ {0}, v_ {1}, ..., v_ {n}): = (v_ {0}, v_ {1}, ..., v_ {i- 1}, {ilde {v}} _ {i}, v_ {i + 1}, ..., v_ {n})}$ kde ${displaystyle {ilde {v}} _ {i} = left {{egin {array} {lcl} v_ {1} + v_ {n} -v_ {0} && i = 0 v_ {i + 1} + v_ { i-1} -v_ {i} & qquad qquad & 0 v_ {n-1} + v_ {0} -v_ {n} && i = n end {pole}} v pořádku.}$

První krok trojrozměrného zjednodušeného pokračování Druhý krok trojrozměrného zjednodušeného pokračování

Reference

^ Eugene L. Allgower, K. Georg, „Úvod do numerických metod pokračování“, SIAM Classics v aplikované matematice 45, 2003.
^ E. L. Allgower, K. Georg, „Zjednodušené a pokračovací metody přibližování pevných bodů a řešení soustav rovnic“, Recenze SIAM, Svazek 22, 28-85, 1980.
^ Eugene L. Allgower, Stefan Gnutzmann, „Algoritmus pro kusovou lineární aproximaci implicitně definovaných dvourozměrných povrchů“, Časopis SIAM o numerické analýze, Svazek 24, číslo 2, 452-469, 1987.
^ Eugene L. Allgower, Phillip H. Schmidt, „Algoritmus pro kusově lineární aproximaci implicitně definovaného potrubí“, Časopis SIAM o numerické analýze, Díl 22, číslo 2, 322-346, duben 1985.
^ David P. Dobkin, Silvio V. F. Levy, William P. Thurston a Allan R. Wilks, „Sledování obrysu lineárními aproximacemi po částech“, Transakce ACM v grafice, 9(4) 389-423, 1990.

[one-1] Eugene L. Allgower, K. Georg, „Úvod do numerických metod pokračování“, SIAM Classics v aplikované matematice 45, 2003.

[three-2] E. L. Allgower, K. Georg, „Zjednodušené a pokračovací metody přibližování pevných bodů a řešení soustav rovnic“, Recenze SIAM, Svazek 22, 28-85, 1980.

[two-3] Eugene L. Allgower, Stefan Gnutzmann, „Algoritmus pro kusovou lineární aproximaci implicitně definovaných dvourozměrných povrchů“, Časopis SIAM o numerické analýze, Svazek 24, číslo 2, 452-469, 1987.

[four-4] Eugene L. Allgower, Phillip H. Schmidt, „Algoritmus pro kusově lineární aproximaci implicitně definovaného potrubí“, Časopis SIAM o numerické analýze, Díl 22, číslo 2, 322-346, duben 1985.

[five-5] David P. Dobkin, Silvio V. F. Levy, William P. Thurston a Allan R. Wilks, „Sledování obrysu lineárními aproximacemi po částech“, Transakce ACM v grafice, 9(4) 389-423, 1990.

[1]

[2]

[3]

[4]

[5]