Generowanie dywanu Sierpińskiego w Pythonie

Dzięki funkcjom rekurencyjnym możemy uzyskać różne znane fraktale. Są to między innymi:

zbiór Cantora,
płatek Kocha,
dywan Sierpińskiego,
drzewo binarne.

Do tworzenia takich obrazów w języku Python doskonale nadaje się moduł turtle.

Ważne!

W funkcjach będziemy wykorzystywać obiekt klasy Turtle do utworzenia obiektu żółwia. Ponieważ funkcja rekurencyjna wywołuje samą siebie wielokrotnie, obiekt żółwia musi być do niej przekazany jako jeden z parametrów. W przeciwnym razie wyniki działania funkcji rekurencyjnej mogłyby być nieprzewidywalne.

from turtle import Turtle
zlw = Turtle() #definicja obiektu żółwia

def funkcja_rekurencyjna(obiekt_zolwia, ...):
    pass

# wywołanie
funkcja_rekurencyjna(zlw, ...)

Algorytm opisowy do generowania dywanu Sierpińskiego

Dywan Sierpińskiego otrzymujemy z kwadratu przez podzielenie go na dziewięć mniejszych kwadratów (3 x 3). Następnie środkowy kwadrat zostaje zamalowany. Ponownie rekurencyjnie wywołujemy tę funkcję dla każdego z pozostałych kwadratów.

Przykład 1

Spróbujmy zdefiniować algorytm tworzenia geometrycznej prezentacji:

dywan_sierpinskiego(stopien, dlugosc_boku)

    jeśli stopien jest równy 0
        narysuj kwadrat o dlugosc_boku w kolorze turkusowym
        zakończ
    w innym przypadku
        narysuj kwadrat o dlugosc_boku w kolorze białym
        powtórz 4 razy
            powtórz 2 razy
                wywołaj dywan_sierpinskiego(stopien-1, dlugosc_boku/3)
                przesuń się do przodu o dlugosc_boku/3

            przesuń się do przodu o dlugosc_boku/3
            obróć się w prawo o 90 stopni

Na podstawie powyższego opisu zapiszemy kod funkcji:

def dywan_sierpinskiego(z, stopien, dl_bok):

    def kwadrat(bok, kolor):
        z.color(kolor)
        z.begin_fill()
        for i in range(4):
            z.forward(bok)
            z.right(90)
        z.end_fill()

    if stopien == 0:
        kwadrat(dl_bok, 'black')
        return None
    else:
        kwadrat(dl_bok, 'white')
        for i in range(4):
            for j in range(2):
                dywan_sierpinskiego(z, stopien-1, dl_bok/3)
                z.forward(dl_bok/3)
            z.forward(dl_bok/3)
            z.right(90)

Efekt wykonania algorytmu wygląda następująco:

# poniższe wiersze niezbędne są dla wykonania
from turtle import Turtle
zl = Turtle()

# przenosimy żółwia w konkretne miejsce układu współrzędnych
# aby narysowany obraz dobrze mieścił się w oknie
zl.penup()
zl.goto(-300,300)
zl.pendown()

dywan_sierpinskiego(zlw, 3, 500)

R11c8pYfgKo8V

Zdjęcie ukazuje efekt wykonania algorytmu. Dywan Sierpińskiego w kształcie kwadratu. Z środka został usunięty zbiór w kształcie kwadratu, następnie dla kolejnych części usuwane są coraz mniejsze zbiory w kształcie kwadratów. — Dywan Sierpińskiego - efekt po wykonaniu kilku pierwszych kroków
Źródło: Contentplus.pl Sp. z o.o., licencja: CC BY-SA 3.0.

Słownik

fraktal

(łac. fractus – złamany, cząstkowy, ułamkowy) obiekt składający się z coraz bardziej złożonych detali, z których każdy jest podobny do całości

przestrzeń nazw

(ang. namespace) miejsce w pamięci operacyjnej, w której jest przechowywana dana zmienna; najczęściej przestrzeń nazw wiąże się z funkcją, a zmienne używane w niej są widoczne tylko w obrębie tej przestrzeni – jest to „zakres obowiązywania” tych zmiennych

rekurencja

proces polegający na wywoływaniu funkcji przez siebie samą do momentu rozwiązania określonego zadania

turtle

(z ang. żółw) moduł (standardowa biblioteka) w języku Python realizujący grafikę żółwia

Animacja: dywan Sierpińskiego

Generowania zbioru Cantora w Pythonie

Algorytm opisowy do generowania dywanu Sierpińskiego

Słownik