Sierpinski kurve

Den aktuelle version af siden er endnu ikke blevet gennemgået af erfarne bidragydere og kan afvige væsentligt fra den version , der blev gennemgået den 23. april 2020; checks kræver 2 redigeringer .

Sierpinski-kurver er en rekursivt defineret sekvens af kontinuerlige lukkede fraktale kurver opdaget af Vaclav Sierpinski . Kurven i grænsen ved fylder enhedskvadratet helt ud, så grænsekurven, også kaldet Sierpinski-kurven , er et eksempel på rumudfyldende kurver .

Da Sierpinski-kurven fylder rummet, er dens Hausdorff-dimension (i grænsen ved ) lig med . Euklidisk kurvelængde

er lig med ,

det vil sige, at det vokser eksponentielt i , og grænsen for arealet af området omgivet af kurven er kvadratisk (i den euklidiske metrik).

Kurvebrug

Sierpinski-kurven er nyttig til nogle praktiske anvendelser, fordi den er mere symmetrisk end andre almindeligt betragtede rumudfyldende kurver. For eksempel blev det brugt som grundlag for hurtigt at konstruere en omtrentlig løsning på det rejsende sælgerproblem (som leder efter den korteste rute omkring givne punkter) - den heuristiske løsning er at besøge punkterne i den rækkefølge, de forekommer på Sierpinski kurve [1] . Implementering kræver to trin. Først beregnes den omvendte position af hvert punkt, derefter sorteres værdierne. Denne idé blev brugt til et routingsystem for erhvervskøretøjer kun baseret på Rolodex -kort [2] .

Baseret på Sierpinski-kurven kan vibrator- eller trykte antennedesign implementeres [3] .

Kurvekonstruktion

Den rumfyldende kurve er en kontinuerlig afbildning fra enhedsinterval til enhedskvadrat og en (pseudo) omvendt afbildning fra enhedskvadrat til enhedsinterval. En måde at konstruere en pseudo-invers mapping på er som følger. Lad det nederste venstre hjørne (0, 0) af enhedsfirkanten svare til 0,0 (og 1,0). Så skal det øverste venstre hjørne af (0, 1) være 0,25, det øverste højre hjørne af (1, 1) skal være 0,50, og det nederste højre hjørne af (1, 0) skal være 0,75. Det omvendte billede af indre punkter beregnes ved hjælp af kurvens rekursive struktur. Nedenfor er en Java-funktion, der beregner den relative position af ethvert punkt på Sierpinski-kurven (det vil sige den pseudo-inverse). Funktionen tager koordinaterne for punktet (x, y) og vinklerne af den omsluttende ret ligebenede trekant (ax, ay), (bx, by) og (cx, cy) (Bemærk at enhedskvadraten er foreningen af to sådanne trekanter). De resterende parametre bestemmer niveauet af nøjagtighed af beregninger.

statisk lang sierp_pt2code ( dobbelt akse , dobbelt ay , dobbelt bx , dobbelt med , dobbelt cx , dobbelt cy , int nuværende niveau, int maxNiveau , lang kode , dobbelt x , dobbelt y ) { if ( aktuelt niveau < = maks . niveau ) { nuværende niveau ++ ; if (( sqr ( x - ax ) + sqr ( y - ay )) < ( sqr ( x - cx ) + sqr ( y - cy ))) { code = sierp_pt2code ( ax , ay , ( ax + cx ) / 2.0 , ( ay + cy ) / 2.0 , bx , by , currentLevel , maxLevel , 2 * kode + 0 , x , y ); } else { code = sierp_pt2code ( bx , by , ( ax + cx ) / 2.0 , ( ay + cy ) / 2.0 , cx , cy , currentLevel , maxLevel , 2 * code + 1 , x , y ); } } returkode ; _ }

Den følgende Java - applet tegner Sierpinski- kurven ved hjælp af fire gensidigt rekursive metoder (metoder, der kalder hinanden):

