-
        

Ergebnis 1 bis 4 von 4

Thema: kurzesten Weg ausrechnen

  1. #1
    Erfahrener Benutzer Roboter Experte
    Registriert seit
    08.02.2005
    Ort
    Freiburg
    Alter
    29
    Beiträge
    601

    kurzesten Weg ausrechnen

    Anzeige

    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
    Miniaturansichten angehängter Grafiken Miniaturansichten angehängter Grafiken linie2.gif   linie1.gif  
    -

  2. #2
    Erfahrener Benutzer Roboter Experte
    Registriert seit
    08.02.2005
    Ort
    Freiburg
    Alter
    29
    Beiträge
    601
    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 *

    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
    -

  3. #3
    Erfahrener Benutzer Roboter Genie
    Registriert seit
    19.02.2005
    Alter
    29
    Beiträge
    830
    ich verwende diesen für meinen linienschreiber:

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

    ich weiß nicht ob dieser schneller ist, genauer auf jeden fall, weil du dir kommastellen ersparen kannst
    Neun von zehn Stimmen in meinen Kopf sagen ich bin nicht verrückt. Die andere summt die Melodie von Tetris...

  4. #4
    Erfahrener Benutzer Roboter Experte
    Registriert seit
    08.02.2005
    Ort
    Freiburg
    Alter
    29
    Beiträge
    601
    Hi,

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

    Vielen Dank!

    Gruß,
    Mehto
    -

Berechtigungen

  • Neue Themen erstellen: Nein
  • Themen beantworten: Nein
  • Anhänge hochladen: Nein
  • Beiträge bearbeiten: Nein
  •