Curva de Sierpinski

La curva de Sierpinski és una seqüència definida de forma recursiva d'una curva fractal contínua, descoberta pel matemàtic polac Wacław Sierpiński, que en el llímit $n \to \infty$ ompli completament el quadrat unitari: aixina la seua curva llímit, també cridada "curva de Sierpinski" , és un eixemple d'una curva que recobrix una superfície.

Degut a que la curva de Sierpinski està omplint l'espai, el seu dimensió de Hausdorff-Besicovitch (en el llímit $n \to \infty$ ) és $2$ .

La distància euclidiana de

S_{n}

és

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

,

és dir, creix "exponencialment" en $n$ més allà de qualsevol llímit, mentres que el llímit per a $n \to \infty$ de l'àrea tancada per $S_{n}$ és $5 / 12$ la del quadrat (en mètrica euclidiana).

Erro al crear miniatura:

Curves de Sierpinski d'órdens 1 a 3

Usos de la curva

La curva de Sierpinski és útil en vàries aplicacions pràctiques perque és més simètrica que atres curves de farcidura de l'espai comunament estudiades. Per eixemple, s'ha utilisat com a base per a la construcció ràpida d'una solució aproximada al problema del viajante (que busca la seqüència més curta d'un conjunt donat de punts): l'heurística és simplement visitar els punts en la mateixa seqüència en la que apareixen en la curva de Sierpinski.^[1] Per a això, es requerixen dos passos: primer calcular una image inversa de cada punt a visitar; després, ordenar els valors. Esta idea s'ha utilisat per a construir sistemes de enrutamiento per a vehículs comercials basats únicament en archius de targetes Rolodex.^[2]

Una curva d'omplit de l'espai és una correspondència contínua de l'interval unitat sobre un quadrat de costat unitat i aixina una (pseudo) correspondència inversa permet relacionar els punts del quadrat en els de un segment unitari. Una forma de construir una correspondència pseudo-inversa és la següent: el cantó inferior esquerre (0, 0) del quadrat unitari correspon a 0,0 (i 1,0). A continuació, el cantó superior esquerre (0, 1) deu correspondre a 0,25, el cantó superior dret (1, 1) a 0,50 i el cantó inferior dret (1, 0) a 0,75. El mapa invers dels punts interiors es calcula aprofitant l'estructura recursiva de la curva.

A continuació s'inclou el còdic d'una funció en Java que calcula la posició relativa de qualsevol punt en la curva de Sierpinski (és dir, un valor pseudo-invers). Pren com a entrada les coordenades del punt (x,i) a invertir, i els cantons d'un triàngul isósceles rectàngul (ax,ai), (bx,by) i (cx,cy). (Observe's que l'unitat quadrada és l'unió de dos triànguls d'este tipo.) Els paràmetros restants especifiquen el nivell d'exactitut en el que es deu calcular l'inversa.

    static long sierp_pt2code( double ax, double ai, double bx, double by, double cx, double cy,
        int currentLevel, int maxLevel, long code, double x, double i ) 
    {
        if (currentLevel <= maxLevel) {
            currentLevel++;
            if ((sqr(x-ax) + sqr(i-ai)) < (sqr(x-cx) + sqr(i-cy))) {
                code = sierp_pt2code( ax, ai, (ax+cx)/2.0, (ai+cy)/2.0, bx, by,
                    currentLevel, maxLevel, 2 * code + 0, x, i );
            }
            else {
                code = sierp_pt2code( bx, by, (ax+cx)/2.0, (ai+cy)/2.0, cx, cy,
                    currentLevel, maxLevel, 2 * code + 1, x, i );
            }
        }
        return code;    
    }

Dibuix de la curva

La següent applet Java dibuixa una curva de Sierpinski per mig de quatre métodos mútuament recursivos (métodos que es diuen entre sí):

import java.applet.Applet;
import java.awt.Graphics;
import java.awt.Image;

public class SierpinskyCurve extends Applet {

    private SimpleGraphics sg = null;
    private int dist0 = 128, dist;
    private Image offscrBuf;
    private Graphics offscrGfx;

    public void init() {
        sg = new SimpleGraphics(getGraphics());
        dist0 = 100;
        resize(4 * dist0, 4 * dist0);
    }

    public void update(Graphics g) {
        paint(g);
    }

