Startseite   |  Site map   |  A-Z artikel   |  Artikel einreichen   |   Kontakt   |  
  


mathematik artikel (Interpretation und charakterisierung)

Algorithmus

Der algorithmus von bresenham



Das Bresenham-Verfahren beruht im wesentlichen auf zwei grundsätzliche

Beobachtungen:



- Es reicht ein Verfahren aus um Geraden mit einer

Steigung im Bereich von null bis eins darzustellen.



- Es kommen für die Linie prinzipiell immer nur zwei Punkte in Frage, die als nächstes gezeichnet werden

dürfen.










Originaldokument enthält an dieser Stelle eine Grafik!
Original document contains a graphic at this position!


Die erste Behauptung läßt sich einfach erklären. Wenn eine Gerade eine Steigung von minimal null und maximal eins hat, dann liegt sie zwischen

einer Waagerechten und einer Geraden, die einen Winkel von 45 Grad mit


der X-Achse einschließt.

Es gibt natürlich auch Geraden mit einer steileren Steigung als eins. Doch alle diese Geraden kann man auch erhalten, indem man eine Gerade mir der Steigung null bis eins um die Winkelhalbierende spiegelt. Dies kann man leicht

erreichen, indem man die X- und Y- Koordinaten austauscht.

Bleiben noch Geraden mit einer negativen Steigung, also \"fallende\" Geraden,

übrig. Doch auch diese lassen sich herleiten, indem man die entsprechende Gerade an der X-Achse spiegelt. Das erreicht man durch das Umdrehen des Vorzeichens der Y-Koordinate.



Die zweite wichtige Voraussetzung des Algorithmus basiert nun auf der erstgenannten. Sie besagt, daß bei allen Geraden die aufwendigen Berechnungen unter Einbeziehung der Steigung überflüssig sind. Wenn man vom Anfangspunkt einer \"Grund-Geraden\" ausgeht, kommen generell nur zwei Punkte in Frage, die als nächste gezeichnet werden dürfen.

Beginnend mit dem Anfangspunkt wird kontinuierlich entschieden, ob der rechts davon liegende Punkt A oder B dargestellt werden muß. Von diesem Punkt wird wieder weiter entschieden.



Jetzt stellt sich die Frage wie entschieden wird?

Dazu muß herausgefunden werden, welcher Punkt, A oder B, näher der tatsächlichen Gerade liegt. Es wird von der Geradengleichung y = kx + d

ausgegangen. Bei der Bresenham-Methode wird der Einfachheit halber davon

ausgegangen, daß der Anfangspunkt der Gerade durch den Ursprung geht.

Daher wird d zu null und die Gleichung vereinfacht sich zu: y = kx


Originaldokument enthält an dieser Stelle eine Grafik!
Original document contains a graphic at this position!


Der Bresenham-Algorithmus berechnet die Koordinaten jedes einzelnen Punktes, indem vom zuletzt gezeichneten Punkt ausgegangen wird. Der Punkt P

besitzt die Koordinaten X und Y. Als nächster Punkt kommt entweder A oder B

mit den Koordinaten X+1 und Y+1 bzw. X+1 und Y.



Der Punkt A liegt oberhalb der tatsächlichen Geraden. Die tatsächliche Y-Koordinate an der Stelle X ergibt sich aus der Geradengleichung:

y = kx Daher beträgt der Abstand des Punktes A zu dieser Koordinate

a = y + 1 - kx



Ähnlich läßt sich auch b berechnen. Der Punkt B liegt unterhalb des exakten Punktes der Gerade. b = kx - y



Jetzt kann leicht entschieden werden, welcher Punkt gezeichnet wird.

Ist a kleiner b wird A gezeichnet. Ist b kleiner a wird B gezeichnet.

Es ist also wichtig die Differenz zu berechnen:



b - a = kx - y - (y + 1 - kx)



Die Steigung kann man aus dem Quotienten der Differenzen der Koordinaten

