Curva de Sierpinski

La curva de Sierpinski es una secuencia definida de forma recursiva de una curva fractal continua, descubierta por el matemático polaco Wacław Sierpiński, que en el límite $n\rightarrow \infty$ llena completamente el cuadrado unitario: así su curva límite, también llamada "curva de Sierpinski" , es un ejemplo de una curva que recubre una superficie.

Debido a que la curva de Sierpinski está llenando el espacio, su dimensión de Hausdorff-Besicovitch (en el límite $n\rightarrow \infty$ ) es $2$ .

La distancia euclidiana de

S_{n}

es

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

,

es decir, crece "exponencialmente" con $n$ más allá de cualquier límite, mientras que el límite para $n\rightarrow \infty$ del área encerrada por $S_{n}$ es $5/12\,$ la del cuadrado (en métrica euclidiana).

Usos de la curva[editar]

La curva de Sierpinski es útil en varias aplicaciones prácticas porque es más simétrica que otras curvas de relleno del espacio comúnmente estudiadas. Por ejemplo, se ha utilizado como base para la construcción rápida de una solución aproximada al problema del viajante (que busca la secuencia más corta de un conjunto dado de puntos): la heurística es simplemente visitar los puntos en la misma secuencia en la que aparecen en la curva de Sierpinski.^[1] Para ello, se requieren dos pasos: primero calcular una imagen inversa de cada punto a visitar; luego, ordenar los valores. Esta idea se ha utilizado para construir sistemas de enrutamiento para vehículos comerciales basados únicamente en archivos de tarjetas Rolodex.^[2]

Una curva de llenado del espacio es una correspondencia continua del intervalo unidad sobre un cuadrado de lado unidad y así una (pseudo) correspondencia inversa permite relacionar los puntos del cuadrado con los de un segmento unitario. Una forma de construir una correspondencia pseudo-inversa es la siguiente: la esquina inferior izquierda (0, 0) del cuadrado unitario corresponde a 0,0 (y 1,0). A continuación, la esquina superior izquierda (0, 1) debe corresponder a 0,25, la esquina superior derecha (1, 1) a 0,50 y la esquina inferior derecha (1, 0) a 0,75. El mapa inverso de los puntos interiores se calcula aprovechando la estructura recursiva de la curva.

A continuación se incluye el código de una función en Java que calcula la posición relativa de cualquier punto en la curva de Sierpinski (es decir, un valor pseudo-inverso). Toma como entrada las coordenadas del punto (x,y) a invertir, y las esquinas de un triángulo isósceles rectángulo (ax,ay), (bx,by) y (cx,cy). (Obsérvese que la unidad cuadrada es la unión de dos triángulos de este tipo.) Los parámetros restantes especifican el nivel de exactitud con el que se debe calcular la inversa.

    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 );
            }
        }
        return code;    
    }

Dibujo de la curva[editar]

La siguiente applet Java dibuja una curva de Sierpinski mediante cuatro métodos mutuamente recursivos (métodos que se llaman 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, 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;
        this.y = y;
    }

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

El siguiente programa en lenguaje Logo dibuja una curva de Sierpinski mediante un procedimiento 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 y0 = 3 * h;
   int x, xAnt;
   int y, yAnt;
   Graphics g2;

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

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

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

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

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

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

   }
   
   public void d (int i){
       if(i>0){
           
          d(i-1);x=x+h; y=y+h; g2.drawLine(xAnt, yAnt, x, y);
           xAnt=x; yAnt=y;
           a(i-1);y=y+2*h; g2.drawLine(xAnt, yAnt, x, y);
           xAnt=x; yAnt=y;
           c(i-1); x=x-h; y=y+h; g2.drawLine(xAnt, yAnt, x, y);
 xAnt=x; yAnt=y;
 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

}

Referencias[editar]

↑ 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". Georgia Institute of Technology.