Sierpinského křivka

Aktuální verze stránky ještě nebyla zkontrolována zkušenými přispěvateli a může se výrazně lišit od verze recenzované 23. dubna 2020; kontroly vyžadují 2 úpravy .

Sierpinského křivky jsou rekurzivně definovanou sekvencí souvislých fraktálových křivek v uzavřené rovině objevených Václavem Sierpinskim . Křivka v limitě v zcela vyplňuje jednotkový čtverec, takže limitní křivka, nazývaná také Sierpinského křivka , je příkladem křivek vyplňujících prostor . $n\rightarrow \infty$

Protože Sierpinského křivka vyplňuje prostor, její Hausdorffova dimenze (v limitě v ) je rovna . Délka euklidovské křivky $n\rightarrow \infty$ $2$

{\displaystyle S_{n))

se rovná ,

l_{n}={2 \over 3}(1+{\sqrt {2}})2^{n}-{1 \over 3}(2-{\sqrt {2}}){1 \přes 2^{n}}

tj. roste exponenciálně v , a limit pro oblast oblasti ohraničené křivkou je čtverec (v euklidovské metrice). $n$ $n\rightarrow \infty$ ${\displaystyle S_{n))$ $5/12$

Použití křivky

Sierpinského křivka je užitečná pro některé praktické aplikace, protože je symetričtější než jiné běžně uvažované křivky vyplňující prostor. Byl například použit jako základ pro rychlé sestavení přibližného řešení problému obchodního cestujícího (který hledá nejkratší cestu kolem daných bodů) - heuristickým řešením je navštívit body v pořadí, v jakém se vyskytují na Sierpinski. křivka [1] . Implementace vyžaduje dva kroky. Nejprve se vypočítá inverzní poloha každého bodu a poté se seřadí hodnoty. Tato myšlenka byla použita pro směrovací systém užitkových vozidel založený pouze na kartách Rolodex [2] .

Na základě Sierpinského křivky lze implementovat návrhy vibrátorů nebo tištěných antén [3] .

Konstrukce křivky

Křivka vyplňování prostoru je souvislé zobrazení z jednotkového intervalu na jednotkový čtverec a (pseudo) inverzní zobrazení z jednotkového čtverce na jednotkový interval. Jedním ze způsobů, jak vytvořit pseudoinverzní mapování, je následující. Nechť levý dolní roh (0, 0) jednotkového čtverce odpovídá 0,0 (a 1,0). Pak by měl být levý horní roh (0, 1) 0,25, pravý horní roh (1, 1) by měl být 0,50 a pravý dolní roh (1, 0) 0,75. Inverzní obraz vnitřních bodů se vypočítá pomocí rekurzivní struktury křivky. Níže je funkce Java, která vypočítává relativní polohu libovolného bodu na Sierpinského křivce (tedy pseudoinverzní). Funkce bere souřadnice bodu (x, y) a úhly obklopujícího pravoúhlého rovnoramenného trojúhelníku (ax, ay), (bx, by) a (cx, cy) (Všimněte si, že jednotkový čtverec je sjednocením dva takové trojúhelníky). Zbývající parametry určují úroveň přesnosti výpočtů.

static long sierp_pt2code ( double ax , double ay , double bx , double by , double cx , double cy , int currentLevel , int maxLevel , long code , double x , double y ) { if ( currentLevel <= maxLevel ) { currentLevel ++ ; if (( sqr ( x - ax ) + sqr ( y - ay )) < ( sqr ( x - cx ) + sqr ( y - cy ))) { kód = sierp_pt2code ( ax , ay , ( ax + cx ) / 2.0 , ( ay + cy ) / 2.0 , bx , by , currentLevel , maxLevel , 2 * kód + 0 , x , y ); } else { kód = sierp_pt2code ( bx , by , ( ax + cx ) / 2.0 , ( ay + cy ) / 2.0 , cx , cy , currentLevel , maxLevel , 2 * kód + 1 , x , y ); } } návratový kód ; }

Následující Java applet kreslí Sierpinského křivku pomocí čtyř vzájemně rekurzivních metod (metody, které se navzájem volají):

