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 ${\displaystyle 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 ${\displaystyle n\rightarrow \infty }$) es ${\displaystyle 2}$.

La distancia euclidiana de

${\displaystyle S_{n}}$ es ${\displaystyle 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 ${\displaystyle n}$ más allá de cualquier límite, mientras que el límite para ${\displaystyle n\rightarrow \infty }$ del área encerrada por ${\displaystyle S_{n}}$ es ${\displaystyle 5/12\,}$ la del cuadrado (en métrica euclidiana).

Curva de Sierpinski de orden 1

Curvas de Sierpinski de órdenes 1 y 2

Curvas de Sierpinski de órdenes 1 a 3

Usos de la curva

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

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

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

Véase también

•   Wikimedia Commons alberga una galería multimedia sobre Curva de Sierpinski.
• Curva de Hilbert
• Copo de nieve de Koch
• Curva de Moore
• Curva de Peano
• Curva de la punta de flecha de Sierpinski
• Anexo:Fractales por dimensión de Hausdorff
• Recursión (ciencias de computación)
• Triángulo de Sierpinski

•   Datos: Q786286
•   Multimedia: Sierpinski curves / Q786286