Trójkąt Sierpińskiego
Trójkąt Sierpińskiego (znany też jako uszczelka Sierpińskiego) – jeden z najprostszych fraktali. Znany był na długo przed powstaniem tego pojęcia (patrz: Benoît Mandelbrot). Konstrukcja tego zbioru została podana przez polskiego matematyka Wacława Sierpińskiego w 1915 roku[1].
Trójkąt Sierpińskiego otrzymuje się następująco: w trójkącie równobocznym łączy się środki boków, dzieląc go w ten sposób na cztery mniejsze trójkąty. Trójkąt środkowy usuwa się (bez boków), a wobec trzech pozostałych trójkątów operację się powtarza, dzieląc każdy z nich na cztery mniejsze trójkąty, usuwając środkowy (bez boków), a wobec pozostałych trójkątów czynności się powtarzają. Po każdym powtórzeniu tej operacji z figury zostają usunięte pewne punkty. Punkty, które nie zostaną usunięte, tworzą trójkąt Sierpińskiego[2].
Fraktal ten można także utworzyć z trójkąta Pascala, zabarwiając na czarno jego nieparzyste liczby[3].
Definicja formalna
Niech będzie trójkątem ABC.
- Dzieląc na cztery mniejsze trójkąty i gdzie środki krawędzi są wierzchołkami trójkąta traktując jako zbiór otwarty, a trójkąty za zbiory domknięte, otrzymuje się zbiory rozłączne: i Środki krawędzi leżą w dwóch małych trójkątach (np. zawiera dokładnie jeden punkt – środek odpowiedniej krawędzi).
- Każdy trójkąt dzieli się na cztery mniejsze trójkąty i w podobny sposób.
- Każdy trójkąt dzieli się na cztery mniejsze trójkąty i i tak dalej.
Trójkąt Sierpińskiego zawiera dokładnie te punkty trójkąta ABC, które nie są elementami zbioru
tj. . Trójkąt Sierpińskiego jest zbiorem domkniętym jako różnica zbioru domkniętego i zbioru otwartego . Trójkąt Sierpińskiego jest zbiorem domkniętym, Wymiar fraktalny trójkąta Sierpińskiego wynosi ln 3 / ln 2 = 1,585...
Reprezentacja cyfrowa
Każdy ciąg (gdzie ) określa punkt trójkąta Sierpińskiego, a mianowicie jedyny punkt w zbiorze Odwrotnie, dla każdego punktu można znaleźć taki ciąg określający ten punkt, tzw. reprezentację cyfrową punktu Podobnie jak w przypadku liczb rzeczywistych, nie każdy punkt trójkąta Sierpińskiego ma jednoznaczną reprezentację. Na przykład (jedyny) punkt w przekroju ma reprezentację i jednocześnie reprezentację
Trójkąt Sierpińskiego jako rezultat Gry w chaos
Ciekawym algorytmem pozwalającym otrzymać trójkąt Sierpińskiego jest gra w chaos. Narysujmy trójkąt równoboczny ABC i definiujmy D0 := punkt A. Następnie należy wielokrotnie powtórzyć następującą operację: losowo wybieramy jeden z punktów A, B lub C, rysujemy punkt w połowie odległości między Dn i wybranym punktem. Nowo narysowany punkt oznaczamy przez Dn+1. Każdy punkt Dn będzie należeć do trójkąta Sierpińskiego, i cały trójkąt Sierpińskiego będzie prawie na pewno domknięciem zbioru {D0, D1,...}.
Jeśli wybieramy D0 nie jako punkt A, lecz jako dowolny punkt trójkąta Sierpińskiego, to znowu otrzymujemy (prawie na pewno) trójkąt Sierpińskiego. Jeśli D0 należy do trójkąta ABC, ale nie do trójkąta Sierpińskiego, to żaden punkt Dn do tego trójkąta nie należy, jednak otrzymujemy ten trójkąt (prawie na pewno) jako zbiór punktów skupienia ciągu (D0, D1,...).
Jeśli punkty A, B i C tworzą dowolny (nierównoboczny) trójkąt, to tą samą konstrukcją otrzymujemy zniekształcony trójkąt Sierpińskiego, tzn. obraz trójkąta Sierpińskiego przez przekształcenie afiniczne.
Zobacz też
Przypisy
- ↑ W. Sierpinski, Sur une courbe dont tout point est un point de ramification, „C. R. Acad. Sci. Paris” 160 (1915): 302-305.
- ↑ Sierpińskiego dywan, [w:] Encyklopedia PWN [online] [dostęp 2021-09-15].
- ↑ http://mathforum.org/workshops/usi/pascal/pascal_sierpinski.html
Linki zewnętrzne
- Łukasz Rajkowski, Trójkąt Sierpińskiego w trójkącie Pascala, [w:] pismo „Delta” [online], deltami.edu.pl, marzec 2022, ISSN 0137-3005 [dostęp 2022-03-15] (pol.).
- Eric W. Weisstein, Sierpiński Sieve, [w:] MathWorld [online], Wolfram Research [dostęp 2020-12-12] (ang.).
- Trójkąt Sierpińskiego. chamicewicz.com. [zarchiwizowane z tego adresu (2016-03-18)]. Wersja interaktywna wraz z kodem źródłowym (Processing)
- Trójkąt Sierpińskiego. krzywicki.pro. [zarchiwizowane z tego adresu (2014-08-08)]. Dynamiczny generator fraktalu
- Grant Sanderson, Binary, Hanoi and Sierpinski, kanał 3blue1brown na YouTube, 25 listopada 2016 [dostęp 2021-03-15].
Media użyte na tej stronie
Evolution of the Sierpinski triangle in five iterations.
(c) Dino z angielskiej Wikipedii, CC BY-SA 3.0
Animated construction of Sierpinski Triangle
Self-made.
Licencja
I made this with SAGE, an open-source math package. The latest source code lives here, and has a few better variable names & at least one small bug fix than the below. Others have requested source code for images I generated, below. Code is en:GPL; the exact code used to generate this image follows:
#***************************************************************************** # Copyright (C) 2008 Dean Moore < dean dot moore at deanlm dot com > # < deanlorenmoore@gmail.com > # # # Distributed under the terms of the GNU General Public License (GPL) # http://www.gnu.org/licenses/ #***************************************************************************** ################################################################################# # # # Animated Sierpinski Triangle. # # # # Source code written by Dean Moore, March, 2008, open source GPL (above), # # source code open to the universe. # # # # Code animates construction of a Sierpinski Triangle. # # # # See any reference on the Sierpinski Triangle, e.g., Wikipedia at # # < http://en.wikipedia.org/wiki/Sierpinski_triangle >; countless others are # # out there. # # # # Other info: # # # # Written in sage mathematical package sage (http://www.sagemath.org/), hence # # heavily using computer language Python (http://www.python.org/). # # # # Important algorithm note: # # # # This code does not use recursion. # # # # More topmatter & documentation probably irrelevant to most: # # # # Inspiration: I viewed it an interesting problem, to try to do an animated # # construction of a Sierpinski Triangle in sage. Thought I'd be lazy & search # # the 'Net for open-source versions of this I could simply convert to sage, but # # the open-source code I found was poorly documented & I couldn't figure it # # out, so I gave up & solved the problem from scratch. # # # # Also, I wanted to animate the construction, which I did not find in # # open-source code on the 'Net. # # # # Comments on algorithm: # # # # The code I found on the 'Net was recursive. I do not much like recursion, # # considering it way for programmers to say, "Look how smart I am! I'm using # # recursion! Aren't I cool?!" I feel strongly recursion is often confusing, # # can chew up too much memory, and should be avoided except when # # # # a) It's unavoidable, or # # b) The code would be atrocious without it. # # # # Did some thinking & swearing, but concocted a non-recursive method, and by # # doing the problem from scratch. Guess it avoids all charges of copyright # # violation, plagiarism, whatever. # # # # More on algorithm via ASCII art. Below we have a given triangle, shaded via # # x's. # # # # The next "generation" is the blank triangles. Sit down & start a Sierpinski # # Triangle on scratch: the next generation is always two on each side of a # # given triangle from the last generation, one on top. Algorithm takes the # # given, shaded triangle (below), and makes the three of the next generation # # arising from it. # # # # See code for more on how this works. # # __________ # # \ / # # \ / # # \ / # # \ / # # _________\/_________ # # \ xxxxxxxxxxxxxxxx / # # \ xxxxxxxxxxxxxx / # # \ xxxxxxxxxxxx / # # \ xxxxxxxxxx / # # _________\ xxxxxxxx /_________ # # \ /\ xxxxxx /\ / # # \ / \ xxxx / \ / # # \ / \ xx / \ / # # \ / \ / \ / # # \/ \/ \/ # # # ################################################################################# # # # Begin program: # # # # First we need three functions; see the below code on how they are used. # # # # The three functions *right_side_triangle* , *left_side_triangle* & # # *top_triangle* are here defined & not as "lambda" functions, as they need # # documented. # # # # I don't care to replicate the poorly-documented code I found on the 'Net. # # # ################################################################################# # # # First function, *right_side_triangle*. # # # # Function *right_side_triangle* gives coordinates of next triangle on right # # side of a given triangle whose coordinates are passed in. # # # # Points *p*, *r*, *q*, *s* & *t* are labeled as passed in: # # # # (p, r)____________________(q, r) # # \ / # # \ / # # \ / # # \ / # # \ (p1, r1)/_________ (q1, r1) # # \ /\ / # # \ / \ / # # \ / \ / # # \ / \ / # # \/ \/ # # (s, t) (s1, t1) # # # # p1 = (q + s)/2, a simple average. # # q1 = q + (q - s)/2 = (3*q - s)/2 # # r1 = (r + t)/2, a simple average. # # s1 = q, easy. # # t1 = t, easy. # # # ################################################################################# def right_side_triangle(p,q,r,s,t): p1 = (q + s)/2 q1 = (3*q - s)/2 r1 = (r + t)/2 s1 = q # A placeholder, solely to make code clear. t1 = t # Ditto, a placeholder. return ((p1,r1),(q1, r1),(s1, t1)) # End of function *right_side_triangle*. ################################################################################# # # # Function *left_side_triangle*: # # # # (p, q) ____________________(q, r) # # \ / # # \ / # # \ / # # \ / # # (p1, r1) _________\ (q1, r1) / # # \ /\ / # # \ / \ / # # \ / \ / # # \ / \ / # # \/ \/ # # (s1, t1) (s, t) # # # # p1 = p - (s - p)/2 = (2p-s+p)/2 = (3p - s)/2 # # q1 = (p + s)/2, a simple average # # r1 = (r + t)/2, a simple average. # # s1 = p, easy. # # t1 = t, easy. # # # ################################################################################# def left_side_triangle(p,q,r,s,t): p1 = (3*p - s)/2 q1 = (p + s)/2 r1 = (r + t)/2 s1 = p # A placeholder, solely to make code clear. t1 = t # Ditto, a placeholder. return ((p1,r1),(q1, r1),(s1, t1)) # End of function *left_side_triangle*. ################################################################################# # # # Function *top_triangle*. # # # # (p1, r1) __________ (q1, r1) # # \ / # # \ / # # \ / # # \ / (s1, t1) # # (p, r)_________\/_________ # # \ xxxxxxxxxxxxxxxx / # # \ xxxxxxxxxxxxxx / (q, r) # # \ xxxxxxxxxxxx / # # \ xxxxxxxxxx / # # \ xxxxxxxx / # # \ xxxxxx / # # \ xxxx / # # \ xx / # # \ / # # \/ # # (s, t) # # # # p1 = (p + s)/2, a simple average. # # q1 = (s + q)/2, a simple average # # r1 = r + (r - t)/2 = (3r - t)/2 # # s1 = s, easy. # # t1 = r, easy. # # # ################################################################################# def top_triangle(p,q,r,s,t): p1 = (p + s)/2 q1 = (s + q)/2 r1 = (3*r - t)/2 s1 = s # Again, both this & next are t1 = r # placeholders, solely to make code clear. return ((p1,r1),(q1, r1),(s1, t1)) # End of function *top_triangle*. ################################################################################# # # # Main program commences: # # # ################################################################################# # Top matter a user may wish to vary: number_of_generations = 8 # How "deep" goes the animation after initial triangle. first_triangle_color = (1,0,0) # First triangle's rgb color as red-green-blue tuple. chopped_piece_color = (0,0,0) # Color of "chopped" pieces as rgb tuple. delay_between_frames = 50 # Time between "frames" of final "movie." figure_size = 12 # Regulates size of final image. initial_edge_length = 3^7 # Initial edge length. # End of material user may realistically vary. Rest should churn without user input. number_of_triangles_in_last_generation = 3^number_of_generations # Always a power of three. images = [] # Holds images of final "movie." coordinates = [] # Holds coordinates. p0 = (0,0) # Initial points to start iteration -- note p1 = (initial_edge_length, 0) # y-values of *p0* & *p1* are the same -- an p2 = ((p0[0] + p1[0])/2, # important book-keeping device. ((initial_edge_length/2)*sin(pi/3))) # Equilateral triangle; see any Internet # reference on these. # We make a polygon (triangle) of initial points: this_generations_image = polygon((p0, p1, p2), rgbcolor=first_triangle_color) images.append(this_generations_image) # Save image from last line. coordinates = [( ( (p0[0] + p2[0])/2, (p0[1] + p2[1])/2 ), # Coordinates ( (p1[0] + p2[0])/2, (p1[1] + p2[1])/2 ), # of second ( (p0[0] + p1[0])/2, (p0[1] + p1[1])/2 ) )] # triangle. # It is *supremely* important # that the y-values of the first two # points are equal -- check definitions # above & code below. this_generations_image = polygon(coordinates[0], # Image of second triangle. rgbcolor=chopped_piece_color)
images.append(images[0] + this_generations_image) # Save second image, tacked on top of first.
# Now the loop that makes the images:
number_of_triangles_in_this_generation = 1 # We have made one "chopped" triangle, the second, above.
while number_of_triangles_in_this_generation < number_of_triangles_in_last_generation:
this_generations_image = Graphics() # Holds next generation's image, initialize.
next_generations_coordinates = [] # Holds next generation's coordinates, set to null.
for a,b,c in coordinates: # Loop on all triangles.
(p, r) = a # Right point; note y-value of this & next are equal.
(q, r1) = b # Left point; note r1 = r & thus *r1* is irrelevant;
# it's only there for book-keeping.
(s, t) = c # Bottom point.
# Now construct the three triangles & their three polygons of the next
# generation.
right_triangle = right_side_triangle(p,q,r,s,t) # Here use those
left_triangle = left_side_triangle (p,q,r,s,t) # utility functions
upper_triangle = top_triangle (p,q,r,s,t) # defined at top.
right = polygon(right_triangle, rgbcolor=(chopped_piece_color)) # Make next
left = polygon(left_triangle, rgbcolor=(chopped_piece_color)) # generation's
top = polygon(upper_triangle, rgbcolor=(chopped_piece_color)) # triangles.
this_generations_image = this_generations_image + (right + left + top) # Add image.
next_generations_coordinates.append(right_triangle) # Save the coordinates
next_generations_coordinates.append( left_triangle) # of triangles of the
next_generations_coordinates.append(upper_triangle) # next generation.
# End of "for a,b,c" loop.
coordinates = next_generations_coordinates # Save for next generation.
images.append(images[-1] + this_generations_image) # Make next image: all previous
# images plus latest on top.
number_of_triangles_in_this_generation *= 3 # Bump up.
# End of *while* loop.
a = animate(images, figsize=[figure_size, figure_size], axes=False) # Make image, ...
a.show(delay = delay_between_frames) # Show image.
# End of program.
End of code.