berechnen.

Y2 - Y1 DY

k = ------------- = ------

X2 - X1 DX



Diesen Term setzt man nun in den Ausdruck (b-a) ein:



DY DY

b - a = ------ x - y - (y + 1 - ------ x)

DX DX



Diesen Ausdruck kann man vereinfachen:

DY

Klammer auflösen -> b - a = 2 ------ x - 2y - 1

DX



---> (b - a) DX = 2 (DY x - y DX) - DX



Der Trick beim Bresenham-Algorithmus liegt nun darin, daß man die Differenz

(b - a) nicht jedesmal völlig neu berechnet, sondern jeden neuen Punkt aus

der Differenz des letzten Punktes ableitet. Für den Ausdruck (a - b) ergibt sich an der Stelle Xi und Yi:



(bi - ai) DX = 2 (DY xi - yi DX) - DX



Für den nächsten Punkt ergibt sich analog dazu:



(bi+1 - ai+1) DX = 2 (DY xi+1 - yi+1 DX) - DX



Um festzustellen, wie man anhand von (bi - ai) DX den Ausdruck

(bi+1 - ai+1) DX berechnen kann, zieht man beide Terme voneinander ab:



(bi+1 - ai+1) DX - (bi - ai) DX = 2 (DY xi+1 - yi+1 DX) - DX -

( 2 (DY xi - yi DX) - DX)



Durch Umformung erreicht man daraus:



2 (DY xi+1 - yi+1 DX) - DX -2 (DY xi - yi DX) + DX



= 2 (DY xi+1 - yi+1 DX - (DY xi - yi DX)



= 2 (DY xi+1 - yi+1 DX - DY xi + yi DX)



= 2 (DY (xi+1 - xi) - DX(yi+1 - yi))



Da die X-Koordinaten immer nebeneinander liegen, gilt:



xi+1 - xi = 1



Jetzt setzt man Eins in den obigen Term ein:



2 (DY - DX (yi+1 - yi))



Entweder beträgt der Ausdruck null oder eins. Ein Wert von null tritt dann auf wenn Punkt B gesetzt wurde. In diesem Fall ist yi+1 - yi = 0 => 2 DY

Ein Wert von eins tritt dann auf wenn A gesetzt wurde. Es gilt yi+1 - yi = 1

=> 2 (DY - DX)





Die Differenz der beiden Alternativpunkte entweder 2 DY oder 2 DY - DX stellen Konstanten dar, die schon am Beginn des Programms einmal berechnet werden können, ebenfalls kann berechnet werden, welcher Alternativpunkt

gesetzt werden muß.









Das Programm in Pascal



Procedure Line (X1, Y1, X2, Y2: word; Farbe: byte);

Var

DX, DY, DAB : Integer;

IncA, IncB, IncY :Integer;

X, Y : Integer;


Begin If X2

 
 

Datenschutz
Top Themen / Analyse
indicator Prinzipielle Unschärfen bei den Meßwerten
indicator Einstein auf Arbeitsuche
indicator Albert EINSTEIN-
indicator Rauminhalt eines Rotationskörpers
indicator Die nichtlineare Gleichung
indicator Einstein selbst gab die vielzitierte Antwort:
indicator Einführung und Grundbegriffe
indicator Die Quadratwurzel
indicator Kurvendiskussion
indicator Binäre Bäume


Datenschutz
Zum selben thema
icon Funktionen
icon Einstein
icon Pythagoras
icon System
icon Algorithmus
icon Formel
icon Geometrie
A-Z mathematik artikel:
A B C D E F G H I J K L M N O P Q R S T U V W X Y Z #

Copyright © 2008 - : ARTIKEL32 | Alle rechte vorbehalten.
Vervielfältigung im Ganzen oder teilweise das Material auf dieser Website gegen das Urheberrecht und wird bestraft, nach dem Gesetz.
dsolution