kurzesten Weg ausrechnen

[Mehto]

Es geht um folgendes:

Ich muss für eine Zeichenfunktion zwischen zwei Punkten den kürzesten Pixelweg ermitteln, so das die Linie möglichst gerade wird.
Problem ist das es möglichst schnell und einfach auf einem sehr beschäftigten Atmega162 laufen muss (für meinen Dipslaycontroller).


Das Programm weiß nur zwei positionen (x und Y koordinaten), muss dann ausrechnen wo es überall einen Punkt hin macht und gibt diese Postionen dann an ein anderes Unterprogramm weiter.


Hat jemand eine Idee wie man das am schnellsten machen könnte?

Im Anhang zwei Bidler wie es dann aussehen müste.

Gruß,
Mehto

[Mehto]

mhh, ich glaub Mathematisch habe ich es jetzt.

Ich rechne zuerst die x und Y Entferneung der Beiden Punkte aus.
Das sind dann 15 Pixel in X und -19 Pixel in Y Richtung.

Dann teile ich die x länge durch die Y länge, das sind -19/15= -1,26
Das ist dann die Steigung der Linie. Das heißt ich müste wenn ich eins nach rechts gehe 1,26 Pixel nach unten gehen.

Da ich aber nur Pixelweise setzen kann muss ich runden.

Das heißt, ich muss 1,26 nach unten, gehe aber nur eins, das ist ein Rest von 0,26. Dann muss ich wieder eins nach rechts und 1,26 nach unten gehe aber wieder nur ein Pixel nach unten, dann habe ich einen Rest von 0,52.

Und genau jetzt gehe ich eins nach rechts und ZWEI nach unten und habe einen Rest von -0,26 . Jetzt gehe ich einfach wieder nur so lange eins nach unten bis der Rest wieder größer als +0,5 ist. Wenn dann alles stimmt müste ich genau auf den anderen Punkt kommen.
*Juhu, ich glaube ich habe die lösung O:) *

Das einzigste Problem sind die Stellen hinterm komma und das Teilen. Das dauert dann zwar länger aber besser als keine Lösung.

Hat jemand eine noch schnellere Lösung?


Gruß,
Mehto

[user529]

ich verwende diesen für meinen linienschreiber:

http://wwwiti.cs.uni-magdeburg.de/~buchmann/privat/bresenham.htm

ich weiß nicht ob dieser schneller ist, genauer auf jeden fall, weil du dir kommastellen ersparen kannst

[Mehto]

Hi,

super, das ist genau das was ich brauche: Bresenham-Algorithmus

Vielen Dank!

Gruß,
Mehto