    public void paint(Graphics g) {

        if (g == null)
            throw new NullPointerException();

        if (offscrBuf == null) {
            offscrBuf = createImage(this.getWidth(), this.getHeight());
            offscrGfx = offscrBuf.getGraphics();
            sg.setGraphics(offscrGfx);
        }

        int level = 3;
        dist = dist0;
        for (int i = level; i > 0; i--)
            dist /= 2;
        sg.goToXY(2 * dist, dist);
        sierpA(level); // start recursion
        sg.lineRel('X', +dist, +dist);
        sierpB(level); // start recursion
        sg.lineRel('X', -dist, +dist);
        sierpC(level); // start recursion
        sg.lineRel('X', -dist, -dist);
        sierpD(level); // start recursion
        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(level - 1);
            sg.lineRel('A', +2 * dist, 0);
            sierpD(level - 1);
            sg.lineRel('A', +dist, -dist);
            sierpA(level - 1);
        }
    }

    private void sierpB(int level) {
        if (level > 0) {
            sierpB(level - 1);
            sg.lineRel('B', -dist, +dist);
            sierpC(level - 1);
            sg.lineRel('B', 0, +2 * dist);
            sierpA(level - 1);
            sg.lineRel('B', +dist, +dist);
            sierpB(level - 1);
        }
    }

    private void sierpC(int level) {
        if (level > 0) {
            sierpC(level - 1);
            sg.lineRel('C', -dist, -dist);
            sierpD(level - 1);
            sg.lineRel('C', -2 * dist, 0);
            sierpB(level - 1);
            sg.lineRel('C', -dist, +dist);
            sierpC(level - 1);
        }
    }

    private void sierpD(int level) {
        if (level > 0) {
            sierpD(level - 1);
            sg.lineRel('D', +dist, -dist);
            sierpA(level - 1);
            sg.lineRel('D', 0, -2 * dist);
            sierpC(level - 1);
            sg.lineRel('D', -dist, -dist);
            sierpD(level - 1);
        }
    }
}

class SimpleGraphics {
    private Graphics g = null;
    private int x = 0, i = 0;

    public SimpleGraphics(Graphics g) {
        setGraphics(g);
    }

    public void setGraphics(Graphics g) {
        this.g = g;
    }

    public void goToXY(int x, int i) {
        this.x = x;
        this.i = i;
    }

    public void lineRel(char s, int deltaX, int deltaY) {
        g.drawLine(x, i, x + deltaX, i + deltaY);
        x += deltaX;
        i += deltaY;
    }
}

El següent programa en llenguage Logo dibuixa una curva de Sierpinski per mig d'un procediment de recursión.

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

//A I M C package FiguraRecursiva202; import java.awt.Graphics; public class FiguraRecursiva extends javax.swing.JFrame {

     int i =0;
   final int N = 4;
   final int H0 = 512;
   int h = H0 / 4;
   int x0 = 2 h;
   int i0 = 3 * h;
   int x, xAnt;
   int i, yAnt;
   Graphics g2;

   public FiguraRecursiva() {
       initComponents();
        setSize(H0, H0);//tamaÃ±o de la finestra

setLocationRelativeTo(this);

   }
