stringtranslate.com

Curva de Sierpinski

Las curvas de Sierpiński son una secuencia definida recursivamente de curvas fractales planas cerradas continuas descubiertas por Wacław Sierpiński , que en el límite llenan completamente el cuadrado unitario: por lo tanto, su curva límite, también llamada curva de Sierpiński , es un ejemplo de una curva que llena el espacio .

Como la curva de Sierpiński ocupa todo el espacio, su dimensión de Hausdorff (en el límite ) es . La longitud euclidiana de la curva de iteración es

es decir, crece exponencialmente más allá de cualquier límite, mientras que el límite para el área encerrada por es el del cuadrado (en la métrica euclidiana).

Curva cuadrada de Sierpiński [2] de órdenes 2–4

Usos de la curva

La curva de Sierpiński es útil en varias aplicaciones prácticas porque es más simétrica que otras curvas de relleno de espacio estudiadas comúnmente. Por ejemplo, se ha utilizado como base para la construcción rápida de una solución aproximada al Problema del Viajante (que pide 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 Sierpiński. [3] Para hacer esto 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. [4]

Una curva que llena el espacio es una aplicación continua del intervalo unitario sobre un cuadrado unitario y, por lo tanto, una (pseudo)inversa asigna el cuadrado unitario al intervalo unitario. Una forma de construir una pseudoinversa es la siguiente. Supongamos que la esquina inferior izquierda (0, 0) del cuadrado unitario corresponde a 0,0 (y 1,0). Entonces, 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. La aplicación inversa de los puntos interiores se calcula aprovechando la estructura recursiva de la curva.

Aquí hay una función codificada en Java que calculará la posición relativa de cualquier punto en la curva de Sierpiński (es decir, un valor pseudoinverso). Toma como entrada las coordenadas del punto (x, y) que se va a invertir y los vértices de un triángulo isósceles rectángulo que lo encierra (ax, ay), (bx, by) y (cx, cy). (El cuadrado unitario es la unión de dos de esos triángulos). Los parámetros restantes especifican el nivel de precisión 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 { código = sierp_pt2code ( bx , by , ( ax + cx ) / 2.0 , ( ay + cy ) / 2.0 , cx , cy , currentLevel , maxLevel , 2 * código + 1 , x , y ); } } código de retorno ; }                                                                                         

Representación como sistema de Lindenmayer

La curva de Sierpiński se puede expresar mediante un sistema de reescritura ( sistema L ).

Alfabeto : F, G, X
Constantes : F, G, +, −
Axioma : F−−XF−−F−−XF
Reglas de producción :
X → XF+G+XF−−F−−XF+G+X
Angulo : 45

Aquí, tanto F como G significan "avanzar", + significa "girar a la izquierda 45°" y significa "girar a la derecha 45°" (ver gráficos de tortugas ). La curva suele dibujarse con longitudes diferentes para F y G.

La curva cuadrada de Sierpiński se puede expresar de manera similar:

Alfabeto : F, X
Constantes : F, +, −
Axioma : F+XF+F+XF
Reglas de producción :
X → XF−F+F−XF+F+XF−F+F−X
Ángulo : 90

Curva de punta de flecha

La curva de punta de flecha de Sierpiński es una curva fractal similar en apariencia e idéntica en límite al triángulo de Sierpiński .

Evolución de la curva de punta de flecha de Sierpiński

La curva de punta de flecha de Sierpiński dibuja un triángulo equilátero con agujeros triangulares a intervalos iguales. Se puede describir con dos reglas de producción de sustitución: (A → BAB) y (B → A+B+A). A y B se repiten y en la parte inferior hacen lo mismo: dibujan una línea. Más y menos (+ y -) significan un giro de 60 grados hacia la izquierda o hacia la derecha. El punto final de la curva de punta de flecha de Sierpiński es siempre el mismo siempre que se repita un número par de veces y se reduzca a la mitad la longitud de la línea en cada recursión. Si se repite a una profundidad impar (el orden es impar), entonces se termina girando 60 grados, en un punto diferente del triángulo.

En el artículo sobre la curva de De Rham se ofrece una constricción alternativa : se utiliza la misma técnica que las curvas de De Rham, pero en lugar de utilizar una expansión binaria (base 2), se utiliza una expansión ternaria (base 3).

Código

Dadas las funciones de dibujo void draw_line(double distance);y void turn(int angle_in_degrees);, el código para dibujar una curva de punta de flecha de Sierpiński (aproximada) se ve así:

void sierpinski_arrowhead_curve ( unsigned order , double length ) { // Si el orden es par, podemos simplemente dibujar la curva. if ( 0 == ( order & 1 ) ) { curve ( order , length , + 60 ); } else /* el orden es impar */ { turn ( +60 ) ; curve ( order , length , -60 ); } }                           
void curva ( unsigned order , double length , int angle ) { if ( 0 == order ) { draw_line ( length ); } else { curva ( order - 1 , length / 2 , - angle ); girar ( angle ); curva ( order - 1 , length / 2 , - angle ); girar ( angle ); curva ( order - 1 , length / 2 , - angle ); } }                                         

Representación como sistema de Lindenmayer

Al igual que muchas curvas fractales bidimensionales, la curva de punta de flecha de Sierpiński se puede extender a tres dimensiones.

La curva de punta de flecha de Sierpiński se puede expresar mediante un sistema de reescritura ( sistema L ).

Alfabeto : X, Y
Constantes : F, +, −
Axioma : XF
Reglas de producción :
X → YF + XF + Y
Y → XF − YF − X

Aquí, F significa "avanzar", + significa "girar a la izquierda 60°" y significa "girar a la derecha 60°" (ver gráficos de tortugas ).

Véase también

Referencias

  1. ^ Weisstein, Eric W. "Curva de Sierpiński". MathWorld . Consultado el 21 de enero de 2019 .
  2. ^ Dickau, Robert M. (1996/7) "Sistemas L bidimensionales", Robert's Math Figures . MathForum.org. Consultado el 21 de enero de 2019.
  3. ^ Platzman, Loren K.; Bartholdi, John J. III (1989). "Curvas que llenan el espacio y el problema del viajante de comercio planar". Revista de la Asociación de Maquinaria Computacional . 36 (4): 719–737. doi : 10.1145/76359.76361 .
  4. ^ Bartholdi, John J. III. "Algunas aplicaciones combinatorias de curvas que llenan el espacio". Instituto Tecnológico de Georgia . Archivado desde el original el 3 de agosto de 2012.

Lectura adicional