Der Algorithmus von Bresenham - schulnote.de 
Akzeptieren

Unsere Webseite nutzt Cookies. Wenn Sie auf dieser Webseite bleiben, nehmen wir an, dass Sie damit einverstanden sind. Sie können unsere Cookies löschen. Wie das geht, erfahren Sie in unserer Datenschutzerklärung. Mehr erfahren



Impressum | Datenschutzerklärung Startseite




 Apache HTTP Server Test Page powered by CentOS

Apache 2 Test Page
powered by CentOS

This page is used to test the proper operation of the Apache HTTP server after it has been installed. If you can read this page it means that the Apache HTTP server installed at this site is working properly.


If you are a member of the general public:

The fact that you are seeing this page indicates that the website you just visited is either experiencing problems or is undergoing routine maintenance.

If you would like to let the administrators of this website know that you've seen this page instead of the page you expected, you should send them e-mail. In general, mail sent to the name "webmaster" and directed to the website's domain should reach the appropriate person.

For example, if you experienced problems while visiting www.example.com, you should send e-mail to "webmaster@example.com".

If you are the website administrator:

You may now add content to the directory /var/www/html/. Note that until you do so, people visiting your website will see this page and not your content. To prevent this page from ever being used, follow the instructions in the file /etc/httpd/conf.d/welcome.conf.

You are free to use the images below on Apache and CentOS Linux powered HTTP servers. Thanks for using Apache and CentOS!

[ Powered by Apache ] [ Powered by CentOS Linux ]

About CentOS:

The Community ENTerprise Operating System (CentOS) Linux is a community-supported enterprise distribution derived from sources freely provided to the public by Red Hat. As such, CentOS Linux aims to be functionally compatible with Red Hat Enterprise Linux. The CentOS Project is the organization that builds CentOS. We mainly change packages to remove upstream vendor branding and artwork.

For information on CentOS please visit the CentOS website.

Note:

CentOS is an Operating System and it is used to power this website; however, the webserver is owned by the domain owner and not the CentOS Project. If you have issues with the content of this site, contact the owner of the domain, not the CentOS Project.

Unless this server is on the centos.org domain, the CentOS Project doesn't have anything to do with the content on this webserver or any e-mails that directed you to this site.

For example, if this website is www.example.com, you would find the owner of the example.com domain at the following WHOIS server:

http://www.internic.net/whois.html





Titel:

Der Algorithmus von Bresenham


  Note: 2   Klasse: 11









Arbeit: 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.

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



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
Begin

Tausche (X1, X2); (* Die Koordinaten müssen ver- *)

Tausche (Y1, Y2); (* tauscht werden. *)

End;

If (Y1 < Y2) (* Steigung positiv ? *)

Then

IncY:=1 (* Y muß in der Schleife erhöht *)

Else (* werden *)

IncY:=-1; (* wenn nicht, Y abziehen *)

DX := X2-X1; (* Berechnung der Konstanten *)

DY := Y2-Y1; (* DX, DY, Differenz (a-b) *)

DAB := (DY SHL 1) - DX;

IncA := (DY - DX) SHL 1; (* Alternativwert für A und B *)

IncB := DY SHL 1;

X := X1;

Y := Y1;

Putpixel (X, Y, 2); (* Setze ersten Punkt *)

For X:= X1+1 To X2 Do

Begin

If DAB < 0 Then (* Es wurde zuletzt A gesetzt *)

Begin

Dab := Dab + IncB; (* Differenz ändern und *)

Putpixel (X, Y, 2); (* Punkt setzen *)

End

Else (* Es wurde zuletzt B gesetzt *)

Begin

Y := Y + IncY; (* Neue Koordinaten und *)

Dab := Dab + IncA; (* Differenz ändern *)

End;

End;

End;









Quelle:




ähnliche Referate Algorithmus
3D-Grafik
Der Algorithmus von Bresenham



Hier könnt Ihr die DRUCKANSICHT für das Referat öffnen




Tipp:







(c) schulnote.de 2004-2018

MEDIADATEN --- Besucher seit dem 01.09.2006
gesamt: 6726426 - heute: 1086 - gestern: 1082 - online: 9 - Rekord online: 340 - Rekord Tag: 2801


ID: 5700      Aufrufe seit dem 02.08.2011: 938