Aus Das deutschsprachige Scratch-Wiki

Man kann natürlich im Malprogramm Kreise malen. In diesem Tutorial geht es aber nicht darum, sondern ich will dir zeigen, wie man Scratch beibringen kann, dass ein Kreis gezeichnet werden soll.

Ein Kreis ist eine Menge, die aus unendlich vielen Punkten besteht, die von einem Punkt (nämlich dem Mittelpunkt) den gleichen Abstand haben. Dieser Abstand wird Radius genannt.

Um einen "schönen Kreis" zu zeichnen, muss man also ausreichend viele (nicht unendlich viele, sonst endet der Algorithmus nicht) Punkte entlang eines kreisförmigen Weges setzen.

Um einen Kreis zu zeichnen, gibt es verschiedene Algorithmen. Der einfachste wird im Artikel Mein erstes Programm verwendet:

360-Schritte-Algorithmus

Eine Kreislinie entsteht durch einen Weg, der 360 Mal abbiegt.

schalte Stift ein
wiederhole (360) mal
gehe (1)er-Schritt
drehe dich im Uhrzeigersinn um (1) Grad
ende
schalte Stift aus

Der Nachteil dieses Algorithmus ist offensichtlich: Der "Radius" kommt darin nicht vor. Es wird also immer der gleiche Kreis.
Auch ist es schwierig, vorab den Mittelpunkt festzulegen. Dieser "entsteht" erst während des Zeichnens als "gedachte Mitte".

360-Punkte-Algorithmus

360-mal geht ein Punkt zum Mittelpunkt und zeigt immer in verschiedene Richtungen und geht "Radius" Schritte nach vorn. Hier wird nun ein Abdruck hinterlassen. Dazu muss es natürlich eine Figur (bzw. Sprite) geben, die nur aus einem Punkt besteht.

Definiere Kreis (Mittelpunkt_X) (Mittelpunkt_Y) (Radius)
setze [Drehrichtung v] auf [-180]
wiederhole (361) mal
gehe zu x: (Mittelpunkt_X) y: (Mittelpunkt_Y)
setze Richtung auf (Drehrichtung)
gehe (Radius)er-Schritt
hinterlasse Abdruck
ändere [Drehrichtung v] um (1)
ende

Die Nachteile dieses Algorithmus:

  • Bei größeren Radien ist die Kreislinie nicht geschlossen.
  • Das Zeichnen kleiner Kreise benötigt genau so lange wie größere Kreise: Es werden stur 361 Punkte gesetzt.

2629646_144x108.png

Tutorial- Kreise

Parametrischer Algorithmus

Jeder Punkt des Kreises hat die Koordinaten [r*cos(phi)|r*sin(phi)]. Huch! Wie das? Vertraue mir, du wirst es in der Schule lernen, Stichwort "Polarkoordinaten" bzw. "Parameterdarstellung eines Kreises". "cos" bezeichnet die Cosinus-Funktion, "sin" den Sinus. Beide gibt es in Scratch unter "Operatoren" als Auswahl dort, wo "Wurzel" steht.

Wenn man phi also von 0 bis 360 durchläuft, kann man die Koordinaten der Punkte auf der Kreislinie berechnen.

Wieviele Pixel benötigt man, damit eine durchgehende Linie entsteht?
Der Kreisumfang wird mit der Formel 2*Radius*Pi berechnet. Die Zahl Pi ist ungefähr 3.142, 2*Pi folglich 6.284. Man benötigt also 6.3*Radius Pixel, um eine durchgehende Linie zu erhalten. Wir müssen also für phi nicht nur 360 Werte, sondern für Radius=100 630 Werte verwenden, für Radius=50 hingegen nur 315.

Definiere Kreis (Mittelpunkt_X) (Mittelpunkt_Y) (Radius)
setze [Anzahl v] auf (((6.3) * (Radius)) gerundet)
setze [Zähler v] auf [0]
wiederhole bis <(Zähler) > (Anzahl)>
setze [phi v] auf (((360) * (Zähler)) / (Anzahl))
gehe zu x: ((Mittelpunkt_X) + ((Radius) * ([cos v] (phi)))) y: ((Mittelpunkt_Y) + ((Radius) * ([sin v] (phi))))
hinterlasse Abdruck
ändere [Zähler v] um (1)
ende 

Dieser Algorithmus kann deutlich verbessert werden, wenn man die radiale Symmetrie des Kreises ausnutzt: Wenn [x|y] ein Punkt des Kreises ist, dann sind auch [x|-y], [-x|y], [-x|-y], [y|x], [y|-x], [-y|x], [-y|-x] Punkte des Kreises und können ohne weitere Berechnungen sofort gezeichnet werden. Das heißt insbesonders, dass man nur die Punkte eines Achtelkreises berechnen muss. (Dies verwendet auch der unten erklärte Bresenham-Algorithmus.) Wir berechnen die Werte also nur von 0 bis 45 Grad und benötigen dementsprechend auch nur ein Achtel der Werte. Und der Algorithmus wird fast achtmal so schnell! Juchu!


Definiere SetzePunkt (x) (y)
gehe zu x: (x) y: (y)
schalte Stift ein
schalte Stift aus