Override
   public void paint(Graphics g) {
       super.paint(g);
       this.g2=g;
    do{
        i = i +1;
        x0 = x0 - h;
        h = h / 2;
        i0 = i0 + h;
        x = x0;
        i = i0;
        
        xAnt = x;
        yAnt = i;

        a(i); x=x+h; i=i-h; g2.drawLine(xAnt, yAnt, x, i);
        xAnt=x; yAnt=i;
        b(i);x=x-h; i=i-h; g2.drawLine(xAnt, yAnt, x, i);
         xAnt=x; yAnt=i;
         c(i);x=x-h; i=i+h; g2.drawLine(xAnt, yAnt, x, i);
          xAnt=x; yAnt=i;
          d(i);x=x+h; i=i+h; g2.drawLine(xAnt, yAnt, x, i);
           xAnt=x; yAnt=i;
           
        
 
    }while (i != N);
            
    }

    public void a(int i){
        if(i > 0){
           
       a(i-1); x=x+h; i=i-h; g2.drawLine(xAnt, yAnt, x, i);
       xAnt=x; yAnt=i;
       b (i-1); x = x + 2 * h; g2.drawLine(xAnt, yAnt, x, i);
       xAnt=x; yAnt=i;
       d(i-1);x=x+h; i=i+h; g2.drawLine(xAnt, yAnt, x, i);
       xAnt=x; yAnt=i;
       a(i-1);

         public void b(int i){
         if(i>0){
          b(i-1); x=x-h; i=i-h; g2.drawLine(xAnt, yAnt, x, i);
             xAnt=x; yAnt=i;
             c(i-1); i = i - 2 * h; g2.drawLine(xAnt, yAnt, x, i);
             xAnt=x; yAnt=i;
             a(i-1);x=x+h; i=i-h; g2.drawLine(xAnt, yAnt, x, i);
             xAnt=x; yAnt=i;
             b(i-1);
   
             
             
         }
    
                   
     }

   public void c(int i){
       if(i>0){
           c(i-1); x=x-h; i=i+h; g2.drawLine(xAnt, yAnt, x, i);
           xAnt=x; yAnt=i;
           d(i-1);x=x-2h; g2.drawLine(xAnt, yAnt, x, i);
           xAnt=x; yAnt=i;
           b(i-1);x=x-h; i=i-h; g2.drawLine(xAnt, yAnt, x, i);
           xAnt=x; yAnt=i;
           c(i-1);
 
           
       }

   }
   
   public void d (int i){
       if(i>0){
           
          d(i-1);x=x+h; i=i+h; g2.drawLine(xAnt, yAnt, x, i);
           xAnt=x; yAnt=i;
           a(i-1);i=i+2h; g2.drawLine(xAnt, yAnt, x, i);
           xAnt=x; yAnt=i;
           c(i-1); x=x-h; i=i+h; g2.drawLine(xAnt, yAnt, x, i);
 xAnt=x; yAnt=i;
 d(i-1);
                   
           
 
       }
   }

   SuppressWarnings("unchecked")
   // <editor-fold defaultstate="collapsed" desc="Generated Code">//GEN-BEGIN:initComponents
   private void initComponents() {

       setDefaultCloseOperation(javax.swing.WindowConstants.EXIT_ON_CLOSE);

       javax.swing.GroupLayout layout = new javax.swing.GroupLayout(getContentPane());
       getContentPane().setLayout(layout);
       layout.setHorizontalGroup(
           layout.createParallelGroup(javax.swing.GroupLayout.Alignment.LEADING)
           .addGap(0, 400, Short.MAX_VALUE)
       );
       layout.setVerticalGroup(
           layout.createParallelGroup(javax.swing.GroupLayout.Alignment.LEADING)
           .addGap(0, 300, Short.MAX_VALUE)
       );

       pack();
   }// </editor-fold>//GEN-END:initComponents

   public static void main(String args[]) {
       /* Set the Nimbus look and feel */
       //<editor-fold defaultstate="collapsed" desc=" Look and feel setting code (optional) ">
       /* If Nimbus (introduced in Java SE 6) is not available, stay with the default look and feel.
        * For details see http://download.oracle.com/javase/tutorial/uiswing/lookandfeel/plaf.html 
        */
       try {
           for (javax.swing.UIManager.LookAndFeelInfo info : javax.swing.UIManager.getInstalledLookAndFeels()) {
               if ("Nimbus".equals(info.getName())) {
                   javax.swing.UIManager.setLookAndFeel(info.getClassName());
                   break;
               }
           }
       } catch (ClassNotFoundException ex) {
           java.util.logging.Logger.getLogger(FiguraRecursiva.class.getName()).log(java.util.logging.Level.SEVERE, null, ex);
       } catch (InstantiationException ex) {
           java.util.logging.Logger.getLogger(FiguraRecursiva.class.getName()).log(java.util.logging.Level.SEVERE, null, ex);
       } catch (IllegalAccessException ex) {

java.util.logging.Logger.getLogger(FiguraRecursiva.class.getName()).log(java.util.logging.Level.SEVERE, null, ex);

       } catch (javax.swing.UnsupportedLookAndFeelException ex) {
           java.util.logging.Logger.getLogger(FiguraRecursiva.class.getName()).log(java.util.logging.Level.SEVERE, null, ex);
       }
       //</editor-fold>

       /* Create and display the form */
       java.awt.EventQueue.invokeLater(new Runnable() {
           public void run() {
               new FiguraRecursiva().setVisible(true);
           }
       });
   }

   // Variables declaration - do not modify//GEN-BEGIN:variables
   // End of variables declaration//GEN-END:variables

}

Referències

↑ Platzman, Loren K.; Bartholdi, John J., III (1989). "Spacefilling curves and the planar traveling salesman problem". Journal of the Association of Computing Machinery. 36 (4): 719–737
↑ Bartholdi, John J., III. "Some combinatorial applications of spacefilling curves". Geòrgia Institute of Technology.

Este artícul conté una traducció derivada de «Curva de Sierpinski» de Wikipedia en castellà publicada baix la Llicència de documentació lliure de GNU i la Llicència Creative Commons Reconeiximent-CompartirIgual 4.0 Internacional.

[1] Platzman, Loren K.; Bartholdi, John J., III (1989). "Spacefilling curves and the planar traveling salesman problem". Journal of the Association of Computing Machinery. 36 (4): 719–737

[2] Bartholdi, John J., III. "Some combinatorial applications of spacefilling curves". Geòrgia Institute of Technology.

[1]

[2]