importer java.applet.Applet ; importer java.awt.Graphics ; importer java.awt.Image ; offentlig klasse SierpinskyCurve udvider Applet { private SimpleGraphics sg = null ; privat int dist0 = 128 , dist ; privat billede offscrBuf ; privat grafik offscrGfx ; public void init () { sg = new SimpleGraphics ( getGraphics ()); dist0 = 100 ; ændre størrelse ( 4 * dist0 , 4 * dist0 ); } public void update ( Graphics g ) { paint ( g ); } public void paint ( grafik g ) { if ( g == null ) smid ny NullPointerException (); if ( offscrBuf == null ) { offscrBuf = createImage ( this . getWidth (), this . getHeight ()); offscrGfx = offscrBuf . getGraphics (); sg . setGraphics ( offscrGfx ); } int niveau = 3 ; dist = dist0 ; for ( int i = niveau ; i > 0 ; i -- ) dist /= 2 ; sg . goToXY ( 2 * dist , dist ); sierpA ( niveau ); // start rekursion sg . lineRel ( 'X' , + dist , + dist ); sierpB ( niveau ); // start rekursion sg . lineRel ( 'X' , - dist , + dist ); sierpC ( niveau ); // start rekursion sg . lineRel ( 'X' , - dist , - dist ); sierpD ( niveau ); // start rekursion sg . lineRel ( 'X' , + dist , - dist ); g . drawImage ( offscrBuf , 0 , 0 , dette ); } private void sierpA ( int niveau ) { if ( niveau > 0 ) { sierpA ( niveau - 1 ); sg . lineRel ( 'A' , + dist , + dist ); sierpB ( niveau - 1 ); sg . lineRel ( 'A' , + 2 * dist , 0 ); sierpD ( niveau - 1 ); sg . lineRel ( 'A' , + dist , - dist ); sierpA ( niveau - 1 ); } } private void sierpB ( int niveau ) { if ( niveau > 0 ) { sierpB ( niveau - 1 ); sg . lineRel ( 'B' , - dist , + dist ); sierpc ( niveau - 1 ); sg . lineRel ( 'B' , 0 , + 2 * dist ); sierpA ( niveau - 1 ); sg . lineRel ( 'B' , + dist , + dist ); sierpB ( niveau - 1 ); } } private void sierpC ( int niveau ) { if ( niveau > 0 ) { sierpC ( niveau - 1 ); sg . lineRel ( 'C ' , -dist , -dist ) ; sierpD ( niveau - 1 ); sg . lineRel ( 'C' , - 2 * dist , 0 ); sierpB ( niveau - 1 ); sg . lineRel ( 'C' , - dist , + dist ); sierpc ( niveau - 1 ); } } private void sierpD ( int niveau ) { if ( niveau > 0 ) { sierpD ( niveau - 1 ); sg . lineRel ( 'D' , + dist , - dist ); sierpA ( niveau - 1 ); sg . lineRel ( 'D' , 0 , - 2 * dist ); sierpc ( niveau - 1 ); sg . lineRel ( 'D ' , -dist , -dist ) ; sierpD ( niveau - 1 ); } } } class SimpleGraphics { private Graphics g = null ; privat 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 ) { dette . x = x ; dette . y = y _ } public void lineRel ( char s , int deltaX , int deltaY ) { g . drawLine ( x , y , x + deltaX , y + deltaY ); x += deltaX ; y += delta Y ; } }

Følgende Logo -program tegner en Sierpinski-kurve ved hjælp af rekursion .

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

Se også

Noter

  1. ↑ Platzman, Bartholdi, 1989 .
  2. ↑ Bartholdi .
  3. ↑ Slyusar, V. Fractal Antennas. En fundamentalt ny type "knækkede" antenner. Del 2. . Elektronik: videnskab, teknologi, forretning. - 2007. - Nr. 6. S. 82-89. (2007). Hentet 22. april 2020. Arkiveret fra originalen 3. april 2018.

Litteratur