Circle Packing

Wie viele Orangen passen in eine Kiste? Wie legt man Kreise so, dass sie möglichst viel Fläche bedecken, ohne sich zu überlappen? Diese Fragen nach dem Packen von Kreisen beschäftigen Mathematikerinnen und Mathematiker seit Jahrhunderten – und sie ergeben schöne Bilder.

Unser Verfahren ist einfach: Setze einen winzigen Kreis an eine zufällige freie Stelle. Lass ihn wachsen, bis er an einen anderen Kreis oder an den Rand stößt. Wiederhole das ein paar hundert Mal.

Vorwissen: Klassen und Objekte, eindimensionale Felder und – wie so oft – der Satz des Pythagoras.

Kreise als Objekte

Ein Kreis hat eine Mitte (x, y) und einen Radius. Das ist ein Fall für eine eigene Klasse Kreis. Alle Kreise, die schon auf der Leinwand liegen, merken wir uns in einem Feld kreise. Weil wir vorher nicht wissen, wie viele es werden, legen wir das Feld groß genug an und zählen in anzahl mit, wie viele Plätze schon belegt sind.

Und wie zeichnet ein Stift, der nur gerade Linien kann, einen Kreis? Er zeichnet ein Vieleck mit so vielen Ecken, dass man den Unterschied nicht mehr sieht. Die Ecke Nummer i eines n-Ecks liegt beim Winkel 2π · i / n und hat die Koordinaten

x = mx + r · cos(winkel) und y = my + r · sin(winkel).

a) Setze ECKEN auf 3, 4, 6 und 10. Ab wie vielen Ecken sieht ein kleiner Kreis rund aus? Und ein großer?

b) Die Schleife in zeichneKreis läuft bis i <= ECKEN, nicht bis i < ECKEN. Warum?

c) Das Programm legt erst alle Kreise im Feld ab und zeichnet sie danach. Das ginge auch in einer einzigen Schleife. Warum lohnt sich das Feld trotzdem? Die Antwort steht im nächsten Abschnitt.

Wachsen, bis es eng wird

Zwei Kreise überlappen sich, wenn der Abstand ihrer Mittelpunkte kleiner ist als die Summe ihrer Radien. Den Abstand liefert der Satz des Pythagoras:

abstand = √(dx² + dy²) mit dx = x₁ − x₂ und dy = y₁ − y₂

Diese Prüfung gehört zum Kreis selbst, deshalb bekommt die Klasse Kreis zwei neue Methoden: ueberschneidet vergleicht mit einem anderen Kreis, ragtUeberRand prüft die Leinwand.

Der Ablauf für jeden neuen Kreis ist dann:

Würfle eine Stelle und probiere dort einen Kreis mit dem Radius MIN_RADIUS. Stößt er an, würfle neu – höchstens VERSUCHE-mal.
Lass den Kreis Bildpunkt für Bildpunkt wachsen, bis er anstößt oder MAX_RADIUS erreicht. Dann nimm den letzten Radius, bei dem noch Platz war.
Lege ihn ins Feld und zeichne ihn.

a) In erzeugeKreis steht return; mitten in der Methode. Wann wird es erreicht, und was bedeutet das für die Anzahl der Kreise im Bild?

b) Setze MAX_RADIUS auf 20 und auf 200. Wie verändert sich der Charakter des Bildes?

c) Füge in stoesstAn einen Zähler hinzu, der mitzählt, wie oft ueberschneidet aufgerufen wird, und gib ihn am Ende des Konstruktors mit IO.println(...) aus. Wie verändert sich die Zahl, wenn du ANZAHL_KREISE verdoppelst?

d) Begründe: Warum dauert der hundertste Kreis länger als der erste?

Tipp zu c)

Der Zähler muss ein Attribut sein, keine lokale Variable in stoesstAn – sonst fängt er bei jedem Aufruf wieder bei 0 an.

Tipp zu d)

Schau dir die Schleife in stoesstAn an. Wie oft läuft sie, wenn schon 99 Kreise im Feld liegen? Und wie oft wird stoesstAn beim Wachsen eines einzigen Kreises aufgerufen?

Weiterspielen

Schneller wachsen. Statt den Radius Bildpunkt für Bildpunkt zu vergrößern, kann man ihn direkt ausrechnen: Der größte erlaubte Radius ist der kleinste Wert aus „Abstand zum anderen Kreis minus dessen Radius“ über alle Kreise – und dem Abstand zum nächsten Rand. Baue das ein und miss mit dem Zähler aus Aufgabe c), wie viel du sparst.

Gefüllte Kreise. Fülle jeden Kreis, indem du mehrere Kreise mit abnehmendem Radius ineinander zeichnest. Gib großen und kleinen Kreisen verschiedene Farben.

Kreise in Kreisen. Erlaube, dass ein Kreis innerhalb eines großen Kreises entsteht, solange er dessen Rand nicht berührt. Wann liegt ein Kreis vollständig in einem anderen?

Form vorgeben. Lass Kreise nur dort entstehen, wo eine Bedingung erfüllt ist – etwa innerhalb eines großen Kreises, in der Form eines Buchstabens oder in einem Herz. Der Rest der Leinwand bleibt leer.

Nach dem Tutorial Circle Packing von Generative Artistry.