Curba Sierpinski

Versiunea actuală a paginii nu a fost încă examinată de colaboratori experimentați și poate diferi semnificativ de versiunea revizuită pe 23 aprilie 2020; verificările necesită 2 modificări .

Curbele Sierpinski sunt o secvență definită recursiv de curbe fractale plane închise continue descoperite de Vaclav Sierpinski . Curba din limită la umple complet pătratul unității, astfel încât curba limită, numită și curba Sierpinski , este un exemplu de curbe de umplere a spațiului . $n\rightarrow \infty$

Deoarece curba Sierpinski umple spațiul, dimensiunea lui Hausdorff (în limita la ) este egală cu . Lungimea curbei euclidiene $n\rightarrow \infty$ $2$

S_{n)

este egal cu ,

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

adică crește exponențial în , iar limita pentru aria regiunii închise de curbă este pătrată (în metrica euclidiană). $n$ $n\rightarrow \infty$ $S_{n)$ $5/12$

Utilizarea curbei

Curba Sierpinski este utilă pentru unele aplicații practice, deoarece este mai simetrică decât alte curbe de umplere a spațiului considerate în mod obișnuit. De exemplu, a fost folosit ca bază pentru construirea rapidă a unei soluții aproximative la problema vânzătorului ambulant (care caută ruta cea mai scurtă în jurul punctelor date) - soluția euristică este de a vizita punctele din secvența în care acestea apar pe Sierpinski. curba [1] . Implementarea necesită doi pași. Mai întâi, se calculează poziția inversă a fiecărui punct, apoi se sortează valorile. Această idee a fost folosită pentru un sistem de rutare a vehiculelor comerciale bazat doar pe carduri Rolodex [2] .

Pe baza curbei Sierpinski, pot fi implementate modele de vibratoare sau antene imprimate [3] .

Construcția curbei

Curba de umplere a spațiului este o mapare continuă de la un interval de unitate la unitatea de pătrat și o mapare (pseudo) inversă de la unitatea de patrat la unitatea de interval. O modalitate de a construi o mapare pseudo-inversă este următoarea. Fie colțul din stânga jos (0, 0) al pătratului unității să corespundă cu 0,0 (și 1,0). Apoi colțul din stânga sus al (0, 1) ar trebui să fie 0,25, colțul din dreapta sus al (1, 1) ar trebui să fie 0,50, iar colțul din dreapta jos al (1, 0) ar trebui să fie 0,75. Imaginea inversă a punctelor interioare este calculată folosind structura recursivă a curbei. Mai jos este o funcție Java care calculează poziția relativă a oricărui punct de pe curba Sierpinski (adică pseudo-inversa). Funcția ia coordonatele punctului (x, y) și unghiurile triunghiului dreptunghic isoscel care înconjoară (ax, ay), (bx, by) și (cx, cy) (Rețineți că unitatea de pătrat este uniunea dintre două astfel de triunghiuri). Parametrii rămași determină nivelul de precizie al calculelor.

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 ))) { cod = sierp_pt2code ( ax , ay , ( ax + cx ) / 2.0 , ( ay + cy ) / 2.0 , bx , by , currentLevel , maxLevel , 2 * cod + 0 , x , y ); } else { cod = sierp_pt2code ( bx , by , ( ax + cx ) / 2.0 , ( ay + cy ) / 2.0 , cx , cy , currentLevel , maxLevel , 2 * cod + 1 , x , y ); } } cod de retur ; }

Următorul applet Java desenează curba Sierpinski folosind patru metode recursive reciproc (metode care se apelează reciproc):

