Równoległe Układy Funkcji: Szylkowa Solnica i Gra Chaosu |……

Kontrakcje odwrotne i zbioru zwłok

Podstawą działania IFS jest Twierdzenie o Punktie Stałym Banacha: każda kontrakcja odwrotna ma unikalny punkt stały, a powtarzalne zastosowanie zbiega się do niego z dowolnej pozycji. (IFS to system funkcji iterowanych, który składa się z skończonej liczby przekształceń odwrotnych {f₁, …, fₙ} na ℝⁿ, zwykle afinowych (fᵢ(x) = Aᵢx + bᵢ, gdzie wszystkie wartości własne Aᵢ są mniejsze niż 1). Zbiór zwłok A jest jedynym zwartym zbiorem spełniającym: A = f₁(A) ∪ f₂(A) ∪ ... ∪ fₙ(A) Rozpoczynając od dowolnego zbioru zwłok S₀: S_{k+1} = f₁(Sₖ) ∪ ... ∪ fₙ(Sₖ) → A (metryka Hausdorffa, wykładniczo szybki). Niezależnie od tego, czy zaczynamy od punktu, wypełnionej kwadratu, czy losowego zarysyku, orbitę zbiega się do tej samej zbioru zwłok – cecha samopodobieństwa definicji.

A = f₁(A) ∪ f₂(A) ∪ ... ∪ fₙ(A)

Starting from ANY compact set S₀:
S_{k+1} = f₁(Sₖ) ∪ ... ∪ fₙ(Sₖ)  →  A  (Hausdorff metric, exponentially fast)

Gra chaosu

Śledzenie wykładniczych zbiorów rosnących jest niepraktyczne, dlatego gra chaosu Michała Barnsley'a (1988) śladem pojedynczej losowej orbity zamiast tego: wybieramy transformację losowo, ważoną przez prawdopodobieństwo pᵢ, stosujemy ją, rysujemy punkt, powtarzamy to setki tysięcy razy (pomijając pierwsze ~20 dla rozgrzewki). Naturalnym wyborem prawdopodobieństwa jest pᵢ ∝ |det(Aᵢ)|, proporcjonalny do obszaru, który każda transformacja pokrywa, co daje jednorodną gęstość na zbiorze zwrotnym. Cały algorytm działa w czasie O(N) – każdy IFS fractal wyświetla się w milisekundach.

demo na żywo · powiązana symulacja● LIVE

Żuka Barnsley: cztery transformacje, jedna frędzierzna

Dzięki czterem transformacjom afinowym otrzymujemy strukturę identyczną z prawdziwą frędzlą paproci – jedna (p=0.01) skurcza całą frędzlę do małej łodygi, kolejna (p=0.85) kopiuje frędzlę w skali 85% dla głównego pnia, a dwie pozostałe (p=0.07 każda) generują lewe i prawe liście, obrócone o około 83° i 37°. Prawdopodobieństwa kodują względny ciężar każdej transformacji w obszarze przyciądzanym – ustawiając je wszystkie równo, chaosowa gra nadal zbiega się do tej samej formy frędzli, ale łodyga i liście są nadmiernie próbkowane, podczas gdy główny pniak jest pozbawiony punktów.

Wymiar fraktali i twierdzenie kolacji

Dla samopowtarzalnego odwzorowania (IFS) spełniającego warunek otwartego zbioru (nie nakładają się transformowane kopie), wymiar Hausdorffa d rozwiązuje równanie Morana Σᵢ rᵢᵈ = 1, gdzie rᵢ jest współczynnikiem zwężenia każdej transformacji – co daje wymiar trójkąta Sierpińskiego log(3)/log(2) ≈ 1.585 i krzywej Koch log(4)/log(3) ≈ 1.262. Rozwiązanie problemu w odwrotnym kierunku to Twierdzenie Kolacji: jeśli można pokryć docelowy obraz transformowanymi kopiami z dokładnością ε, to IFS przybliża ten obraz z błędem ograniczonym do ε/(1−c), gdzie c jest największym współczynnikiem zwężenia. Jest to podstawa kompresji obrazów fraktalnych – kodowania obrazu jako małego zbioru samopowtarzalnych transformacji zamiast surowych pikseli.

Frequently asked questions

Co to jest Iterated Function System?

Iterated Function System (IFS) to skończony zbiór przekształceń zwężających, zazwyczaj transformacji afinowych, którego unikalny punkt stały w przestrzeni zwartych zbiorów to fraktalny łowisko A spełniający równanie A = f1(A) ∪ f2(A) ∪ ... ∪ fn(A). Rozpoczynając od dowolnego kształtu i wielokrotnie stosując te przekształcenia, dąży się do tego samego łowiska niezależnie od punktu początkowego.

Jak chaos game renderuje fraktal IFS?

Zamiast śledzić wykładniczo rosnące zbiory, chaos game śledzi pojedynczą losową orbitę: zaczynając od dowolnego punktu, wielokrotnie wybiera się losowo jedno przekształcenie (zważone przez prawdopodobieństwo) i stosuje się je, a każdy nowy punkt jest rysowany po krótkim rozgrzewaniu. Po kilkuset tysiącach iteracji łowisko staje się widoczne, a algorytm działa w czasie O(N).

Co to jest Twierdzenie Collage?

Twierdzenie Collage to problem odwrotny: jeśli podano docelowy obraz i można go pokryć przekształconymi kopiami samego siebie (collage) z błędem epsilon, to wynikowy łowisko IFS będzie przybliżał się do celu z błędem ograniczonym do epsilon podzielonego przez (1 minus maksymalny współczynnik zwężenia). Jest to podstawa matematyczna kompresji obrazów fraktalnych.

Wypróbuj na żywo

Wszystko powyżej działa bezpośrednio w Twojej przeglądarce — otwórz the simulation i zmieniaj parametry podczas działania. Nic nie jest instalowane ani przesyłane na serwer, cały model działa w jednej karcie.

▶ Otwórz symulację the simulation