Las curvas de Sierpiński son una secuencia definida de forma recursiva de curvas fractales continuas de plano cerrado descubiertas por Wacław Sierpiński , que en el límitellenar completamente el cuadrado unitario: por lo tanto, su curva límite, también llamada curva de Sierpiński , es un ejemplo de una curva de llenado de espacio .
Debido a que la curva de Sierpiński ocupa espacio, su dimensión de Hausdorff (en el límite) es .
La longitud euclidiana dela curva de iteración es
es decir, crece exponencialmente con más allá de cualquier límite, mientras que el límite para del área delimitada por es el del cuadrado (en métrica euclidiana).
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 comúnmente estudiadas. Por ejemplo, se ha utilizado como base para la construcción rápida de una solución aproximada al problema del vendedor ambulante (que pide la secuencia más corta de un conjunto de puntos dado): la heurística es simplemente visitar los puntos en la misma secuencia tal como aparecen en la curva de Sierpiński. [3] Para hacer esto, se requieren dos pasos: Primero, calcular una imagen inversa de cada punto que se visitará; luego ordene los valores. Esta idea se ha utilizado para crear sistemas de enrutamiento para vehículos comerciales basados únicamente en archivos de tarjetas Rolodex. [4]
Una curva de relleno de espacio es un mapa continuo del intervalo unitario en un cuadrado unitario y, por lo tanto, una (pseudo) inversa asigna el cuadrado unitario al intervalo unitario. Una forma de construir un pseudo-inverso es la siguiente. Deje que la esquina inferior izquierda (0, 0) del cuadrado unitario corresponda a 0.0 (y 1.0). Luego, 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 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 pseudo-inverso). Toma como entrada las coordenadas del punto (x, y) a invertir, y las esquinas de un triángulo isósceles recto circundante (ax, ay), (bx, by) y (cx, cy). (Tenga en cuenta que 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 ))) { código = sierp_pt2code ( ax , ay , ( ax + cx ) / 2.0 , ( ay + cy ) / 2.0 , bx , by , currentLevel , maxLevel , 2 * código + 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 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
- Ángulo : 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 generalmente se dibuja con diferentes longitudes 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 el límite al triángulo de Sierpiński .
La curva de punta de flecha de Sierpiński dibuja un triángulo equilátero con agujeros triangulares a intervalos iguales. Puede describirse con dos reglas de producción sustitutivas: (A → BAB) y (B → A + B + A). A y B se repiten y en la parte inferior hacen lo mismo: dibuja una línea. Más y menos (+ y -) significan girar 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 repita un número par de veces y reduzca a la mitad la longitud de la línea en cada recursión. Si recurre a una profundidad extraña (el orden es extraño), terminará girando 60 grados, en un punto diferente del triángulo.
En el artículo sobre la curva de Rham se da una constricción alternativa : se usa la misma técnica que las curvas de Rham, pero en lugar de usar una expansión binaria (base 2), se usa 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 ( orden sin firmar , doble longitud ) { // Si el orden es par, podemos dibujar la curva. if ( 0 == ( orden & 1 ) ) { curva ( orden , longitud , + 60 ); } else / * el orden es impar * / { turn ( + 60 ); curva ( orden , longitud , -60 ); } }
curva vacía ( orden sin firmar , longitud doble , ángulo int ) { if ( 0 == orden ) { draw_line ( longitud ); } else { curva ( orden - 1 , longitud / 2 , - ángulo ); girar ( ángulo ); curva ( orden - 1 , longitud / 2 , ángulo ); girar ( ángulo ); curva ( orden - 1 , longitud / 2 , - ángulo ); } }
Representación como sistema Lindenmayer
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 ).
Ver también
Referencias
- ^ Weisstein, Eric W. "Curva de Sierpiński" . MathWorld . Consultado el 21 de enero de 2019 .
- ^ Dickau, Robert M. (1996/7) " Sistemas L bidimensionales ", Figuras matemáticas de Robert . MathForum.org. Consultado el 21 de enero de 2019.
- ^ Platzman, Loren K .; Bartholdi, John J., III (1989). "Las curvas de llenado de espacio y el problema del viajante de comercio plano". Revista de la Asociación de Maquinaria Informática . 36 (4): 719–737. doi : 10.1145 / 76359.76361 .
- ^ Bartholdi, John J., III. "Algunas aplicaciones combinatorias de las curvas de llenado de espacios" . Instituto de Tecnología de Georgia . Archivado desde el original el 3 de agosto de 2012.
Otras lecturas
- Peitgen, H.-O .; Jürgens, H .; Saupe, D. (2013) [1992]. Caos y fractales: nuevas fronteras de la ciencia . Saltador. ISBN 978-1-4757-4740-9.
- Stevens, Roger T. (1989). Programación en C fractal . Libros de M&T. ISBN 9781558510371.