import java.applet.Applet ; import java.awt.Graphics ; import java.awt.Image ; clasă publică SierpinskyCurve extinde Applet { private SimpleGraphics sg = null ; private int dist0 = 128 , dist ; private Image offscrBuf ; Grafică privată offscrGfx ; public void init () { sg = new SimpleGraphics ( getGraphics ()); dist0 = 100 ; redimensionare ( 4 * dist0 , 4 * dist0 ); } public void update ( Graphics g ) { paint ( g ); } vopsea public void ( Grafică g ) { if ( g == null ) aruncă o nouă excepție NullPointerException (); if ( offscrBuf == null ) { offscrBuf = createImage ( this . getWidth (), this . getHeight ()); offscrGfx = offscrBuf . getGraphics (); sg . setGraphics ( offscrGfx ); } nivel int = 3 ; dist = dist0 ; pentru ( int i = nivel ; i > 0 ; i -- ) dist /= 2 ; sg . goToXY ( 2 * dist , dist ); sierpA ( nivel ); // începe recursiunea sg . lineRel ( 'X' , + dist , + dist ); sierpB ( nivel ); // începe recursiunea sg . lineRel ( 'X' , - dist , + dist ); sierpC ( nivel ); // începe recursiunea sg . lineRel ( 'X' , - dist , - dist ); sierpD ( nivel ); // începe recursiunea sg . lineRel ( 'X' , + dist , - dist ); g . drawImage ( offscrBuf , 0 , 0 , this ); } private void sierpA ( int level ) { if ( level > 0 ) { sierpA ( level - 1 ); sg . lineRel ( 'A' , + dist , + dist ); sierpB ( nivel - 1 ); sg . lineRel ( 'A' , + 2 * dist , 0 ); sierpD ( nivel - 1 ); sg . lineRel ( 'A' , + dist , - dist ); sierpA ( nivel - 1 ); } } private void sierpB ( int level ) { if ( level > 0 ) { sierpB ( level - 1 ); sg . lineRel ( 'B' , - dist , + dist ); sierpc ( nivel - 1 ); sg . lineRel ( 'B' , 0 , + 2 * dist ); sierpA ( nivel - 1 ); sg . lineRel ( 'B' , + dist , + dist ); sierpB ( nivel - 1 ); } } private void sierpC ( int level ) { if ( level > 0 ) { sierpC ( level - 1 ); sg . lineRel ( 'C ' , -dist , -dist ) ; sierpD ( nivel - 1 ); sg . lineRel ( 'C' , - 2 * dist , 0 ); sierpB ( nivel - 1 ); sg . lineRel ( 'C' , - dist , + dist ); sierpc ( nivel - 1 ); } } private void sierpD ( int level ) { if ( level > 0 ) { sierpD ( level - 1 ); sg . lineRel ( 'D' , + dist , - dist ); sierpA ( nivel - 1 ); sg . lineRel ( 'D' , 0 , - 2 * dist ); sierpc ( nivel - 1 ); sg . lineRel ( 'D ' , -dist , -dist ) ; sierpD ( nivel - 1 ); } } } class SimpleGraphics { private Graphics g = null ; private int x = 0 , y = 0 ; public SimpleGraphics ( Graphics g ) { setGraphics ( g ); } public void setGraphics ( Grafică g ) { this . g = g ; } public void goToXY ( int x , int y ) { this . x = x ; aceasta . y = y _ } public void lineRel ( char s , int deltaX , int deltaY ) { g . drawLine ( x , y , x + deltaX , y + deltaY ); x += deltaX ; y += delta Y ; } }

Următorul program Logo desenează o curbă Sierpinski folosind recursiunea .

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

Vezi și

curba Hilbert
curba Koch
curba Moore
Curba Peano
pont Sierpinski
Lista fractalilor după dimensiunea Hausdorff
functie recursiva
triunghiul Sierpinski

Note

↑ Platzman, Bartholdi, 1989 .
↑ Bartholdi .
↑ Slyusar, V. Fractal Antennas. Un tip fundamental nou de antene „rupte”. Partea 2. . Electronică: știință, tehnologie, afaceri. - 2007. - Nr 6. S. 82-89. (2007). Consultat la 22 aprilie 2020. Arhivat din original pe 3 aprilie 2018. (nedefinit)

Literatură

Loren K. Platzman, John J. Bartholdi III. Curbele de umplere a spațiului și problema vânzătorului care călătorește plan // Journal of the Association of Computing Machinery. - 1989. - T. 36 , nr. 4 . - S. 719-737 .
Ioan J. Bartholdi III. Câteva aplicații combinatorii ale curbelor de umplere a spațiului . — Institutul de Tehnologie din Georgia . Arhivat din original pe 3 august 2012.

Curbe

Definiții

Transformat

Neplanare

algebric plat

Secțiuni conice

Ordinul 3 ( cubic )

Eliptic	Curba eliptică Funcții eliptice Jacobi Integrală eliptică Funcții eliptice
Alte	Verziera Agnesi Foaie carteziană Maclaurin trisector Chirnhaus Ophiurida Strofoid Parabola semimicubă Trident Cissoid din Diocle

Ordinul 4

Lemniscate

Apropiere

Splina
- B-spline
- Cub
- monospline
- Netezire
- Perfect
- Sihastrul
beziers

Cicloidală

Alte

Ferma strâmbă

Plat
transcendental

Spirale	Arhimedov Fermă Galileea hiperbolic "Baghetă" De aur clotoid logaritmică sinusoidal
Cicloidală	trohoid Cicloid Epitrohoid Epicicloid Hipotrocoid Hipocicloid Quasitrocoid "Trandafir" quadrifolium Coborâre rapidă (brahistocron, arc cicloid)
Alte	Quadratrix cohleoid urmarire tractor trohoid linie de lanț arcuit inversat latime constanta sinusoid Ribokura Super formula Superelipsă Triunghiul Reuleaux poligon figurile Lissajous

fractal

Simplu	Gilbert Gosper curba dragonului Koch Taxă Minkowski Peano Sierpinsky
topologic	Servetul Sierpinski covor Sierpinski Sponge Menger fractal circular covorul Apollonius