Definiere Kreis (Mittelpunkt_X) (Mittelpunkt_Y) (Radius)
setze [Anzahl v] auf (((0.7854) * (Radius)) gerundet)
setze [Zähler v] auf [0]
wiederhole bis <(Zähler) > (Anzahl)>
setze [phi v] auf (((360) * (Zähler)) / (Anzahl))
setze [X v] auf ((Radius) * ([cos v] (phi)))
setze [Y v] auf ((Radius) * ([sin v] (phi)))
SetzePunkt ((Mittelpunkt_X) + (X)) ((Mittelpunkt_Y) + (Y)) 
SetzePunkt ((Mittelpunkt_X) + (X)) ((Mittelpunkt_Y) - (Y)) 
SetzePunkt ((Mittelpunkt_X) - (X)) ((Mittelpunkt_Y) + (Y)) 
SetzePunkt ((Mittelpunkt_X) - (X)) ((Mittelpunkt_Y) - (Y)) 
SetzePunkt ((Mittelpunkt_X) + (Y)) ((Mittelpunkt_Y) + (X)) 
SetzePunkt ((Mittelpunkt_X) + (Y)) ((Mittelpunkt_Y) - (X)) 
SetzePunkt ((Mittelpunkt_X) - (Y)) ((Mittelpunkt_Y) + (X)) 
SetzePunkt ((Mittelpunkt_X) - (Y)) ((Mittelpunkt_Y) - (X)) 
ändere [Zähler v] um (1)
ende 


Dieser Algorithmus hat einen Nachteil: Winkelfunktionen (Sinus, Cosinus) sind aufwändig zu berechnen. Auch wird hier mit Kommazahlen gerechnet, was im Computer länger dauert als mit ganzen Zahlen (also Zahlen ohne Kommastellen). Und schließlich gibt es auf der Bühne nur ganzzahlige Werte für x und y.

Ob du die Punkte so

Definiere SetzePunkt (x) (y)
gehe zu x: (x) y: (y)
hinterlasse Abdruck

oder so

Definiere SetzePunkt (x) (y)
gehe zu x: (x) y: (y)
schalte Stift ein
schalte Stift aus

setzen willst, ist Geschmackssache. Der zweite Punktsetze-Algorithmus hat den Vorteil, das hier über den Malstift sehr einfach die Farbe und die Dicke der Linie geändert werden kann.

Bresenham-Kreis-Algorithmus

Es geht noch anders. Jeder Punkt des Kreises hat Koordinaten (also x und y) und den gleichen Abstand zum Mittelpunkt (den Radius, abgekürzt r). Mit dem Satz des Pythagoras gilt x2 + y2 = r2 (wenn der Mittelpunkt in [0|0] liegt). Damit ist x2 + y2 - r2 = 0, wenn der Punkt am Kreis liegt, <0 für Punkte innerhalb des Kreises und >0 für Punkte außerhalb des Kreises. Mit diesem Kriterium wird entschieden, ob der nächstgelegene Pixel des Bildschirms (auf einen Zick-Zack-Weg) zur Kreislinie dazu kommen soll oder nicht.

Dieser Algorithmus hat den Vorteil, dass er nur mit ganzen Zahlen rechnet und damit keine Rundungsfehler hat. Auch benötigt er keine einzige Multiplikation. Die damit gezeichneten Kreise sind auch bei riesigen Radien exakt und "schön". Dieser Algorithmus wird in Plottern, in den Grafikchips moderner Grafikkarten und in vielen Grafikbibliotheken verwendet.

Definiere SetzePunkt (x) (y)
gehe zu x: (x) y: (y)
schalte Stift ein
schalte Stift aus

Definiere Kreis (Mittelpunkt_X) (Mittelpunkt_Y) (Radius)
setze [f v] auf ((1) - (Radius))
setze [x v] auf [0]
setze [y v] auf [Radius]
SetzePunkt (Mittelpunkt_X) ((Mittelpunkt_Y) + (Radius)) 
SetzePunkt (Mittelpunkt_X) ((Mittelpunkt_Y) - (Radius)) 
SetzePunkt ((Mittelpunkt_X) + (Radius)) (Mittelpunkt_Y) 
SetzePunkt ((Mittelpunkt_X) - (Radius)) (Mittelpunkt_Y) 
wiederhole bis <<(x) > (y)> oder <(x) = (y)>>
ändere [x v] um (1)
falls <(f) < [0]> dann
ändere [f v] um (((x) + (x)) - (1))
sonst
ändere [f v] um ((x) - (y))
ändere [f v] um ((x) - (y))
ändere [y v] um (-1)
ende
SetzePunkt ((Mittelpunkt_X) + (x)) ((Mittelpunkt_Y) + (y)) 
SetzePunkt ((Mittelpunkt_X) + (x)) ((Mittelpunkt_Y) - (y)) 
SetzePunkt ((Mittelpunkt_X) - (x)) ((Mittelpunkt_Y) + (y)) 
SetzePunkt ((Mittelpunkt_X) - (x)) ((Mittelpunkt_Y) - (y)) 
SetzePunkt ((Mittelpunkt_X) + (y)) ((Mittelpunkt_Y) + (x)) 
SetzePunkt ((Mittelpunkt_X) + (y)) ((Mittelpunkt_Y) - (x)) 
SetzePunkt ((Mittelpunkt_X) - (y)) ((Mittelpunkt_Y) + (x)) 
SetzePunkt ((Mittelpunkt_X) - (y)) ((Mittelpunkt_Y) - (x)) 
ende 


188663_144x108.png

Fast circle algorithm

49800724_144x108.png

Bresenham's Circle Drawing Algorithm