Sierpinski görbe

Az oldal jelenlegi verzióját még nem ellenőrizték tapasztalt közreműködők, és jelentősen eltérhet a 2020. április 23-án felülvizsgált verziótól ; az ellenőrzések 2 szerkesztést igényelnek .

A Sierpinski-görbék folyamatos zárt síkú fraktálgörbék rekurzívan meghatározott sorozata, amelyet Vaclav Sierpinski fedezett fel . A határérték görbéje teljesen kitölti az egységnégyzetet, így a határgörbe, amelyet Sierpinski-görbének is neveznek, a térkitöltő görbék példája .

Mivel a Sierpinski-görbe kitölti a teret, a Hausdorff-dimenziója (a határértékben ) egyenlő . Euklideszi görbe hossza

egyenlő ,

azaz exponenciálisan növekszik -ben , és a görbe által bezárt tartomány területének határa négyzet (az euklideszi metrikában).

Görbehasználat

A Sierpinski-görbe bizonyos gyakorlati alkalmazásokban hasznos, mert szimmetrikusabb, mint a többi általánosan elfogadott térkitöltő görbe. Például alapul szolgált arra, hogy gyorsan hozzávetőleges megoldást alkossunk az utazó eladó problémájára (amely a legrövidebb utat keresi adott pontok körül) – a heurisztikus megoldás az, hogy meglátogatjuk a pontokat abban a sorrendben, amelyben előfordulnak a Sierpinskin. görbe [1] . A megvalósítás két lépést igényel. Először az egyes pontok fordított helyzetét számítják ki, majd rendezik az értékeket. Ezt az ötletet használták a csak Rolodex kártyákon alapuló haszonjárművek útválasztó rendszeréhez [2] .

A Sierpinski-görbe alapján vibrátoros vagy nyomtatott antennatervek valósíthatók meg [3] .

Görbeépítés

A térkitöltési görbe egy folyamatos leképezés egységnyi intervallumról egységnégyzetre és (pszeudo) inverz leképezés egységnégyzetről egységintervallumra. A pszeudo-inverz leképezés megalkotásának egyik módja a következő. Az egységnégyzet bal alsó sarka (0, 0) feleljen meg 0.0-nak (és 1.0). Ekkor a (0, 1) bal felső sarkának 0,25-nek, az (1, 1) jobb felső sarkának 0,50-nek, az (1, 0) jobb alsó sarkának pedig 0,75-nek kell lennie. A belső pontok inverz képét a görbe rekurzív szerkezetével számítjuk ki. Az alábbiakban egy Java-függvény található, amely kiszámítja a Sierpinski-görbe bármely pontjának relatív helyzetét (vagyis a pszeudo-inverzét). A függvény felveszi az (x, y) pont koordinátáit és a befoglaló derékszögű egyenlő szárú háromszög szögeit (ax, ay), (bx, by) és (cx, cy) (Megjegyezzük, hogy az egységnégyzet a két ilyen háromszög). A fennmaradó paraméterek határozzák meg a számítások pontosságának szintjé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 ))) { code = sierp_pt2code ( ax , ay , ( ax + cx ) / 2.0 , ( ay + cy ) / 2.0 , bx , by , currentLevel , maxLevel , 2 * code + 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 ); } } visszatérési kód ; }

A következő Java kisalkalmazás négy kölcsönösen rekurzív metódussal rajzolja meg a Sierpinski - görbét (egymást hívó metódusok):

import java.applet.Applet ; import java.awt.Graphics ; import java.awt.Image ; public class SierpinskyCurve kiterjeszti a kisalkalmazást { privát SimpleGraphics sg = null ; privát int dist0 = 128 , dist ; privát kép offscrBuf ; privát grafika offscrGfx ; public void init () { sg = new SimpleGraphics ( getGraphics ()); dist0 = 100 ; átméretezés ( 4 * dist0 , 4 * dist0 ); } public void frissítés ( Graphics g ) { paint ( g ); } public void paint ( Graphics g ) { if ( g == null ) dob új NullPointerException (); if ( offscrBuf == null ) { offscrBuf = createImage ( this . getWidth (), ez . getHeight ()); offscrGfx = offscrBuf . getGraphics (); vmit . setGraphics ( offscrGfx ); } int szint = 3 ; dist = dist0 ; for ( int i = szint ; i > 0 ; i -- ) dist /= 2 ; vmit . goToXY ( 2 * dist , dist ); sierpA ( szint ); // rekurzió indítása vmi . lineRel ( 'X' , + dist , + dist ); sierpB ( szint ); // rekurzió indítása vmi . lineRel ( 'X' , - dist , + dist ); sierpC ( szint ); // rekurzió indítása vmi . lineRel ( 'X' , - dist , - dist ); sierpD ( szint ); // rekurzió indítása vmi . lineRel ( 'X' , + dist , - dist ); g . drawImage ( offscrBuf , 0 , 0 , this ); } private void sierpA ( int szint ) { if ( level > 0 ) { sierpA ( szint - 1 ); vmit . lineRel ( 'A' , + dist , + dist ); sierpB ( szint - 1 ); vmit . lineRel ( 'A' , + 2 * dist , 0 ); sierpD ( szint - 1 ); vmit . lineRel ( 'A' , + dist , - dist ); sierpA ( szint - 1 ); } } private void sierpB ( int szint ) { if ( level > 0 ) { sierpB ( szint - 1 ); vmit . lineRel ( 'B' , - dist , + dist ); sierpc ( szint - 1 ); vmit . lineRel ( 'B' , 0 , + 2 * dist ); sierpA ( szint - 1 ); vmit . lineRel ( 'B' , + dist , + dist ); sierpB ( szint - 1 ); } } private void sierpC ( int szint ) { if ( level > 0 ) { sierpC ( szint - 1 ); vmit . lineRel ( 'C ' , -dist , -dist ) ; sierpD ( szint - 1 ); vmit . lineRel ( 'C' , - 2 * dist , 0 ); sierpB ( szint - 1 ); vmit . lineRel ( 'C' , - dist , + dist ); sierpc ( szint - 1 ); } } private void sierpD ( int szint ) { if ( level > 0 ) { sierpD ( szint - 1 ); vmit . lineRel ( 'D' , + dist , - dist ); sierpA ( szint - 1 ); vmit . lineRel ( 'D' , 0 , - 2 * dist ); sierpc ( szint - 1 ); vmit . lineRel ( 'D ' , -dist , -dist ) ; sierpD ( szint - 1 ); } } } class SimpleGraphics { private Graphics g = null ; privát 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 ; ezt . y = y_ _ } public void lineRel ( char s , int deltaX , int deltaY ) { g . drawLine ( x , y , x + deltaX , y + deltaY ); x += deltaX ; y += Y delta ; } }

A következő Logo program rekurzió segítségével Sierpinski-görbét rajzol .

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

Lásd még

Jegyzetek

  1. ↑ Platzman, Bartholdi, 1989 .
  2. ↑ Bartholdi .
  3. ↑ Slyusar, V. Fraktálantennák. Egy alapvetően új típusú "törött" antenna. 2. rész . Elektronika: tudomány, technológia, üzlet. - 2007. - No. 6. S. 82-89. (2007). Letöltve: 2020. április 22. Az eredetiből archiválva : 2018. április 3..

Irodalom