Menu

Barnsleys Fractal Top: Adressen

Was ist eine Adresse?

Ein IFS besteht aus endlich vielen kontrahierenden Abbildungen w₁, w₂,..., w_N. Wählt man eine unendliche Folge von Indizes s = (s₁, s₂, s₃,...) aus dem Alphabet {1,..., N} und wendet die zugehörigen Abbildungen nacheinander auf einen beliebigen Startpunkt x₀ an, also

x = lim_{n →∞} w_s1 ° w_s2 °... ° w_sn(x₀),

so konvergiert diese Folge - weil alle w_i Kontraktionen sind - gegen einen eindeutigen Punkt x des Attraktors, und zwar unabhängig davon, welchen Startpunkt man gewählt hat. Man sagt, s sei eine Adresse von x. Eine Adresse ist also nichts anderes als eine "Bauanleitung" für einen Punkt: die Reihenfolge der Abbildungen, mit der man ihn beliebig genau annähern kann.

Das ist dieselbe Idee wie bei einer Dezimalzahl: Die Ziffernfolge 0,3141... beschreibt eine reelle Zahl als Grenzwert immer feinerer Unterteilungen des Intervalls [0,1]. Bei einem IFS treten an die Stelle der zehn Ziffern die N Abbildungen - und an die Stelle des Intervalls der Attraktor.

Der Adressraum und die Codierungsabbildung

Die Menge aller möglichen unendlichen Indexfolgen bezeichnet man als Adressraum S = {1,..., N}^∞. Die Zuordnung, die jeder Adresse ihren Grenzpunkt zuweist,

heißt Codierungsabbildung. Sie ist stetig und surjektiv: Jeder Punkt des Attraktors A besitzt mindestens eine Adresse. Sie ist aber im Allgemeinen nicht injektiv - überlappen sich die Bilder der Abbildungen w_i, so kann ein und derselbe Punkt mehrere verschiedene Adressen besitzen, je nachdem, über welchen der sich überlappenden Teile man ihn erreicht.

Mehrdeutigkeit und die Top-Adresse

Für viele Anwendungen - insbesondere für das Color Stealing bei Fractal Tops - braucht man aber pro Punkt genau eine Adresse, sonst wäre nicht klar, welche Farbe übertragen werden soll. Barnsley löst das, indem er auf dem Adressraum eine Ordnung einführt (die Indizes 1,..., N werden der Größe nach geordnet und Adressen wie Zahlen lexikographisch verglichen) und für jeden Punkt aus allen seinen gültigen Adressen konsequent die - in dieser Ordnung - größte auswählt. Diese ausgezeichnete Adresse nennt er die top address des Punktes. Sie liefert eine eindeutige, konsistente Zuordnung Punkt → Adresse und ist damit die Grundlage dafür, dass Color Stealing überhaupt wohldefiniert ist.

In der folgenden Anwendung ist die Idee für eine Dimension anschaulich nachzuvollziehen. Die schwarze Linie zeigt das Intervall [0;1]. Die rote Linie zeigt das Intervall [0;0.6], die blaue Linie das Intervall [0.4;1]. Es gibt daher einen gemeinsamen Bereich zwischen 0.4 und 0.6.
Der rote Punkt in der Mitte bei 0.5 wurde zwölf mal iteriert. Je nachdem, ob der Punkt im ersten bzw. im zweiten Bereich landete.
Im ersten Fall gilt (x,y) → (0.6·x , 0.6·y),
im zweiten Fall (x,y) → (0.6·x+0.4 , 0.6·y+0.4)
Fällt der Punkt auf den gemeinsamen Bereich, dann wird die Top-Adresse 2 gewählt. Die Adresse ist somit eindeutig und besteht hier aus den 12 Ziffern: 211211121112.
Setzt man mit der Maus einen weitere Punkte auf das Intervall, dann werden wieder 12 Iterationen auf eben diesen Werte Punkt angewandt und der Ergebnis-Punkt plus Adresse angezeigt. Die Farben alternieren, damit man die Zugehörigkeiten besser erkennt. Klickt man auf einen gegebenen Wert des Intervalls ein zweites Mal, so wird die gleiche Adresse und der gleiche Ergebnis-Punkt angezeigt.

Adressen und Selbstähnlichkeit

Der Adressraum macht die Selbstähnlichkeit eines Attraktors direkt ablesbar: Alle Punkte, deren Adresse mit demselben Präfix σ₁... σ_k beginnt, liegen in derselben - um den Faktor der jeweiligen Kontraktionen verkleinerten - Kopie des gesamten Attraktors, nämlich in
Eine zusätzliche Adressziffer entspricht also einem Zoomschritt eine Ebene tiefer in die Selbstähnlichkeit des Fraktals. Genau diese Struktur ist es, die zwei IFS mit gleicher Abbildungsanzahl über ihren gemeinsamen Adressraum koppelt - die Voraussetzung für das Color Stealing aus einem vorigen Kapitel Chaos Game IFS Colorstealing.

Dort wurde ein IFS aus vier affinen Abbildungen behandelt, das einen "Barnsley-Farn" (siehe unten) erzeugt. Wir ändern die erste - für den roten Stiel verantwortliche - affine Abbildungen geringfügig, so dass auch diese umkehrbar ist.
In der Farn-App unten kann man sich durch klicken auf einen Punk die Adresse dieses Punktes auf eine Tiefe von 12 Ziffern anzeigen lassen. Nehmen wir an, die angezeigte Adresse sei [2,2,0,3,3,1,1,2,2,0,3,0]. Dann wäre die Reihenfolge der Abbildungen durch 0,3,0,2,2,1,1,3,3,0,2,2 gegeben.

(Eventuell kurz warten, bis der Farn fertig gezeichnet ist!)
Wie aber kann man die vorherige Abbildungsnummer berechnen?
Wir benötigen die Umkehrabbildungen (externer Link) der einzelnen affinen Abbildungen.
Das heißt, man muss für jede der vier Abbildungen den Abbstand zu allen Attraktorpunkten bestimmen. Hat die Abbildung mit Nummer k den minimalen Abstand, dann ist diese Nummer k der nächste Adresseintrag. Und nun beginnt das Spiel von vorn. Und zwar so lange, bis die gewünschte Adresstiefe erreicht ist.
Die Methode ist allenfalls für einzelne Punkte durchführbar, denn der Rechenaufwand ist gewaltig!

Hier können die beiden Sketche heruntergeladen werden:


Sketch Topadresse

Sketch TopAdressExtraktor

Menu