suchen...
Zeichnen einer Linie von A nach B
Gesucht ist ein Algorithmus, der alle Pixel berechnet, die zu einer Verbindungslinie zweier Punkte A nach B gehören. Beispiel: A(1,1) B(8,5)
| B | |||||||||
| A |
Strategie
Eine rekursive Lösung bedingt eine Abbruchbedingung und eine allgemeine Vorschrift, die zu einer Problemvereinfachung führt.
Abbruchbedingung:
wenn A und B benachbart, dann A und B markieren
sonst
Allg. Rekursionsvorschrift:
Berechne den Mittelpunkt (ganzzahlige Koordinaten)
und Zeichne folgende (kürzere) Linien:
Linie von A nach M
Linie von M nach B
Gemäß dieser Vorschrift erhält man folgende Zwischenschritte, aus denen die Baumstruktur hervorgeht:
1. Aufruf 2. Schritt 3. Schritt 4. Schritt 5. Schritt
/ L(1,1)-(2,2) = P[(1,1),(2,2)]
/
L(1,1)-(4,3)
/ \ / L(2,2)-(3,2) = P[(2,2),(3,2)]
/ \ L(2,2)-(4,3)
/ \ L(3,2)-(4,2) = P[(3,2),(4,2)]
/
L(1,1)-(8,5)
\ / L(4,3)-(5,3) = P[(4,3),(5,3)]
\ / L(4,3)-(6,4)
\ / \ L(5,3)-(6,4) = P[(5,3),(6,4)]
\L(4,3)-(8,5)
\ / L(6,4)-(7,4) = P[(6,4),(7,4)]
\ L(6,4)-(8,5)
\ L(7,4)-(8,5) = P[(7,4),(8,5)]
| B | |||||||||
| A |