Dreiecke füllen

Ein Dreieck füllen heißt entscheiden, welche Pixel innerhalb seiner drei Kanten liegen. Fast jede Fläche am Bildschirm, ob Figur oder Gelände, wird aus solchen Dreiecken zusammengesetzt.

Wer einen Test für ein einzelnes Pixel hat, kann jede Fläche füllen und sie sogar sanft einfärben. Beides lernen Sie in dieser Lektion mit einfachen Zahlen.

Jede Kante des Dreiecks teilt die Fläche in zwei Hälften. Für die Kante von A nach B und ein Pixel P rechnen Sie so. Nehmen Sie (bx minus ax) mal (py minus ay). Ziehen Sie davon (by minus ay) mal (px minus ax) ab.

Das Beispiel nutzt A (0, 0), B (4, 0) und C (0, 4). Das Ergebnis ist positiv auf der einen Seite, negativ auf der anderen und null genau auf der Kante. Ein Pixel liegt im Dreieck, wenn die drei Werte dasselbe Vorzeichen haben oder null sind.

Außerhalb des kleinsten Rechtecks um das Dreieck kann kein Pixel innen liegen. Das Programm läuft darum Zeile für Zeile nur über dieses Rechteck und prüft jedes Pixel mit den drei Kantenwerten.

Das Beispiel hat die Ecken A (1, 1), B (7, 1) und C (1, 5). Die Zeilen sind unterschiedlich lang, weil das Dreieck schräge Kanten hat. Zählen Sie sie, und Sie kennen die Fläche in Pixeln.

# Zählt die Pixel im Dreieck A(0, 0), B(4, 0), C(0, 4).
def kante(ax, ay, bx, by, px, py):
    return (bx - ax) * (py - ay) - (by - ay) * (px - ax)

anzahl = 0
for y in range(-1, 6):
    for x in range(-1, 6):
        ab = kante(0, 0, 4, 0, x, y)
        bc = kante(4, 0, 0, 4, x, y)
        ca = kante(0, 4, 0, 0, x, y)
        if ab >= 0 and bc >= 0 and ca >= 0:
            anzahl = anzahl + 1
print("Pixel im Dreieck:", anzahl)
# Streichen Sie "and ca >= 0" und starten Sie erneut: Das Gebiet bleibt links offen.

Zum Vergleich füllt Pillow dasselbe Dreieck. Der erste Befehl druckt ein Bild mit 8 mal 8 Pixeln als Text. Die Zeilen enthalten fünf, vier, drei, zwei und ein #, danach drei Zeilen nur mit Punkten.

Das sind 15 Pixel, so viele wie Ihre Kantenwerte zählen. Pillow nimmt die Pixel auf der Kante mit.

docker exec jupyter python3 -c "from PIL import Image, ImageDraw; b = Image.new('L', (8, 8), 0); ImageDraw.Draw(b).polygon([(0, 0), (4, 0), (0, 4)], fill=255); print('\n'.join(''.join('#' if b.getpixel((x, y)) else '.' for x in range(8)) for y in range(8)))"

docker exec jupyter python3 -c "from PIL import Image, ImageDraw; a = Image.new('L', (10, 10), 0); ImageDraw.Draw(a).polygon([(1, 1), (7, 1), (1, 5)], fill=255); print(sum(1 for p in a.getdata() if p == 255))"

Teilen Sie die drei Kantenwerte eines Pixels durch den Kantenwert (A, B, C), das ist die doppelte Fläche des Dreiecks. Sie erhalten drei Gewichte, die zusammen 1 ergeben. Jede Ecke zählt so viel, wie das Pixel ihr nah ist.

Hat jede Ecke eine Farbe, mischt das Pixel diese Farben mit den Gewichten, wie in der Lektion zum Mischen. So entsteht ein sanfter Verlauf.

Der nächste Befehl färbt ein Dreieck mit 20 mal 20 Pixeln. Die Ecke oben links ist Rot, die Ecke oben rechts Grün und die Ecke unten links Blau. Dazwischen mischen die Gewichte.

Er speichert dreieck_farben.png: ein Dreieck mit sanftem Verlauf, die untere rechte Hälfte bleibt schwarz. Er gibt die drei Ecken aus und die Zahl der Dreieckspixel, 210.

docker exec jupyter python3 -c "import numpy as np; from PIL import Image; y, x = np.mgrid[0:20, 0:20]; ok = x + y <= 19; bild = (np.stack([(19 - x - y) / 19, x / 19, y / 19], axis=2) * 255 * ok[:, :, None]).astype('uint8'); Image.fromarray(bild).resize((200, 200), Image.NEAREST).save('dreieck_farben.png'); print(bild[0, 0], bild[0, 19], bild[19, 0], bild[19, 19], ok.sum())"