import java.applet.Applet ; import java.awt.Graphics ; import java.awt.Image ; public class SierpinskyCurve rozšiřuje Applet { private SimpleGraphics sg = null ; private int dist0 = 128 , dist ; soukromý Obrázek offscrBuf ; private Graphics offscrGfx ; public void init () { sg = new SimpleGraphics ( getGraphics ()); dist0 = 100 ; změna velikosti ( 4 * dist0 , 4 * dist0 ); } public void update ( Graphics g ) { paint ( g ); } public void paint ( grafika g ) { if ( g == null ) vyvolá novou výjimku NullPointerException ( ); if ( offscrBuf == null ) { offscrBuf = createImage ( this . getWidth (), this . getHeight ()); offscrGfx = offscrBuf . getGraphics (); sg . setGraphics ( offscrGfx ); } int úroveň = 3 ; dist = dist0 ; for ( int i = hladina ; i > 0 ; i -- ) dist /= 2 ; sg . goToXY ( 2 * dist , dist ); sierpA ( hladina ); // spuštění rekurze sg . lineRel ( 'X' , + dist , + dist ); sierpB ( hladina ); // spuštění rekurze sg . lineRel ( 'X' , - dist , + dist ); sierpC ( úroveň ); // spuštění rekurze sg . lineRel ( 'X' , - dist , - dist ); sierpD ( úroveň ); // spuštění rekurze sg . lineRel ( 'X' , + dist , - dist ); g . drawImage ( offscrBuf , 0 , 0 , toto ); } private void sierpA ( int level ) { if ( level > 0 ) { sierpA ( level - 1 ); sg . lineRel ( 'A' , + dist , + dist ); sierpB ( úroveň - 1 ); sg . lineRel ( 'A' , + 2 * dist , 0 ); sierpD ( úroveň - 1 ); sg . lineRel ( 'A' , + dist , - dist ); sierpA ( úroveň - 1 ); } } private void sierpB ( int level ) { if ( level > 0 ) { sierpB ( level - 1 ); sg . lineRel ( 'B' , - dist , + dist ); sierpc ( úroveň - 1 ); sg . lineRel ( 'B' , 0 , + 2 * dist ); sierpA ( úroveň - 1 ); sg . lineRel ( 'B' , + dist , + dist ); sierpB ( úroveň - 1 ); } } private void sierpC ( int level ) { if ( level > 0 ) { sierpC ( level - 1 ); sg . lineRel ( 'C ' , -dist , -dist ) ; sierpD ( úroveň - 1 ); sg . lineRel ( 'C' , -2 * dist , 0 ) ; sierpB ( úroveň - 1 ); sg . lineRel ( 'C' , - dist , + dist ); sierpc ( úroveň - 1 ); } } private void sierpD ( int level ) { if ( level > 0 ) { sierpD ( level - 1 ); sg . lineRel ( 'D' , + dist , - dist ); sierpA ( úroveň - 1 ); sg . lineRel ( 'D' , 0 , - 2 * dist ); sierpc ( úroveň - 1 ); sg . lineRel ( 'D ' , -dist , -dist ) ; sierpD ( úroveň - 1 ); } } } class SimpleGraphics { private Graphics g = null ; private int x = 0 , y = 0 ; public SimpleGraphics ( Graphics g ) { setGraphics ( g ); } public void setGraphics ( Graphics g ) { this . g = g ; } public void goToXY ( int x , int y ) { this . x = x ; toto . y = y _ } public void lineRel ( char s , int deltaX , int deltaY ) { g . drawLine ( x , y , x + deltaX , y + deltaY ); x += deltaX ; y + = delta Y ; } }

Následující program Logo kreslí Sierpinského křivku pomocí rekurze .

to half.sierpinski :size :level if :level = 0 [forward :size stop] half.sierpinski :size :level - 1 left 45 forward :size * sqrt 2 left 45 half.sierpinski :size :level - 1 right 90 forward :size right 90 half.sierpinski :size :level - 1 left 45 forward :size * sqrt 2 left 45 half.sierpinski :size :level - 1 end to sierpinski :size :level half.sierpinski :size :level right 90 forward :size right 90 half.sierpinski :size :level right 90 forward :size right 90 end

Viz také

Hilbertova křivka
Kochova křivka
Mooreova křivka
Peanova křivka
Sierpinski tip
Seznam fraktálů podle Hausdorffovy dimenze
rekurzivní funkce
Sierpinského trojúhelník

Poznámky

↑ Platzman, Bartholdi, 1989 .
↑ Bartholdi .
↑ Slyusar, V. Fraktální antény. Zásadně nový typ „rozbitých“ antén. Část 2 . Elektronika: věda, technika, obchod. - 2007. - č. 6. S. 82-89. (2007). Staženo 22. dubna 2020. Archivováno z originálu 3. dubna 2018. (neurčitý)

Literatura

Loren K. Platzman, John J. Bartholdi III. Křivky vyplňující prostor a problém rovinného cestujícího prodejce // Journal of the Association of Computing Machinery. - 1989. - T. 36 , no. 4 . - S. 719-737 .
John J. Bartholdi III. Některé kombinatorické aplikace křivek vyplňování prostoru . — Georgia Institute of Technology . Archivováno z originálu 3. srpna 2012.

Křivky

Definice

Transformováno

Nerovinné

Plochá
algebraika

Kuželosečky

3. řád ( kubický )

Eliptický	Eliptická křivka Jacobiho eliptické funkce Eliptický integrál Eliptické funkce
jiný	Verziera Agnesi Kartézský list Maclaurinův trisektor Chirnhaus Ophiurida Strofoid Semikubická parabola Trojzubec Cissoid of Diocles

4. řádu

Lemniscates

Přiblížení

Spline
beziers

Cykloidní

jiný

Pokřivená farma

Ploché
transcendentální

Spirály	Archimedov Farma Galilee Hyperbolický "Hůlka" Zlatý klotoidní logaritmický sinusový
Cykloidní	trochoidní Cykloidní Epitrochoidní Epicykloida Hypotrochoidní Hypocykloidní Kvazitrochoidní "Růže" quadrifolium Rychlý sestup (brachistochronní, cykloidní oblouk)
jiný	Quadratrix kochleoidní Honit traktor trochoidní řetězová linka obráceně klenutý konstantní šířka sinusoida Ribokura Super formule Superelipsa Reuleauxův trojúhelník polygon Lissajousovy postavy

fraktál

Jednoduchý	Gilbert Gosper dračí křivka Koch Levy Minkowski Peano Sierpinsky
topologické	Ubrousek Sierpinski Koberec Sierpinski Houba Menger kruhový fraktál Koberec Apollonius