Sierpinski kurva

Den aktuella versionen av sidan har ännu inte granskats av erfarna bidragsgivare och kan skilja sig väsentligt från versionen som granskades den 23 april 2020; kontroller kräver 2 redigeringar .

Sierpinski-kurvor är en rekursivt definierad sekvens av kontinuerliga slutna plana fraktalkurvor som upptäckts av Vaclav Sierpinski . Kurvan i gränsen vid fyller enhetskvadraten helt, så gränskurvan, även kallad Sierpinski-kurvan , är ett exempel på rymdfyllande kurvor .

Eftersom Sierpinski-kurvan fyller utrymmet är dess Hausdorff-dimension (i gränsen vid ) lika med . Euklidisk kurvlängd

är lika med ,

d.v.s. den växer exponentiellt i , och gränsen för området för regionen som omges av kurvan är kvadratisk (i den euklidiska metriken).

Curve use

Sierpinski-kurvan är användbar för vissa praktiska tillämpningar eftersom den är mer symmetrisk än andra allmänt betraktade rymdfyllande kurvor. Till exempel användes den som en grund för att snabbt konstruera en ungefärlig lösning på problemet med resande säljare (som letar efter den kortaste vägen runt givna punkter) - den heuristiska lösningen är att besöka punkterna i den sekvens i vilken de inträffar på Sierpinski kurva [1] . Implementeringen kräver två steg. Först beräknas den omvända positionen för varje punkt, sedan sorteras värdena. Denna idé användes för ett routingsystem för kommersiella fordon endast baserat på Rolodex- kort [2] .

Baserat på Sierpinski-kurvan kan vibrator eller tryckta antenndesigner implementeras [3] .

Kurvkonstruktion

Den rymdfyllande kurvan är en kontinuerlig mappning från enhetsintervall till enhetskvadrat och en (pseudo) omvänd mappning från enhetskvadrat till enhetsintervall. Ett sätt att konstruera en pseudo-invers mappning är som följer. Låt det nedre vänstra hörnet (0, 0) av enhetsrutan motsvara 0,0 (och 1,0). Sedan ska det övre vänstra hörnet av (0, 1) vara 0,25, det övre högra hörnet av (1, 1) ska vara 0,50 och det nedre högra hörnet av (1, 0) ska vara 0,75. Den omvända bilden av inre punkter beräknas med hjälp av kurvans rekursiva struktur. Nedan finns en Java-funktion som beräknar den relativa positionen för vilken punkt som helst på Sierpinski-kurvan (det vill säga pseudo-inversen). Funktionen tar koordinaterna för punkten (x, y) och vinklarna för den omslutande rätt likbenta triangeln (ax, ay), (bx, by) och (cx, cy) (Observera att enhetskvadraten är föreningen av två sådana trianglar). De återstående parametrarna bestämmer nivån av noggrannhet av beräkningar.

statisk lång sierp_pt2code ( dubbel axe , dubbel ay , dubbel bx , dubbel med , dubbel cx , dubbel cy , int nuvarandeLevel , int maxLevel , lång kod , dubbel x , dubbel y ) { if ( aktuell nivå <= maxNivå ) { aktuellLevel ++ ; 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 * kod + 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 ); } } returkod ; _ }

Följande Java -applet ritar Sierpinski- kurvan med fyra ömsesidigt rekursiva metoder (metoder som anropar varandra):

importera java.applet.Applet ; importera java.awt.Graphics ; importera java.awt.Image ; offentlig klass SierpinskyCurve utökar Applet { privat SimpleGraphics sg = null ; privat int dist0 = 128 , dist ; privat bild offscrBuf ; privat grafik offscrGfx ; public void init () { sg = new SimpleGraphics ( getGraphics ()); dist0 = 100 ; ändra storlek ( 4 * dist0 , 4 * dist0 ); } public void update ( Graphics g ) { paint ( g ); } public void paint ( Grafik g ) { if ( g == null ) kasta nytt NullPointerException (); if ( offscrBuf == null ) { offscrBuf = createImage ( this . getWidth (), this . getHeight ()); offscrGfx = offscrBuf . getGraphics (); sg . setGraphics ( offscrGfx ); } int nivå = 3 ; dist = dist0 ; for ( int i = nivå ; i > 0 ; i -- ) dist /= 2 ; sg . goToXY ( 2 * dist , dist ); sierpA ( nivå ); // starta rekursion sg . lineRel ( 'X' , + dist , + dist ); sierpB ( nivå ); // starta rekursion sg . lineRel ( 'X' , - dist , + dist ); sierpC ( nivå ); // starta rekursion sg . lineRel ( 'X' , - dist , - dist ); sierpD ( nivå ); // starta rekursion sg . lineRel ( 'X' , + dist , - dist ); g . drawImage ( offscrBuf , 0 , 0 , detta ); } privat void sierpA ( int nivå ) { if ( nivå > 0 ) { sierpA ( nivå - 1 ); sg . lineRel ( 'A' , + dist , + dist ); sierpB ( nivå - 1 ); sg . lineRel ( 'A' , + 2 * dist , 0 ); sierpD ( nivå - 1 ); sg . lineRel ( 'A' , + dist , - dist ); sierpA ( nivå - 1 ); } } privat void sierpB ( int nivå ) { if ( nivå > 0 ) { sierpB ( nivå - 1 ); sg . lineRel ( 'B' , - dist , + dist ); sierpc ( nivå - 1 ); sg . lineRel ( 'B' , 0 , + 2 * dist ); sierpA ( nivå - 1 ); sg . lineRel ( 'B' , + dist , + dist ); sierpB ( nivå - 1 ); } } privat void sierpC ( int nivå ) { if ( nivå > 0 ) { sierpC ( nivå - 1 ); sg . lineRel ( 'C ' , -dist , -dist ) ; sierpD ( nivå - 1 ); sg . lineRel ( 'C' , - 2 * dist , 0 ); sierpB ( nivå - 1 ); sg . lineRel ( 'C' , - dist , + dist ); sierpc ( nivå - 1 ); } } privat void sierpD ( int nivå ) { if ( nivå > 0 ) { sierpD ( nivå - 1 ); sg . lineRel ( 'D' , + dist , - dist ); sierpA ( nivå - 1 ); sg . lineRel ( 'D' , 0 , - 2 * dist ); sierpc ( nivå - 1 ); sg . lineRel ( 'D ' , -dist , -dist ) ; sierpD ( nivå - 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 ) { detta . x = x ; detta . 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öljande logoprogram ritar en Sierpinski-kurva med hjälp av 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 även

Anteckningar

  1. ↑ Platzman, Bartholdi, 1989 .
  2. ↑ Bartholdi .
  3. ↑ Slyusar, V. Fractal Antennas. En i grunden ny typ av "trasiga" antenner. Del 2. . Elektronik: vetenskap, teknik, affärer. - 2007. - Nr 6. S. 82-89. (2007). Hämtad 22 april 2020. Arkiverad från originalet 3 april 2018.

Litteratur