Bresenham-Algorithmus (in Arbeit): Unterschied zwischen den Versionen

Aus Geometrie-Wiki
Wechseln zu: Navigation, Suche
(→‎Aufstellen der Gleichungen)
(→‎Zusammenfassung)
 
(43 dazwischenliegende Versionen von einem Benutzer werden nicht angezeigt)
Zeile 3: Zeile 3:
 
==Motivation des Algorithmus==
 
==Motivation des Algorithmus==
  
−
Der Bresenham-Algorihtmus, ist ein Verfahren um Graden bzw. Kreise möglichst "gut" auf Anzeigegeräten zu zeichnen. Hier heisst "gut", dass die Abweichung zwischen dem gezeichneten und dem gedachten Objekt möglichst gering ist.
+
Der Bresenham Algorihtmus, ist ein Verfahren um Geraden möglichst "gut" auf Anzeigegeräten zu zeichnen. Hier heisst "gut", dass die Abweichung zwischen dem gezeichneten und dem gedachten Objekt möglichst gering ist.
  
−
Das Problem beim Darstellen einer Strecke auf einem Anzeigegerät ist, dass das erzeugte Bild nur durch endlich viele Punkte aufgebaut ist. Dadurch entstehen "Lücken" beim zeichnen. Da unser Auge nur eine endliche Auflösung verarbeiten kann, scheint uns ein Bild auf dem Monitor nicht durch einzelne Punkte aufgebaut zu sein, sondern es entstehen für uns geometrische Formen, die wir mit unserer Vorstellung von mathematischen Objekten in Einklang bringen können.
+
Das Problem beim Darstellen einer Strecke auf einem Anzeigegerät ist, dass das erzeugte Bild nur durch endlich viele Punkte aufgebaut ist, dadurch entstehen "Lücken" beim Zeichnen. Da unsere Augen nur eine endliche Auflösung verarbeiten können, scheint uns ein Bild auf dem Monitor nicht durch einzelne Punkte aufgebaut zu sein, sondern es entstehen für uns geometrische Formen, die wir mit unserer Vorstellung von mathematischen Objekten in Einklang bringen können.
 
<br />
 
<br />
 
<br />
 
<br />
Zeile 16: Zeile 16:
 
<br />
 
<br />
 
<br />
 
<br />
−
Hier sieht man dieselbe Gerade um das 8fache vergrößert.<br />
+
Hier sieht man dieselbe Gerade um das Achtfache vergrößert.<br />
 
<br />
 
<br />
 
<br />
 
<br />
Zeile 22: Zeile 22:
  
 
==Effektivität des Algorithmus==
 
==Effektivität des Algorithmus==
−
Dieser Algorithmus ist auch in heutiger Zeit, in seiner Geschwindigkeit und Einfachheit ungeschlagen, da die Rechenoperationen sich auf Addition und die Multiplikation mit zwei beschränken lässt. Dadurch kann dieser Rechenalgorithmus direkt in die Hardware der Grafikkarten implementiert werden.
+
Dieser Algorithmus ist auch in heutiger Zeit in seiner Geschwindigkeit und Einfachheit ungeschlagen, da sich die Rechenoperationen h auf Addition und die Multiplikation mit Zwei beschränken. Dadurch kann dieser Rechenalgorithmus direkt in die Hardware der Grafikkarten implementiert werden.
−
 
+
'''Potenzen:'''
 
Obwohl in den Rechentermen Potenzen auftreten, kann man diese umgehen.
 
Obwohl in den Rechentermen Potenzen auftreten, kann man diese umgehen.
 
Hierfür betrachten wir den Ausdruck:<br><br>
 
Hierfür betrachten wir den Ausdruck:<br><br>
Zeile 29: Zeile 29:
 
die zweite Binomische Formel liefert:<br><br>
 
die zweite Binomische Formel liefert:<br><br>
 
<math> (n - 1)^2 = n^2 - 2 \cdot n + 1 \ \Leftrightarrow n ^ 2 = ( n - 1)^2 + 2 \cdot n - 1</math><br\><br>
 
<math> (n - 1)^2 = n^2 - 2 \cdot n + 1 \ \Leftrightarrow n ^ 2 = ( n - 1)^2 + 2 \cdot n - 1</math><br\><br>
−
durch rekursives Anwenden dieser Formel lassen sich Potenzen solange vereinfachen bis die Basis Eins erreicht ist und damit die Potenz verschwindet.
+
durch rekursives Anwenden dieser Formel lassen sich Potenzen solange vereinfachen bis die Basis Eins erreicht ist und damit die Potenz verschwindet.<br><br>
  
−
Multiplikation mit zwei<br\>
+
'''Multiplikation mit Zwei''':<br\>
−
Eine Multiplikation mit der Zwei ist für einen Computer eine elementare Rechenoperation, da die sogenannte Shift Operation (Verrückungsoperation) durchgeführt werden kann.
+
Eine Multiplikation mit Zwei ist für einen Computer eine elementare Rechenoperation, da die sogenannte Shift Operation (Verrückungsoperation) durchgeführt wird.
  
 
Wir erinnern uns an die Darstellung von Zahlen im Binärsystem.
 
Wir erinnern uns an die Darstellung von Zahlen im Binärsystem.
Zeile 61: Zeile 61:
 
Hier wird die Zahl (im Dezimalsystem) dargestellt<br\><br\>
 
Hier wird die Zahl (im Dezimalsystem) dargestellt<br\><br\>
 
<math>  0 \cdot 2^7 + 1 \cdot 2^6 + 0 \cdot 2^5 + 0 \cdot 2^4 + 1 \cdot 2^3 +  1 \cdot 2^2 + 0\cdot 2^1 + 1 \cdot 2^0 = 77</math><br\><br\>
 
<math>  0 \cdot 2^7 + 1 \cdot 2^6 + 0 \cdot 2^5 + 0 \cdot 2^4 + 1 \cdot 2^3 +  1 \cdot 2^2 + 0\cdot 2^1 + 1 \cdot 2^0 = 77</math><br\><br\>
−
Multiplizerien wir nun mit zwei, so folgt:<br\><br\>
+
Multiplizerien wir nun mit Zwei, so folgt:<br\><br\>
 
<math>2 \cdot ( 0 \cdot 2^7 + 1 \cdot 2^6 + 0 \cdot 2^5 + 0 \cdot 2^4 + 1 \cdot 2^3 +  1 \cdot 2^2 + 0\cdot 2^1 + 1 \cdot 2^0 )  = 154</math><br\><br\>
 
<math>2 \cdot ( 0 \cdot 2^7 + 1 \cdot 2^6 + 0 \cdot 2^5 + 0 \cdot 2^4 + 1 \cdot 2^3 +  1 \cdot 2^2 + 0\cdot 2^1 + 1 \cdot 2^0 )  = 154</math><br\><br\>
 
<math> \Leftrightarrow </math><br\><br\>
 
<math> \Leftrightarrow </math><br\><br\>
Zeile 89: Zeile 89:
 
| 0
 
| 0
 
|}
 
|}
−
Vergleichen wir nun die Darstellung der Zahl 77 mit der Darstellung der Zahl 154, so fällt auf, dass durch die Multiplikation mit Zwei jedes Bit um eine Stelle nach links verschoben wurde.
+
Vergleichen wir nun die Darstellung der Zahl 77 mit der Darstellung der Zahl 154, so fällt auf, dass durch die Multiplikation mit Zwei, jedes Bit um eine Stelle nach links verschoben wurde.
 +
 
 +
=Bresenham-Algortihmus für Geraden=
 +
==Algorithmus für Gerade mit der Steigung m <= 1 ==
 +
Betrachten wir die folgende Problemstellung: Wir wollen eine Gerade, welche in Hesseform gegeben ist, mit einem Plotter (z.B. auf einem Monitor) zeichnen lassen. Wir wollen für den ersten Teil nur Geraden mit einer Steigung <math> m <= 1 </math> betrachten.<br><br>
 +
Sei die Gerade <math> g : \vec{n_n} \cdot ( \vec{r} - \vec{a} ) = 0 </math> gegeben. Hierbei ist <math> n_n = \begin{pmatrix} n_x \\ n_y \end{pmatrix} </math> der normierte Normalenvektor, <math> \vec{a}</math> ein gegebener Ortsvektor eines Punktes der Geraden.<br>
 +
Wir geben den Startpunkt der Geraden auf unserem Plotter die Koordinaten (0,0), d.h. jede Gerade, die wir zeichnen erhält damit ein eigenes Koordinatensystem.
 +
Der erste Punkt den wir zeichnen ist natürlich der Punkt <math>O (0,0)</math>, denn dies haben wir so festgelegt. Nun müssen wir für den nächsten Punkt entscheiden, ob wir nur ein Pixel (allgemein: einen Plotterschritt) nach rechts zum Punkt <math> T </math> gehen oder ein Pixel nach rechts und nach oben zum Punkt <math> S </math>. Um dies zu entscheiden müssen wir die Abstände, die die jeweiligen Punkte zu der idealen Geraden haben, vergleichen. Der Punkt mit dem kleineren Abstand wird dann angesteuert.<br>
 +
Hierfür betrachten wir die Differenz der Abstände <math> |d_t|-|d_s|</math>.<br>
 +
Da wir nur die y-Achsenabweichung der gezeichneten Geraden mit dem Auge wahrnehmen, aber der folgende Zusammenhang besteht, können wir mit den reinen Abständen, die wir aus der Hesseform gewinnen rechnen:
 +
 
 +
zu zeigen ist: <math> d_s >= d_t  \Leftrightarrow s >= t</math><br>
 +
 
 +
es gilt:<br><br>
 +
<math> d_s >= d_t \ \  d_s = s \cdot sin (\alpha) \ \  d_t = t \cdot sin (\alpha) </math><br><br>
 +
<math> \Leftrightarrow d_s = s \cdot sin (\alpha) >= t \cdot sin (\alpha) = d_t </math><br><br>
 +
<math> \Leftrightarrow  s  >= t </math><br><br>
 +
 
 +
 
 +
 
 +
 
 +
<ggb_applet width="1260" height="880"  version="4.2" ggbBase64="UEsDBBQACAgIALCFaEIAAAAAAAAAAAAAAAAWAAAAZ2VvZ2VicmFfamF2YXNjcmlwdC5qc0srzUsuyczPU0hPT/LP88zLLNHQVKiu5QIAUEsHCEXM3l0aAAAAGAAAAFBLAwQUAAgICACwhWhCAAAAAAAAAAAAAAAADAAAAGdlb2dlYnJhLnhtbOVb627bRhb+nT7FQCj2V0TP/dKVW7hZBE3jtEWdXRSLBQJKHEmsJVIlKV+CvMC+x75A9hX2f/eV9swMKYm6OJblJF4XtjQiOdfvzPnO+Uip983VdIIubFGmeXbcIRHuIJsN8iTNRsedeTXs6s43X3/RG9l8ZPtFjIZ5MY2r4w6PaGfZDo4iwlzjNIFeBn07pIR0ZdwXXR6TuNsfYtwVzKohvLjipIPQVZl+leU/xFNbzuKBPRuM7TQ+zQdx5fscV9Xsq6Ojy8vLqBk9yovR0WjUj67KpINg5ll53Kk/fAXdtRpdMl+dYkyOfnl1GrrvpllZxdnAdpBb1Tz9+osnvcs0S/JLdJkm1RhmT5XpoLFNR2NYp9GwqCNXawaLndlBlV7YEtquHPpFV9NZx1eLM3f9SfiEJov1dFCSXqSJLY47OKJMSS2kIYZLzRjXHZQXqc2qujKpBz1quutdpPYy9Os++SF5B1V5PunHrkskDHr3DlFMMXrqChIKCoWU4RIO5zALBQ0FD4UIdXhozkNVHurwUIczsHlapv2JPe4M40kJMKbZsAATLo7L6npi/ZTqE0sEyFNYVpm+hcoMA6wBdziP8VP3kvDiuMZ7ZZ16ZZ3ELeIdIm72vmDIzZv4+buC14cyHCpfEBwKUl/U7s3jJQ9cEbvTijg2ap+Bq2K+E0kjluNSLZ6C4z1VMK4Qm+OSlUFDn3uM2YxIqFxZKuP4KTW7l0oPWecKunw5pCDCD0nF9iHJgUZdLJSvQAtj+X//2hiSHbTM5YgC33ZEyW8YMQxwvwMq3KKbhmtCSeryJhjubVK9o4YMe/WEUDl2destXdlp6abIjCdFRJAA0pAKOEwgYqBQjjwoIgJxAYdEI+lKhZjjC44Y0sjVIwx56hMa3rjnEokE9OVOqkAqiHEkGCKeMDkCFJAnXcCEMqghBBLQyI1O3LBMIi7hgGnEYYKObpWjNAbt4BgGp4gRxFxbohCVSFKkHGUT7phcajd36JQiiZF0TYGzga8DV0MLjZhbDXjBLC/TBbhjO5ktrOJxTLPZvKqxq88PpkmDY5WvVU/ywfm3a2DbuKyaz1AJAtYyLoYA1gqbT3qTuG8nkF2cuX2A0EU8cW7u+x/mWYUWJBPOjYp4Nk4H5ZmtKmhVol/ji/g0ruzVc6hdNhP0Q/tw3rPzwSRN0jj7G2wS14XrEC2juyOvJrprUQ8zyPMiObsuYeugq7/bIj/udCERUBEXVEuiFZOSAGVfh2sEQnfENROMaU2IpnCpHMRu1zONIwiUXEEd11ACh11vvWawCYPbi8Xq4iu7WBMaFc7vVg5elN/mk+WpWZ5m1bN4Vs0Ln67BSIVb10k2mliPr6dfSHwG5/386iwAy0Jfr69ncITDDPqjZ/kkLxB4JRVAeqO67IfS13FTW9TCvg72NXBjqTRZXCeG+hq+7IfS1wLTh6nVSyXNMgluhklLzzfQeWtn+o3j0qh5llanzUGVDs7rpZLQ4If5tA97rt6U7T7JffXZO1rbZr1zW2R2EvZSBsac5/My7O7FDn3Sm5f2p7gan2TJz3YEfvlT7Kixgq5D1eWUEztIp9AwnK/Bi51h/wpTDWcTOypss8SJz5ADtP4qXt3ZG6d9V8+LfPoiu3gNu2Ztqr2jZj29clCkM7c7UR+4+twu91+SljEwfbLaDhZfwioGjnUAyMqB2EHxvBrnhc+BwXUhlqDv//OvLLMFsCVsSOe1V7PClk5NNEZ5ba8q2Dxw4bjzp9/mefXnMxRKP5Cd2Cnky6jy+xj4oOq0W3rXB9uhvP8r8M8i3oQ6K0aB6xu7v9nZKJ7MxrHL2GvcJvE1zHoVSd/hqzxp4+u5rLRFOlzGf/C/VzCEk0kLkgvxcNEMxElR/eT8GvSR01WGcymEoxFqGKYwu2t3GhONmSbaEE4VbNK3QbuFnRmQ2Qkqa4H6eg9Q2d1AxS1C+eygiggzBZILaNgxsdNe1w4+o4GaqXZqR4OOEDtRbYHkSXiBwLNDEMILwr0zQnEGrOF9D0LZLPDXzNpAfWHC8GEG3fmIsTIdzxNljU+zy1YhAEHrluqiSCtqh7NrBHNbvP7yCPAiNV70E+D1/BHgJT4hXi828WqH/mXEfbB46chIbKTWmgIvaSo9eiJikEISSbhhRippPjqW3z8CLGXEjJYSC0aMNpgyjyWLAEYOnE8oZe5f3guYg3w6jbMEZV7+nkLm21mqrhg79kMxccAG0OZVcyEOXdUdbNjFJdEL1OPDKeGAkLyEtku2oBg26jrkgG3XRCCbDMVSEMWFJnxdH1Qg+84zSF+8iKlqueI/fJcmifWiNuin37LQpA776XQ2SQdptbc9ngV7PN+wR38Pe/Q/5CafyiC05llc82yXLDv7ZCi/yJy6ARTWoI4D1P0NqM8GYxA4cJidVzej3manVrs7eYTU3gKu6IficBsIFm3jGx4JDOmm4BR2vr+D6+gGR8ooRgmWzCiNubxH9jmzI3d+zQot0LxBnm0YJHlT3myHsu66gdc1uAfxJci9sBKOnFIShMAblpxR3nIKJ6UMDCzhDaCXVNzgIeJmDwHQJi72LPY8xKrNewDn1s7czZcfs9dFnJXugVpb/B9uxE0CS958wJk2jXhHLyI43Pmh7o79fVEZiYiB4KK1T3cEpDttZhPgZVhxzuBNKs3Uw7Lidh0uWjocvOb2Qlw8lrsb4JHAgIZTQohskjEBJyEzMGBLoEgt97u9IddgrW4Pq3w09zcwY4ISASUUtdpShBIGp7BQHFIvvgvWNuf8WFTjfJRn8WRLwvQ88E28wTeDPRKmwUNJmLpbUtXrHYntW/dMMqIUorW7lcSxEfqh5FaDXVZ5uU9C9fLhZFHA/BFjIHMl04YaUTOFgbNgLa7APIoC9wezkEgJ0BYczkhFwJr3mEbd6A3PduGe7OENyf+rN7CIQ1KLIQZrrTjmn1zQ7XKHZJdZTvdxh9MH5A5SRAp0sxQG/rUQ4akAMFEklJaUGyMVaAv58f1he0Z6uktL2P2SUPuZ05yWjFAMsNXgDAqyEslDVO26GIClwEQQLLCgWvBaVwgFeQ14B8NgEHaAN3x0WeGfF2/X53bDhP/958029A8WFxaC2q49TGReQ0sAGKyMBGSU4drIOmze2w0scksbkztYpHkOWwxWHKe5PTmZ5Jc/2+HEXnlADxN1L3cpueF+LjT8zClt6zGJAbsLygTGWkhSSzhGNQNVLsGrQLeREMS7MiKQ/RtCYK8IyGdvVHQP0YGGu6LO7//ex4Gg9gccSP3h/Ge77lMt3beHmFaPQkwLcBgqtNCKSk2b+MQiCSdhp0CSrBkRdD8trVuY7qGk9aNQ0hyCvgBXwy7bhWSrUdLggBxyAQOZF2jpnV8U2OtOeH2btUUVJ/skqCd3ezz3MRJUChoB8lIDPCUoF8KEe66ERVphJ+EkSDasVJMqgbRzyRIR2DG+/uj5aR1cTzYAH+0XXEcPRqtBW6OJZhI8X0N8VUJuDa+1JoD6QmiuCUgCTiE/1Q85vG434kkw4umGEcf7GXH8kIzo9ByVoNM40VI1jyraEgOkX2NEsKjTI0YwYcgiFXggRtweUkgrpJzcPqSQRxJSpH/epBSDeEJJE6bBE8F7laLuK2gSs/3iNG+Benp7UPkjyX0o54YD7Un/DZkFqAbCNzZEYQzxZucN7+2Ymhamr26PqfmsX8i4r22qFfAJRHCi/YOEGlFKjYA/QhhsWKFul/lsk0f1LaK1Z5d0202j39/vJZjebwomqjGlMF8IjQprZT6TYrrLly+2KSZ+4B2HbfZ4ucsem3cgfn//huxnkTfkQzYxfzyb7AiPuEU7X6J/+CWhL/cIlPizElBansav7S/rP2hY5aX6l2CBlsiSlvCHn2xCJkQU01orgZUWDS1pLEFEuMcUDK99fe8WmLdzkoD4HngflJk8ZLzdzw80FQo0nOIYwkATV53IUJB3ghmo2Pnzg6PVH4P4H2jVv+P++n9QSwcI84pVEq0LAAB3PgAAUEsBAhQAFAAICAgAsIVoQkXM3l0aAAAAGAAAABYAAAAAAAAAAAAAAAAAAAAAAGdlb2dlYnJhX2phdmFzY3JpcHQuanNQSwECFAAUAAgICACwhWhC84pVEq0LAAB3PgAADAAAAAAAAAAAAAAAAABeAAAAZ2VvZ2VicmEueG1sUEsFBgAAAAACAAIAfgAAAEUMAAAAAA==" showResetIcon = "false" enableRightClick = "false" errorDialogsActive = "true" enableLabelDrags = "false" showMenuBar = "false" showToolBar = "false" showToolBarHelp = "false" showAlgebraInput = "false" useBrowserForJS = "true" allowRescaling = "true" />
 +
 
 +
 
 +
 
 +
 
 +
 
 +
 
 +
 
 +
 
 +
 
 +
 
 +
 
 +
 
 +
Nun gehen wir nicht mehr von dem ersten Punkt (Ursprung) <math> O= \begin{pmatrix} 0 \\ 0 \end{pmatrix} </math> aus, sondern von einem allgemeinen Punkt <math> P = \begin{pmatrix} p_x \\ p_y \end{pmatrix} </math>, dementsprechend lautet dann der Punkt
 +
<math> T = \begin{pmatrix} p_x + 1 \\ p_y \end{pmatrix} </math> und der Punkt <math> S = \begin{pmatrix} p_x + 1 \\ p_y + 1 \end{pmatrix} </math>
 +
 
 +
<ggb_applet width="1260" height="880"  version="4.2" ggbBase64="UEsDBBQACAgIAEOOa0IAAAAAAAAAAAAAAAAWAAAAZ2VvZ2VicmFfamF2YXNjcmlwdC5qc0srzUsuyczPU0hPT/LP88zLLNHQVKiu5QIAUEsHCEXM3l0aAAAAGAAAAFBLAwQUAAgICABDjmtCAAAAAAAAAAAAAAAADAAAAGdlb2dlYnJhLnhtbOVb23Lbxhm+dp5ihxeddCpCez64VDKJUzdOlNgTuZ1ObzwgsCQRgQADgDpk8jh9geYVep9n6r+7AEmIomJKsqyqI5KLXezp//7zAhp9fjHP0Zmt6qwsjgYkwgNki6RMs2J6NFg2k6EefP7ZJ6OpLad2XMVoUlbzuDka8IgO1uOgFhHmBmcpzJKM7YQSMpTxWAx5TOLheILxUDCrJvDlipMBQhd19rwov4/ntl7EiT1JZnYeH5dJ3Pg5Z02zeH54eH5+HnWrR2U1PZxOx9FFnQ4Q7LyojwbtxXOYrjfonPnuFGNy+I/vjsP0w6yom7hI7AA5qpbZZ588G51nRVqeo/MsbWawe6rMAM1sNp0BnUYDUYeu1wKIXdikyc5sDWM3qp7oZr4Y+G5x4e4/C1coX9EzQGl2lqW2OhrgiDIltZCGGC41Y1wPUFlltmjazqRd9LCbbnSW2fMwr7vyS3JsFDAhq7Nxbo8Gkzivga6smFSAKeyoWkK1bi5zO46rrr7eEDmAP+iQ/WzdXEBnAOJoQLU4AP4dKIwPhGgB2Fx4gJqyzP2sGAmDfvkFUUwxOnAFCQWFQspwC4c2zEJBQ8FDIUIfHobz0JWHPjz04ewGOtv6mtC2oUdpRyfbpJMAfe4r4esBuEKn3qCTOCJ+QcTt3hcMuX0Tv39X8LYqQ1X5guBQkPamdj8eL3lHititKCIbqwZ52L3olrx0KxIqN5ZkHB9Qs3tJug+hV9fcoJKvlxRE+CWp2EHlHcFdEcrFxqKgC+7jv1tLsjuRuV5R4PddUfK76P4tFlS4p/adzoeStOVNMNzbpkaHnTUctRtC9cz1bUW6sfPabZEZb5wQQQKUVyqwJQIRA4VySkwREYgLqBKNpCsVYk5vOWJII9ePMORNkNDww71OSyRgLteognIjxpFgiHjDxRGggLzxA0wogx5CIAGD3OrELcsk4hIqTCMOG3RmTznTwmAc1GFxihhBzI0lClGJJEXKmU7CnUWV2u0dJqVIYiTdULCdYDeDzYQRGjFHDWjBoqyzFbgzmy9WXPE4ZsVi2bTYte3JPO1wbMor3dMyOf3yCtg2rpvuGjqBx1o7xuDBen7z2SiPxzaH8OLEyQFCZ3Hu1NzPPymLBq2MTGibVvFiliX1iW0aGFWjH+Oz+Dhu7MVL6F13G/RLe38+ssskz9IsLv4OQuKmcBOitXt3xqtz71q0yyRlWaUnlzWIDrr4p63Ko8GQy4gQTgkzAjPJKBiDy3DLMBFJTZWmgjJBnPuuk9jJPFEywppr5yDAuStQ0ssdt+CeX9qerWiLL+yKIjStnNZtVF7VX5b5umlRZkXzIl40y8pHa2ArK0fVF8U0tx5db3wh7klOx+XFSYCVhbneXi6ghsMOxtMXZV5WCHSSCqBy2pbjUPo+bmurXtj3wb4H7viUpav7xFDfw5fjUPpewPiwtZZU0pFJcLdMVntrA5P35NKLjYuilkXWHHeVJktOW1JJGPD9cj4GiWtFsj8nua85R4dXhGx0aqvC5kGSCmDmslzWQbZX8vlstKztm7iZfVGkP9gpaOWb2BnGBqYOXddbTm2SzWFgaG/Bix1j/wZbDa2pnVa2IzH3AXKA1t/Fm3K91eynelmV81fF2VuQmitbHR129IzqpMoWTjrRGCz1qV3LX5rVMdj5dHMcEF8DFYmzOQBk40AcoHjZzMrKh8CguOBJ0Df/+VdR2ApsJQik09mLRWVrl0x0THlrLxqAH24cDf7w07Js/vwGfbp4d3GAFu8u/xha/JI2t3MInFHjJRrsQjPoz+FNAHARleMfwQ6t/E7os8EeuL9DwlGcL2axC9xb/PL4Ena/iaif7rsy7ePsLVptq2yycn+ght8BS12ytLJ0wSmuRkGKUjVvnHpDluT6GszhA6GONFhTDFH/pUvWlCBYEmG0VlpwMPc/hxQuSGjAZSe4tAfuiQcX/QkRD7C72ANk+mhA7kKt/VHmkREc8GSSGgBWUw8yZLZYSmMIU4IJbMR+ILMeyG/7IO8BMHsaABtlKAWQFRdSed/oxZgbziSkfJpxrrHeCXEPI+/+VgB8cXeAvMu7LURxAfbaWz0IIRbBcyysDU4nbBguFjCd99Ub2/EWunYA+dMXL3N4E4JnI0+q89+9aCm0XjHt74vXl08AL/aAeL14AniJB8TrqyeAV6eP9AHw+ssTwIs9IF4vnwBe4r7xujYE4b0Q5DX6FB/gPSIP/gQiDxwZpbmkSiqmMIVoros8NCecC2UEhM/ukHn/wOOvT0AQ1QMq7tdPCK+HcKSvtvHqn16sDw0eLV46MhIbqbWmGkMCKz16ImKSGCIJN8xIJc0Hx/KbJ4CljJjRUmLBiNEGU+axZBHAyDHmhFLmPvJewEzK+TwuUlT48/vjrLCD9bFxjF2Yh2LigA2gLZvuRhymaifY4os7B1yhHn9UF7OGdkiuQTEI6lXIAduhiYimhmIpCOSzmvCrR5zNLEtOC/DI/hy2aU9c/cXXWZpafyrvx9ifijCkdWPZfJFnSdbszY8XgR8vt/gx3oMf499Tk4diCG3tLG7t7JCsJ3swlF8V7oAWULgCdRygHm9BfZLMiqyBanHa3Ix63zr1xt2OA1J7FrhiHIq7M0Gw6DqDwyOBjeaCUxB91p2L4UgZxag7RoOQC3N5j+bnxE5d+xU29FDzHHmxxZH0XX0zI+p26g5eN+BWNql7fBKUQJB7MUs40phpQQj8YAhTKe9pBUQhxMDCEn4AeknFDSoiblYRAC13zmcl9OCstp9jnFq7cA+QXhdvq7io3TtB/QcYd2fitgVL3/2ONm0z8Ro1eh8mEhyeXlH3zsF92TISEQPeRWsf7wiId/qmTYCWYcU5gx+pNFOPi4vX55ail1uC1rx/XinuQ8E+embJI4UJJaCcQmDCpGqjMeAvxA/umQFEtn7P+zw1kFdgbd4fVnmXWKp76PvRYRURNtg90sJKcSa0adNTycDjGEE0V0wrpXbB2rc5r6tmVk7LIs6viZheBnsTb9mbZI+IKXksEdPwmlj1ckdk+7N7qyqiFLw14xruGqEfS3CV7OLKt/tEVN/eLt/7EFEUWP6IMbAGIMKGGiEDYwy0Are4AvYoynCQaOYf7WrKoUUqAty8xzDqRm14sQv3dA9tSP9XtYFFHIJaDD5Ya8Uxf/CMbpc6pLvYcryPOhw/InWQIlKQOEth4KOFczzuRBaD61RaUm7Ab0JuIT+8PlwfkR7vyiXsfkGo/chhTi+NUAyw1aAMSnIheTgFHzofgCWEL4JggQUFv9vmFUIRA+mGZBgYwu6gDR88rfDvvF2foNstFv7275t56F+OWnEIervxsJFlCy0BYLAyEpBRhmsjW7d5bydY5D15TG7Bke5dsirZUJzufDLPy/Mf7CS3Fx7QuyV13+7K5Cb7qdDkI4e0vQfCBvju3vnEEJ5K0qZwjGoGWbkErYKQnwQnPpQR4ZIbQkBWBAbfflNG9xgVaLLL6/z2614K9OvvKZD6v9Of6/M+1cv79kim1ZNIpoU7UMeQSHMiQckM7x5tcPeQiBNBlaSE7sz6rgdV90DdI5XWTyKV5pHU4PAhmCVKQQTF21SaG2gwmglBqSQ73x093Hyj179j3/4v3mf/BVBLBwicO7LbngoAADs4AABQSwECFAAUAAgICABDjmtCRczeXRoAAAAYAAAAFgAAAAAAAAAAAAAAAAAAAAAAZ2VvZ2VicmFfamF2YXNjcmlwdC5qc1BLAQIUABQACAgIAEOOa0KcO7LbngoAADs4AAAMAAAAAAAAAAAAAAAAAF4AAABnZW9nZWJyYS54bWxQSwUGAAAAAAIAAgB+AAAANgsAAAAA" showResetIcon = "false" enableRightClick = "false" errorDialogsActive = "true" enableLabelDrags = "false" showMenuBar = "false" showToolBar = "false" showToolBarHelp = "false" showAlgebraInput = "false" useBrowserForJS = "true" allowRescaling = "true" />
 +
 
 +
 
 +
 
 +
 
 +
 
 +
 
 +
'''Achtung:'''<br>
 +
Wie wir unter dem Abschnitt Hesseform gesehen haben, kommt es bei dem Vorzeichen der Abständen der Punkte auf die Lage der Punkte im Bezug zur Geraden und dem Ursprung an. Da der Punkt <math> S </math> nicht zwischen Gerade und Ursprung liegt, ist der Abstand <math> d_s </math> positiv, analog ist der Abstand <math> d_t </math> negativ.<br><br>
 +
 
 +
Also folgt mit:<br>
 +
 
 +
<math>|t| - |s| = -t - s = - (t+s) </math><br><br>
 +
<math>= -(\vec{n_n} \cdot (\vec {t} - \vec {a}) - \vec n_n \cdot ( \vec{s} - \vec {a})) </math><br><br>
 +
<math>= - ( \vec{n} \cdot ( \vec{t} + \vec{s})) </math><br><br>
 +
<math>= \begin{pmatrix} n_x \\ n_y \end{pmatrix}  \cdot \begin{pmatrix} p_x + 1 + p_x + 1 \\ p_y + p_y + 1 \end{pmatrix} </math><br><br>
 +
<math>= \begin{pmatrix} n_x \\ n_y \end{pmatrix}  \cdot \begin{pmatrix} 2 \cdot p_x + 2 \\ 2 \cdot p_y + 1 \end{pmatrix} </math><br><br>
 +
<math>= - ( n_x \cdot 2 \cdot p_x \ + 2 \cdot n_x + n_y \cdot 2 \cdot p_y + n_y ) =: d </math><br><br>
 +
 
 +
Nun entscheidet das Vorzeichen von <math> d </math> welcher Punkt angesteuert wird:<br><br>
 +
Für <math> d >= 0  </math> der Punkt <math> S </math><br><br>
 +
Für <math> d < 0  </math> der Punkt <math> T </math><br><br>
 +
 
 +
==Algorithmus für Gerade mit der Steigung m > 1 ==
 +
Wir wollen nun den Fall für Geraden betrachten deren Steigung größer ist als Eins. Die Vorausetzungen seien wie in dem Fall für die Steigung kleiner Eins. Im Fall der Steigung kleiner gleich Eins musste die Stiftposition bei jedem Zeichenschritt in x-Achsenrichtung inkrementiert werden und es wurde anhand einer Gleichung entschieden  ob wir auch in y-Richtung inkrementieren müssen. Im Falle der Steigung größer Eins ist es nun genau umgekehrt, wir müssen bei jedem Zeichenschritt in y-Richtung inkrementieren und an Hand der Abstandsgleichung entscheiden ob wir dies auch in x-Richtung tun müssen.<br><br>
  
−
=Bresenham-Algortihmus für Graden=
+
<ggb_applet width="1269" height="888"  version="4.2" ggbBase64="UEsDBBQACAgIABOOa0IAAAAAAAAAAAAAAAAWAAAAZ2VvZ2VicmFfamF2YXNjcmlwdC5qc0srzUsuyczPU0hPT/LP88zLLNHQVKiu5QIAUEsHCEXM3l0aAAAAGAAAAFBLAwQUAAgICAATjmtCAAAAAAAAAAAAAAAADAAAAGdlb2dlYnJhLnhtbN1b23LbuBm+zj4FRhed7dSmcT6kcnaStOkmtePMOu10epOhJEjimiK1JOVDJo/TF+i+Qu/7TP0BkDpaXtN2HFeTyBBAnP7vPwNU94fLSYrObVEmeXbYIRHuIJv180GSjQ47s2q4rzs/vPiuO7L5yPaKGA3zYhJXhx0e0c5iHNQiwtzgZACz9Ht2SAnZl3FP7POYxPu9Icb7glk1hA9XnHQQuiyT51n+Pp7Ychr37Wl/bCfxUd6PKz/nuKqmzw8OLi4uomb1KC9GB6NRL7osBx0EO8/Kw0795TlMtzLogvnuFGNy8I/jozD9fpKVVZz1bQc5qmbJi++edS+SbJBfoItkUI1h91TrDhrbZDQGOo2rHLheUyB2avtVcm5LGLtU9URXk2nHd4sz9/xZ+IbSOT0dNEjOk4EtDjs4okxiyjXnimJupOmgvEhsVtV9Sb3mQTNb9zyxF2Fa982vyLFRwIOkTHqpPewM47QEspJsWACksKFiBtWyukptLy6a+mI/ZA/+QYfks3VzAe8CDocdavAeJWJPYbwnBA57WV64g6o8T/2sGAmDvnxBFFOM9lxBQkGhkDI8wqENs1DQUPBQiNCHh+E8dOWhDw99OLuBzrq+ILRuWKG0oZMt00mAPveR8PEArNGpl+gkjogviLjd+4Iht2/i9+8KXldlqCpfEBwKUj/U7o/HS96TInYnisjSqkEeti+6IS/NioQ6eW2WZByExWxfkrYhdH3NJSr5YkkBsullVGyh8p7gzgnlYmlR0AX33382lmT3InOxosC3XVHy++j+HRZUeEXtG50PJanLm2B4sE11Dxpr2K03hMqx61uLdGUnpdsiM944IYIEKK9UYEsEIgYK5ZSYIiIQF1AlGklXKsSc3nLEkEauH2HImyCh4Q/3Oi2RgLlcowrKjRhHgiHiDRdHgALyxg8woQx6CIEEDHKrE7csk4hLqDCNOGzQmT3lTAuDcVCHxSliBDE3lihEJZIUKWc6CXcWVWq3d5iUIomRdEPBdoLdDDYTRmjEHDWgBdO8TObgjm06nXPF45hk01lVY1e39yeDBscqX+s+yPtnr9bAtnFZNd+hE3ishV8MHmzFbT7rpnHPphBdnDo5QOg8Tp2a+/mHeVahuZEJbaMino6TfnlqqwpGlejn+Dw+iit7+QZ6l80G/dLenXftrJ8mgyTO/g5C4qZwE6KFd3fGq/HuWuKwTD/Pi8HpVQmigy7/aYscDBcWkQT3zBiW3GDJwNlehUea0UhIxYwghFMJQl/249RLroqUohwLYhQR0oABu7r+mdI8LG3P57TFl3ZOERoVTuuWKm/LV3m6aJrmSVa9jqfVrPDBGixVOKpeZqPUenS98YWwp3/Wyy9PA6wszPXxagq1mvje6HWe5gUCnaQCTN6oLnuh9H3c1ua9sO+DfQ/c8CkZzJ8TQ30PX/ZC6XsB48PWalJJQybBzTJJ6a0NTL4il15sXBA1y5LqqKlUSf+sJpWEAe9nkx5IXC2Sq3OSh5qze7AmZN0zW2Q2DZKUATNn+awMsj2Xz2fdWWk/xNX4ZTb4yY5AKz/EzjBWMHXoutjywPaTCQwM7TV4sWPs32CroXVgR4VtSEx9fByg9U9X5Hqj2U/1psgnb7PzjyA1a1vtHjT0dMt+kUyddKIeWOozu5C/QVLGYOcHy+OA+BKo6DubA0BWDsQOimfVOC98BAyKC54EvfvPv7LMFmArQSCdzl5OC1u6XKJhykd7WQH88OCw87tfZnn1xw/o++mnyz00/XT1+9Dil7SpnUDgjCov0WAXqs7qHN4EABdR3vsZ7NDc74Q+S+yB51skHMXpdBy7uL3GL42vYPfLiPrpjvPBKs7eopW2SIZz9wdqeAwsdbnS3NIFpzgfBRlKUX1w6g1Jkk/KIPyRoESMCqmJ0+ErP4UShoAloZoq4gKkzyGDCxIacNkKLl0B93QBLvoDIi0Apk8G4CbMao8wLAtWXkHWwbBQhGlhPMQcIKZKSwGBjjTUkHYQsxWIP3qIHbp3gZntAMwsgpwXPCbE7xjyJigalLkBERaCKUOEpltRXoHI+785/S/vj4/3eXdFKM7AYHuzBzHENLiOqbXB64QNw5cpTOed9dJ2vIkua0VvAFmG4FnXk+oc+Eq4FFrXbPtt8Xq1A3jRyDABAsUM45pgqRv0CFMQekmtBIcg7atj+XoHsBSPKHt/2gG8cI0XjsTD4HWtB+ErHuQEfY/3cAunwXfAacCy1DAKeRsTTBBOmMu3PPJUgishWmvJMeHKtPPOYgXbwafy9riKu+HaJFdPBFkSEchxNeaaKeqiy8Z+Uk1c2EMZZ5JQ3Q5WuQZrdXtY5X3EtclYvzmsNIIoXRFuBCWSKGykh5VFUguOOYfgUjLGt8eSN1jOP++A5WyiHPkInubNDuDFHhGvv+wAXuIR8fpxB/Bq5Is+Al5vN/FaPYtbHIE9ZbykEUIY5zIxZiZksSqCJATcKMZaQ3JrHibt6OeTSZwNUOZvUI6SzHoEw8F9jF0sjWLigA2gzarmQRymqifY4Is7iZ2jHn/TOHEB7b6M9DqIV9cjDtjuk0gwrpQy4FGJwMSoepn5KXM1TvpnGQQp/ii8qg+9/Zcfk8HA+osRP8b+koUhtW9PJtM06SdVa4a8DAx5tcGQXguG9H5LTx6NI3gtm9ZSBnknm8m344mKXOioJESWBJjG2GOz5G3mDtQBsjW+9AJf4g2+vLuZL6sG7N0dGePgGYWiF4r784biSAkMoTszhggqVIjfBY0MJlhAZE8pBPL1uTCLKORKQlBgInxj8gHt0qkdufbrNeHdBuL9mxEv69kaSPvfONta1QbMwS4Jo5jShmJWawOOhMISNIUTqhiGwD+oAyQDSoPBYlIpwgjnN6gDv1kdAMDUuaW5gIMb27xjOrN26i73TrKPRZyV7nWt1cultlx8t82eDdpxcfCNk7s1LhpIzBxLlNBE09rRkIhJroySglKswYLVRk1EnBuuMSTKXEim9ZPi4k326q87EKCSBw5QV6X+pKjG+SjP4nS7M990GraFM7dPxplvCV2vC7s+u3euIi4pZ8QIzhl8kY/ty2/kzattvBm24M3w/5U3MuLG2S6IvKim2tzkWB41zrLb2HLUJs46ekJxloaAygjJqaJUcFkfP0PYFYFScOAWE1QZrDxjhIRWTJ1rYUppzB7QVG2DfLgN8uM2kB8/IcgJhtwOXLDCENdiLliNueCRFO7+GNI+Q+ub4q8J+fUxUW16jjcAH7eLicZPKSaCVEIpd9XCtcCmjoggxyaMagiKtObuskAGzGWEIXQiYKikhNgW3yPN+0Zxbe3ajzZ4OGrHw9GTyU4wZHiUGgnuAPI+SPSIrHMTSPmAS5CzQJqotHubPuQmLm33P0GAIVKSe/iQrxHWXnu9pFaul1rc2aldubMjwri3ZyD1N+B56gMySFaAu9IQTBlpeWOnVyBtcV+nd+S+jlEK+iHcK76EgDLU16DQrImC+JdwoTXbBuqqsfHzrpmaTcf8vo1jfn+3Q3NCg+T68inkcdRFuJIZDNYJEOU8OHUBIq2YIVxiLcAePcz7FHfhykkbrpzsCFecgzdYgtMHB6CYUM2ROyfUeQfhzrkM/wpM8S+qb4usUExrNVlh0X//fTOP/IvNcxZAbzceNjOrt0TcOZ0CKaRSGa6NrHPaOxoxgjf9ArklD5t+bbxt8yZ40V8CvxGGNM0vfrLD1F56ZG8bHl3Hhnlw5NlwssmGX1ux4dffYoPgd2TDdvf89Nlwk3X5sAPnduKBz+0Oln9d4H/vU/8s+MX/AFBLBwgE5F/XIgsAAMY8AABQSwECFAAUAAgICAATjmtCRczeXRoAAAAYAAAAFgAAAAAAAAAAAAAAAAAAAAAAZ2VvZ2VicmFfamF2YXNjcmlwdC5qc1BLAQIUABQACAgIABOOa0IE5F/XIgsAAMY8AAAMAAAAAAAAAAAAAAAAAF4AAABnZW9nZWJyYS54bWxQSwUGAAAAAAIAAgB+AAAAugsAAAAA" showResetIcon = "false" enableRightClick = "false" errorDialogsActive = "true" enableLabelDrags = "false" showMenuBar = "false" showToolBar = "false" showToolBarHelp = "false" showAlgebraInput = "false" useBrowserForJS = "true" allowRescaling = "true" />
  
−
=Bresenham-Algortihmus für Kreise=
+
<br><br>
  
−
Wir denken uns für jeden Kreis den wir zeichnen ein neues kartesisches Koordinatensystem, dessen Ursprung mit dem Mittelpunkt des Kreises zusammenfällt.<br>
+
Wir betrachten wieder die Differenz der Abstände:<br><br>
−
Im Gegensatz zu dem Zeichnen von Linien, bei denen wir nur zwischen einer Steigung kleinergleich eins und größer eins unterscheiden mussten, verhält es sich bei Kreisen anders, da sich die Steigung kontinuierlich ändert (vgl. Applikation "TangenteKreis". Hieraus resultiert auch eine sich ändernde Zeichenrichtung. Man beachte, bei jedem Durchgang durch 45 Grad, 135 Grad, 225 Grad und 315 Grad über- bzw. unterschreitet der Betrag der Steigung den Wert ein. Ferner wechselt bei jedem Durchgang durch die Koordinatenachsen das Vorzeichen der Steigung, dementsprechend müssen wir die einzelnen Achtel des Kreises seperat betrachten, wenn wir ihn mit Hilfe von Gleichungen beschreiben wollen.
+
<math> |s| - |t| = s + t </math><br><br>
 +
<math>=\vec{n_n} \cdot (\vec{s} - \vec{t}) ) </math><br><br>
 +
<math>= \begin{pmatrix} n_x \\ n_y \end{pmatrix}  \cdot  \begin{pmatrix} (p_x) + (p_x + 1) \\ (p_y + 1) + (p_y + 1) \end{pmatrix} </math><br><br>
 +
<math>= n_x \cdot 2 \cdot p_x + n_x + 2 \cdot n_y \cdot p_y + 2 \cdot n_y =: d</math><br><br>
 +
Auch hier entscheidet nun wieder die Differenz <math> d </math> welcher Punkt angesteuert werden soll.<br>
  
 +
Für <math> d >= 0 </math> wird der Punkt <math>T</math> angesteuert.<br>
 +
Für <math> d < 0 </math> wird der Punkt <math>S</math> angesteuert.<br>
  
−
==Tangente am Kreis==
+
== Zusammenfassung ==
−
<ggb_applet width="1251" height="880" version="4.2" ggbBase64="UEsDBBQACAgIABqEJkIAAAAAAAAAAAAAAAAWAAAAZ2VvZ2VicmFfamF2YXNjcmlwdC5qc0srzUsuyczPU0hPT/LP88zLLNHQVKiu5QIAUEsHCEXM3l0aAAAAGAAAAFBLAwQUAAgICAAahCZCAAAAAAAAAAAAAAAADAAAAGdlb2dlYnJhLnhtbN1Z63LbuBX+nX0KDDuT2Z21JYAAeEnk7DiebDdtkmZi9zL9B5GQhDVFcknIljN5nL7A/uoD7P99ph5cSFGS7a1ldzrtxDYI4gDn/p0DZvLdelmgK9m0qipPAjLCAZJlVuWqnJ8EKz07ToLvXn01mctqLqeNQLOqWQp9ErBRGGz2wWxEqNms8pMgnIpZFnNxPCVReMwYxcdTkYpjnPJZPJvRWDDYjNatelFWH8RStrXI5Hm2kEvxrsqEtmcutK5fjMfX19ejjvuoaubj+Xw6Wrd5gEDysj0J/MMLOG5r0zW15CHGZPy39+/c8ceqbLUoMxkgo9VKvfrq2eRalXl1ja5VrhdggzAGPRZSzRegZ5rAZGyoalC2lplWV7KFvYOpVVov68CSidKsP3NPqOj1CVCurlQum5MAj0jEKWeU4hgnUUQYDVDVKFlqT0w803F33ORKyWt3rnmyLBlOY3CCatW0kCfBTBQt6KXKWQM2BYmaFUxbfVPIqWi6+UYgcgT/gEB9luYs0NMZAhyY4qOQ8KMY4yPOvQGGjAOkq6qwp2LEU/TlCwpxiNGRGYgbQhiiyC1h9w5TN4RuYG7gjoa57cyRMkfDHI2xz516+vlGUf9iS9NOTzrUk4B+5jeCX2uAHT2TgZ7EKPEFESO9HSgychMrvxmYn0ZuGtuBYDcQv5iYP9Ze0SM1ogdpRAZcXTzczXQvXjqOJORkw5IyCJb0bpbhQxTd5dlrGZKBlhxi08Yov0PLRxq3V5QPmUIumB/7u8eSPkrNQzhG7DG5fwBDA4uDtO9y3o3Ej/eZ4cmEmow7NJx4gVC7MLQ+pLVctkZEmlpwQgRxSN4oBizhiKQwxCaJQ0Q4YhymJEGRGWNETd4yRFGCDB2hyEIQT+APszkdIQ5nmZexS25EGeIUEQtcDIEVkAU/sElIgYJzxGGT4U4MWxohFsGEJoiBgAb2YgMtFPbBHJiHiBJEzV4SozBCUYhiA52EGUSNEiM7HBqiCKPIbAXsBNx0mAk7EkSNNpAFddWq3rgLWdS9V6wdVVmvtLedf58t886Outohz6vs8vWOsaVodfcMRFCxNoXRVbCtuvlsUoipLKC9ODdxgNCVKEya2/NnValRDzLu3bwR9UJl7bnUGna16EdxJd4JLdffA3XbCWhZ23o+kausULkS5V8gSMwR5kC0Ke+cbMp7wj2brKqa/PymhdBB67/LpjLAxkeEJyyNKU95QmKw541bYoyMWBpxhsOYJEDCIXQzYYKesRGFdKBhzJKUJTiGpZs71jxvedUrJ9ay7aw5b0zWefubydv2dVVsXtWVKvWZqPWqsd0aYGVjtDot54W01rXgC31Pdjmt1ufOrNSddXFTwww7Aabzs6qoGgQ5GXKQd+7HqRstjZGsp8KWBlsK3PlJ5f06SUNLYcepGy0VON6J5jUlnZoEd2xUa9EGDh+GmY0a00StSqXfdROtskuvKXH0H1bLKQSc37Z9JHmiIyfjnRCbXMqmlIWLoxI8uapWrYvsPjqfTVat/Cj04rTMP8k55ORHYWBRw9GOdCNxLjO1hI3uvTedMG79M4jq3uZy3shOw8K2x86wdhUPo3rvtT3q+6Zavi2vLiBmdkSdjDt9Jm3WqNqEJpoCTl/KTfTlqhWA8vlwHyjfghaZQRwwpDZGDJBY6UXV2AYY0hYKF/rDL/8oS9kAUkI4mowt5BJ6X6RtUFrpevf8+rNtq0HCVafEyKvRFqadRktV2nBZijUcPgoTShIOnTWJIWujoEt8Zq4nQEEIdN9plKaUQgse4gTq6A1Ut1EcR7AppAmL4jSGznqm1rIHQ1BBfQbnbnvKxAeqpj8Cvu2E1YYGlm9NHJtioqgXwt4IfIKIG1Bp6Cx73p9ms1ZqKz614g4X31e5Nw3ZzTIN0HkJN4jWQoH2SW8fflB5LstNeDWZQQiPx32gQBxabwIw1tb0JGachimgaJoyeDDIV0vp0qtnUIMeFpQGQeW9vOdvi2O93V4He3btGrTDDIvvNezGdneoTPb1I7fp55OtNT46xiPGkwTKAw4pi8MEKoj1GuB/zBhOCOcxwQlO4PVnd+12d0xjioEbhm93svjftef7/wN7GqY26M34BPbKquVSlDkqbVt6ppoMAGfTDwlszIYEMdHoLLPS3cIfP715e+4O9MfsOQBgUGW9fd2Gx4IFfoQHVmtVKNHc7JaZW2GC3QETHlqgb5LlFWhQQdlCa+y/Gd3gzjvdmzWxeWDWiH/1mQxcB0HRqDU67ehPO6rTEDaSdATtF2B0jJOQpJQDHJ9Sz+OUdUefcv/kZPupdOq0rn6btlPNwBX3uv+jTZdt7/dO3nL92f1u3867s8PyDtpT1zmF/Olzz1SZg7IPsxhKKlzLoNcNGSFxh2ZpwjBnCUugEMTkadBs2z2fKg1dw45/zlx2HkNzgERosnXPV88F3H1ePshjfsvT1vUHuuzpzc4PKiIGG3qd//oD+Q2rDALnP4Fgv11Dbu05tmoy8UWE+CKykeI2GKTdweEdOLiDNXJdFypT+kFWDf/nrfowo7InMuo2QlzAhUHuQXiXzRYobsfzi9MPv3/z4eKNo7kfKrY812/8L1b1w4HituJ6eD9wkMvOi6rexfTeqLtuWt7vmXK1lM2g31ru3hdNg4Ch247TiCdxEnNOeEoPu78RTq37zDekHf/df4F73B2N7MHKum5gh0neLiblWoNQsHASPP9pVemX5xqatRVc3c0l2SeJPEJLdIIcAfoWJt/6yfPfEfzya7t6jLKqRV//+vM3CP3yT9Sq0k2+cZTuO9+2EzRwD7ZFOQjaus9Pj06PVotG29YOWZzCowRznjIWRRyigHF/6SchiZM0TaI0oTQaFtKhucfDLxv2S6P/H8lX/wJQSwcIrNzY63QIAABBHQAAUEsBAhQAFAAICAgAGoQmQkXM3l0aAAAAGAAAABYAAAAAAAAAAAAAAAAAAAAAAGdlb2dlYnJhX2phdmFzY3JpcHQuanNQSwECFAAUAAgICAAahCZCrNzY63QIAABBHQAADAAAAAAAAAAAAAAAAABeAAAAZ2VvZ2VicmEueG1sUEsFBgAAAAACAAIAfgAAAAwJAAAAAA==" showResetIcon = "false" enableRightClick = "false" errorDialogsActive = "true" enableLabelDrags = "false" showMenuBar = "false" showToolBar = "false" showToolBarHelp = "false" showAlgebraInput = "false" useBrowserForJS = "true" allowRescaling = "true" />
+
Durch die beiden Fallunterscheidungen in 2.1 und 2.2 kann nun im ersten Quadranten jede Linie mit positiver Steigung gezeichnet werden. Wollen wir nun auch die negativen Steigungen zulassen, spiegeln wir den Endpunkt der Strecke in den ersten Quadranten. Dies geschieht indem wir in die passende Gleichung die Absolutbeträge des Punktes und des Normalenvektors einsetzten. <br>
  
 +
Also für Steigungen mit <math> |m| <= 1 </math><br><br>
 +
<math>= - ( n_x \cdot 2 \cdot |p_x| \ + 2 \cdot n_x + n_y \cdot 2 \cdot |p_y| + n_y ) =: d </math><br><br>
  
−
==Symmetrie des Kreises==
+
Also für Steigungen mit <math> |m| > 1 </math><br><br>
 +
<math>= n_x \cdot 2 \cdot |p_x| + n_x + 2 \cdot n_y \cdot |p_y| + 2 \cdot n_y =: d</math><br><br>
  
−
Da bestimmte Kreisachtel (1tes und 5tes, 2tes und 6tes, 3tes und 7tes, 4tes und 8tes) punktsymmetrisch  zueinander sind, werden wir versuchen, indem wir mit Absolutbeträgen arbeiten, die auftretenden Gleichungen zu vereinfachen.
+
=Literaturnachweise=
  
  
  
−
<ggb_applet width="1261" height="880"  version="4.2" ggbBase64="UEsDBBQACAgIAFiAJ0IAAAAAAAAAAAAAAAAWAAAAZ2VvZ2VicmFfamF2YXNjcmlwdC5qc0srzUsuyczPU0hPT/LP88zLLNHQVKiu5QIAUEsHCEXM3l0aAAAAGAAAAFBLAwQUAAgICABYgCdCAAAAAAAAAAAAAAAADAAAAGdlb2dlYnJhLnhtbO1c23Lbxhm+dp5ihxeZtCNCez4kUjKyPJmmY6eZ2O2kvemA5IqEDQEMAEqUJ4/TB2hzvm7v80z9dxfgmRJJWTHNsWx5icWe/u/7TwssffLZ+DJFV7Yokzw7bZEIt5DNunkvyfqnrVF10datzz794KRv877tFDG6yIvLuDpt8Yi2pv3gKiLMdU56p60u61AjL3hbMt1p8w6FUS46tK1Uj/Z4V9kLBi3RuEw+zvIv40tbDuOufd4d2Mv4ad6NKz/moKqGHx8fX19fR83sUV70j/v9TjQuey0EK8/K01b94WMYbq7TNfPNKcbk+JtnT8Pw7SQrqzjr2hZyUo2STz94dHKdZL38Gl0nvWoAGFANqxvYpD8AOY27OHathiDs0Har5MqW0Hfm0gtdXQ5bvlmcufuPwieUTuRpoV5ylfRscdrCERGGKdFCeZHYrKpbkHqm42aMk6vEXofB3Cc/D8dGAfJJmXRSe9q6iNMShEmyiwKAhGUUI7gsq5vUduKiuZ6ughzBH2iQvLZuLBAuSH/aYhIfEa6OFMZHQtRSz07cQlWep35UjIRB332HKKYYHbmChIJCIWW4hUMdZqGgoeChEKEND915aMpDGx7acHaLnPX1VNC6Yk7SRk5qxFROAvK5Xwm/HoAFOfWMnMQJ8R0ibvW+YMitm/j1u4LXlzJcKl8QHApS39TuH4+XvKdErJGIzTJ3l0RkZtagD+snXdKXZkZCJdl8SrqNoItzTqQEHViekoo1Ut4T3ImgfEZZYC7/1/8uTcnuJeZ0RoE3nVHy+9j+DhMqPGf2jc2HktTlbTC8sUWdHDfe8KReECoHrm2t0pW9LN0SmfHOCREkwHilAl8iEDFQKGfEFBGBuIBLopF0pULM2S1HDGnk2hGGvAsSGv7h3qYlEjCWq1TBuBHjSDBEvOPiCFBA3vkBJpRBCyGQgE5uduKmZRJxCRdMIw4LdG5POdfCoB9cw+QUMYKY60sUohJJipRznYQ7jyq1WzsMSpHESLqu4DvBbwafCT00Yk4asIJhXiYTcAc2HU5Y8Tgm2XBU1djV9d3LXoNjlS807+XdV48XwLZxWTWfoRFErGk0DBFsLlg+Oknjjk0hp3ju9AChqzh1Zu7Hv8izCk2cTKjrF/FwkHTL57aqoFeJXsZX8dO4suPPoXXZLNBP7YP4iR1106SXxNnfQEncEG5ANI3pkkxjuhb1NN08L3rPb0pQHTT+hy1yWJRgkeRYUYmJMkZBNLip7zATcS2MJlRxwgxYYtmNU++MI0OZoswwbQjhBhzYzep7IkxsryaSxWM7kQf1C2dzMxdflI/zdFo1zJOsOo+H1ajwCRqsoXAynWX91HpsveuFVKf7qpOPnwdQWRjrxc0QrnBYQad/nqd5gcAiqQCH16/LTih9G7e0SSvs22DfAjcsJb3JfWKob+HLTih9K6A9LK0WlTRiEtxMk5Te18Dgc1rplcYlTqMsqZ42F1XSfVWLSkKHL0eXHdC3WiHnxyRvasyT4wUVO3lli8ymQY8yIHOUj8qg2RPtfHQyKu1XcTU4y3pf2z7Y5Fexc4sVDB2aTpfcs93kEjqG+hq82BH7V1hqqO3ZfmEbEVOfEwdo/V08q9VL1X6oz4v88ovs6gVozcJST44beU7KbpEMnXaiDvjpV3aqf72kjMHL92b7gfAlSNF1HgeArByILRSPqkFe+KwXzBbiCPrz//6VZbYATwkK6Sw2tZeQ+6LKq6XX7Ak9Zz6VdjygvPMS/MgkboT7MwDD/ZU66rU5ToeD2OXbNQZpfAMrmEXFD/gs7y1iBVR4gcA3DINSDK0N+hQWDB+GMJw3w5nlePBLNIYQFoH3AG98c9pqk4iaFnodNlhhN+HkdfY55wtD7QJ1oHkBqjtAe7wM2rzST3Vtb0GjEThY7UFTEWTQ9I2g1s0vL+OshzKfkZwnRTe1rWkojLHTOBQTh2HAZ1Q1N7phsHqIJQpA+5PuBOHu/fUW707A1NNWEDxfwR6y9OGgqh2///CnpNezPjUIkSjp2+wKVpqDR0JjXD8DuMFhfvS6qRkDOm1fdUPqqtdkhhqgvkjG6Kxpf9a0OqPQkVMIg4JCACTG/0A9q6c449CgsZYz4bqBtYTVfZsFgcrgnF1OkVwk3dsJfm77rn5ThuPbGS7r0RoO47fK8dRU2jpi2BmIczAsYspobyxcRFQaSShbCsCbqwXAkzoz/SJzocp6574c3F5ZO3RZxV+yF0Wcle7Z0HxUW8/R13kFcWGBoseBIi7++N9/w0fqSFtk6/GHMeS3n9zO2YJjrLu8Xfc4wxyNqCaQKDJCMGxlQ5CgEdHGCMEINYxwJdgD+L7VsNf4bAz+zhTsHxGMUmGmP3W85pGURs3U/85U7EbIPWnZM3JoxI2WnEutsIQtGw/UmEhwo2Zt5y0wszE/59uwcb432JuICc2m6q8n2JsHSclWIn6+Cb7b6/z5nuk54RFlmi1EA3BBSs6Gg9/NBZ1vrty7up3zvXQ4jghIovDkh9ZxGevZWCD478zEbnzck5U948ZEXGgxsYbgj2Rk5EwoEPoBiLl9LzEFeY6IznY7is6+7ChYBH5mIQW98TsNSJKWYq57i4kptFRUCsz5Pm83NqFxDZm97cjs7QmZfkc447aaR1HNrvG14xtHxnGIad2QHQSFa4i02xFp94TIZeO7WWGqwSbbgkUuXVaYMSalUORdJfR8ib6L7ei72Bv6nL1Nkwri+Vu0TqUCfzMPb+rW7yp/a4ywvx2L/T1hcdHcTIiMKwNjezEySvGOs7iGy8F2XA72hMv2ovG5FPVmpaW+Di9wZ2OkPggu1zCabMdosi+MLtih0LWTnTPasD04nAi5AZ8vt+Pz5Xs+3wKfK575Lu/t0+2YTPeFyTXbkJldyDu1CfEHbW57fXIWHs7cvqX87T+3s+mPaky4gtauP6xw1MAcKS2Y0UQyZhTnuoZsR74JXmScbMz4LubWnG0putOnM24NoTZN8+uv7UVqxx7sN8DMKvvyLC1vMn77fitmvn8wZvzR1xW2eIjMrLecdfbzw1Ys/fDg9lMfeXPPyw6Lp/N5e1nHx49b8fHjnXyQXa1m4SijZ+bAGFnlx263lp+2Yuen99HmXszcxc86ln7eiqWf72SJvvdpG/C0KgItc/PLVtz8chc35n1SsDIpWJUILJPx61Zk/PpghvLOB5vbXgY/OYgT2JpRYoQhiimshKmfIrgTRZhJqZkRXLKHONDyLCmKvFjQ7yfrNvdPtn9Z33R5uyxNsZYRoQJjjjWV1FAeXnO0ZUTlHNhv5hT8eFiAgTjtqAV9YccVTAk3TlsffjvKq0+eoI++Ofr7H8KFH2Aezgp6tOa7v81HJv5bUKUtkovpNwcBl2f+/Mn0O5it5iR03a2s4qL6yuGFHAs80poxTpWShHHDWH2CRRpDMKTVggrgY+7M3N240nlcg+J91P7mCLW3wZceBL6ME/elYMU0UZrX5yPA0QiJCaVUSikkIdsBzP45r7o0QmfdQWXTzcF1Q7z78LZxBBGZcCwhMjPBKa09NnFPC4nQkgvM508gbgLvvAazXeA9BO1t+2/XKM0wN1hJg6ffTsJSKNBnTgk4D6m2BZjNAcx3AZgdAsCApGYCUg6nxYbxxj0o92ibKMrde4r50+SbwMvn4BW7wMsPAF4eYc00JgAslZDRmeZUMnaAY6kIKDWRW7sHMQev3AVecQDw6sg5B+kSBWaoIrJJ4RQDVyHBNzDhnLLYFl85h6+KKlvuALE8AIgJBg8sJSMCKwaxTKuJB5YMC0M15BCK+p3kdhirOYz1jhirA8AY3IEGX8AV1aDD2jQHrjhsQDAWFEMWwajZOsbpOYTJLl5CHwC8kAKDi2WGMK3AF0gu6rPYVAvwHuCDAXm2PoU4nv2+uLtu/nOnT/8PUEsHCIXs6jJ1CwAAjEoAAFBLAQIUABQACAgIAFiAJ0JFzN5dGgAAABgAAAAWAAAAAAAAAAAAAAAAAAAAAABnZW9nZWJyYV9qYXZhc2NyaXB0LmpzUEsBAhQAFAAICAgAWIAnQoXs6jJ1CwAAjEoAAAwAAAAAAAAAAAAAAAAAXgAAAGdlb2dlYnJhLnhtbFBLBQYAAAAAAgACAH4AAAANDAAAAAA=" showResetIcon = "false" enableRightClick = "false" errorDialogsActive = "true" enableLabelDrags = "false" showMenuBar = "false" showToolBar = "false" showToolBarHelp = "false" showAlgebraInput = "false" useBrowserForJS = "true" allowRescaling = "true" />
 
  
−
== Aufstellen der Gleichungen ==
+
Olaf Müller, Ralf Kunze, Vorlesungskript SS 2002:  Computergrafik,  [http://www-lehre.inf.uos.de/~cg/2002/skript/node30.html http://www-lehre.inf.uos.de/~cg/2002/skript/node30.html] 11.03.2012 <br>
−
=== 1.tes Kreisachtel ===
+
  
−
Betrachten wir das erste Kreisachtel
+
J. Frank, Informatik, [http://www.wvs.be.schule.de/faecher/informatik/material/grafik/strecke3.html http://www.wvs.be.schule.de/faecher/informatik/material/grafik/strecke3.html] 11.03.2012 <br>
  
−
<ggb_applet width="1260" height="880"  version="4.2" ggbBase64="UEsDBBQACAgIADaBJ0IAAAAAAAAAAAAAAAAWAAAAZ2VvZ2VicmFfamF2YXNjcmlwdC5qc0srzUsuyczPU0hPT/LP88zLLNHQVKiu5QIAUEsHCEXM3l0aAAAAGAAAAFBLAwQUAAgICAA2gSdCAAAAAAAAAAAAAAAADAAAAGdlb2dlYnJhLnhtbN1a627bOBb+3XkKQj8Wu5jE4V1U1+4gbaeXRdMtNtnF7P4JaImxOZEljyQndtHH2TeZF5tDUvIljtPJBWkRtApF6vBcvnPhkZL+T/NJji5MVduyGESkhyNkirTMbDEaRLPmbF9FP734oT8y5cgMK43Oymqim0HEezRa7YNZjzC32WbAJR2aM0rIvtRDsc810fvDM4z3BTPxGVw85iRCaF7b50X5UU9MPdWpOU7HZqI/lKluPM9x00yfHxxcXl72Oum9shodjEbD3rzOIgSaF/Ugam+eA7uNTZfMk1OMycEvRx8C+31b1I0uUhMhZ9XMvvjhWf/SFll5iS5t1oxBexonERobOxqDnYkCow4c1RSMnZq0sRemhr1rU290M5lGnkwX7vmzcIfypT0RyuyFzUw1iHCPiJgIjqkUilGpCEgsK2uKpiUmrdCDjl3/wprLwNfdeZEcJzE4wdZ2mJtBdKbzGuyyxVkFmIJG1QymdbPIzVBX3XylENmDf0BgPxvHC+wMQAwimuA9SsRejPGeEC0A64Ij1JRl7rliJBL05QuimGK05wYSBgqDlOERDmuYhYGGgYdBBBoetvNAygMNDzSc3WBnO18Z2i5sWNrZydbtJGCfuyRcHoArdqo1O4kz4gsiTns/MOT0Jl5/N/B2KsM09gPBYSDtQ+V+eLzkPS1id7KIrEkN8bBb6Fa8dBIJlWsiGYdgSXaLpLcx9KrMpZUUk5VIAbHpY1TssPKe4C4N5WJNKOSC+++vLZHsXmauJAr8ZyVKfp/cv4PAGG+kfZfzYSTteBMMD6ZU/6Crhv1WIVSPHW0b0o2Z1E5FlvjihAgSkLwyhloiEElgiF0SU0QE4gKmRCHpxhgxl7ccMaSQoyMM+RIkFPzgPqclEsDLLcYhuRHjSDBEfOHiCFBAvvgBJpQBhRBIwCYnnTixTCIuYcIU4qCgK3uxKy0M9sEchFPECGJuL4kRlUhSFLvSSbirqFI53YEpRRIj6bZC7YS6GWom7FCIOWsgC6ZlbZfgjk0+XXrF42iL6axpsWvX00nW4diUV8izMj1/eQVso+umuwciOLFWB2M4wTbOzWf9XA9NDu3FsYsDhC507tLc8z8riwYti0xYG1V6OrZpfWyaBnbV6Fd9oT/oxszfAHXdKehF+/O8b2ZpbjOri/9AkDgWjiFaHe+ueHXHuxKtmLQsq+x4UUPooPn/TFW6KiJ7lMZCSMwlTQiGYrQIjySjvRhLLpkiROIYDoo61blXm/TgYlwlElOeJFBBFjueqSTINhdL4/TcLE1Co8ql3drkff2yzFdL09IWzSs9bWaVb9dAv8qZdViMcuPh9dUXGp/0fFjOjwOuLPA6WUxhhoMGw9GrMi8rBElJBWg8asdhGD2NU21JhT0N9hS4c5TNls9JQj2FH4dh9FTg+aBaayrpzCS4E2NrX26A+UZg+rhxbdSssM2HbtLY9Lw1lYQNH2eTIYRcG5ObPMlD8ewfXImy/rmpCpOHUCrAmbNyVofgXgbos/6sNp90Mz4ssn+ZEaTlJ+0qYwOsA+lK5cykdgIbw3oLnnaO/TeoGlYzM6pMZ2LuO+QArX+K1wN7a9mzelOVk/fFxQlEzRVV+wedPf06rezURScaQqk+N6v4y2ytodBn6/vA+BqsSF3RASAbB2KE9KwZl5XvgSFz4ShB//j9/0VhKiiWEJB+32SiiwwV/qR4XzhMoGhEqyql8SCaH4IngR0ZRAt/620pZ01HcBSUb7m5YpCbCbTVqPHh7jNm6fYjz935F5XDX0Ha8kgKz1fegMfL0JbKR7YbhmHQ+XSsXVffYpvrBVi2jrZneFRm17imRvOwFS0G0b6/+RxexMJbh9PYZe5GoQyrV5wKMRmM/YrZH7fN3kyH6+1eT3lfHO5qti4gsn18QLWdhhybGhPSMygMN1Ng56vaWvqsAGM9CW+RmCXQaOOYUBZ7/EiPM0YV4xKKq+RcyAdBczM4X9kqzc2VyDwKUflxKyLTmyMS8sWmS+TTr0TkGha7XIPv7phVbW7gxD2HF8/aHyBNe1T4m3c2y4zvJ8LZZUemuABNS6hhaI7bbwgL3Ab1525lTrrwXpB26TNZcw2ERGXn6LCjP+yoDilsJKLHRKyEjEmSwMWg+T1krYxD3rE+FGtmm9+KYE0darnrQuyZTbdyZT6twFQXkC3MJ2beQAjCg0H0l99mZfP3T+ivv5zaPfTfU/u3sOK5bPoSepJVlgUe39KdvpuqTWXPlq03RP4RuNRBteyyOnjaXXWjq+aTywgUKlMsBSWJoLFSgikmfKLxHiNKJFTElHLKcCzWE+3r6NINdI89uqc/npLbIky/G4S7d7zbQ0x7QsWCQ2BTpqRKYt5BTAFjwbGk0G+6vu02CLMNhE/ujDB7EghLSqF0CCkliyVV7WFBFGAuEoFVQujuCL7hLD28Pzrf/CwlbfPBH6H3ePkE8GKPiNerJ4CXeES8Xj8BvLp8pI+A189PAC/2iHi9eQJ4iQfGa/Pt6NiM3Pr1r0cvt16P9M2vR3XLrcNXf9NuZIXhPm9BZC2IK153eIkCPHLnsOVnD3Dw9sejc2Om7qvdP4uTShe1+03s5lej3U7xrdAVl6Rbvnh7m48nb+/08cS3WaN2fOhkwL27lQ8qMU0wYQlnhLbdN+2RmHOFmcKKJ5wz8di58nbLP8Pb5crwe8mV67BcXAv8VxOJfeNEut5jP+/y2OvTk9v5zG24S151X+0f0m34erfhXW7DVEmsJJNKxIoKxm7wo/jGftz1gTkNntRbnnwXHtymQr77bj4v0x4ThHHnHckluI21CUhgnSpChKDwIqwercS929UOvD49vm3CHH9HCaMkVzFRivMYx9z9VY9PGFiVgiWEMcGwkPGfKHSPnyAH67+68b9Nbf/q6sUfUEsHCMpvLI+ECAAAJSYAAFBLAQIUABQACAgIADaBJ0JFzN5dGgAAABgAAAAWAAAAAAAAAAAAAAAAAAAAAABnZW9nZWJyYV9qYXZhc2NyaXB0LmpzUEsBAhQAFAAICAgANoEnQspvLI+ECAAAJSYAAAwAAAAAAAAAAAAAAAAAXgAAAGdlb2dlYnJhLnhtbFBLBQYAAAAAAgACAH4AAAAcCQAAAAA=" showResetIcon = "false" enableRightClick = "false" errorDialogsActive = "true" enableLabelDrags = "false" showMenuBar = "false" showToolBar = "false" showToolBarHelp = "false" showAlgebraInput = "false" useBrowserForJS = "true" allowRescaling = "true" />
+
Markus Grodd, Der Bresenham-Algorithmus, [http://algorithm.name/rasteralgorithmus_1.html http://algorithm.name/rasteralgorithmus_1.html], 11.03.2012 <br>

Aktuelle Version vom 11. März 2013, 18:00 Uhr

Inhaltsverzeichnis

Allgemeines zum Bresenham Algorithmus

Motivation des Algorithmus

Der Bresenham Algorihtmus, ist ein Verfahren um Geraden möglichst "gut" auf Anzeigegeräten zu zeichnen. Hier heisst "gut", dass die Abweichung zwischen dem gezeichneten und dem gedachten Objekt möglichst gering ist.

Das Problem beim Darstellen einer Strecke auf einem Anzeigegerät ist, dass das erzeugte Bild nur durch endlich viele Punkte aufgebaut ist, dadurch entstehen "Lücken" beim Zeichnen. Da unsere Augen nur eine endliche Auflösung verarbeiten können, scheint uns ein Bild auf dem Monitor nicht durch einzelne Punkte aufgebaut zu sein, sondern es entstehen für uns geometrische Formen, die wir mit unserer Vorstellung von mathematischen Objekten in Einklang bringen können.



Eine Gerade wie wir sie auf dem Bildschirm wahrnehmen.
Gerade in normaler Größe



Hier sieht man dieselbe Gerade um das Achtfache vergrößert.


Gerade bis auf die Pixeleben vergrößert

Effektivität des Algorithmus

Dieser Algorithmus ist auch in heutiger Zeit in seiner Geschwindigkeit und Einfachheit ungeschlagen, da sich die Rechenoperationen h auf Addition und die Multiplikation mit Zwei beschränken. Dadurch kann dieser Rechenalgorithmus direkt in die Hardware der Grafikkarten implementiert werden. Potenzen: Obwohl in den Rechentermen Potenzen auftreten, kann man diese umgehen. Hierfür betrachten wir den Ausdruck:

n^2

die zweite Binomische Formel liefert:

(n - 1)^2 = n^2 - 2 \cdot n + 1 \ \Leftrightarrow n ^ 2 = ( n - 1)^2 + 2 \cdot n - 1

durch rekursives Anwenden dieser Formel lassen sich Potenzen solange vereinfachen bis die Basis Eins erreicht ist und damit die Potenz verschwindet.

Multiplikation mit Zwei:
Eine Multiplikation mit Zwei ist für einen Computer eine elementare Rechenoperation, da die sogenannte Shift Operation (Verrückungsoperation) durchgeführt wird.

Wir erinnern uns an die Darstellung von Zahlen im Binärsystem.


Wertigkeit der Stelle 2^7 = 128 2^6 = 64 2^5 = 32 2^4 = 16 2^3 = 8 2^2 = 4 2^1 = 2 2^0 = 1
Binärzahl 0 1 0 0 1 1 0 1

Hier wird die Zahl (im Dezimalsystem) dargestellt

0 \cdot 2^7 + 1 \cdot 2^6 + 0 \cdot 2^5 + 0 \cdot 2^4 + 1 \cdot 2^3 + 1 \cdot 2^2 + 0\cdot 2^1 + 1 \cdot 2^0 = 77

Multiplizerien wir nun mit Zwei, so folgt:

2 \cdot ( 0 \cdot 2^7 + 1 \cdot 2^6 + 0 \cdot 2^5 + 0 \cdot 2^4 + 1 \cdot 2^3 + 1 \cdot 2^2 + 0\cdot 2^1 + 1 \cdot 2^0 ) = 154

\Leftrightarrow

0 \cdot 2^8 + 1 \cdot 2^7 + 0 \cdot 2^6 + 0 \cdot 2^5 + 1 \cdot 2^4 + 1 \cdot 2^3 + 0\cdot 2^2 + 1 \cdot 2^1 = 154

Also die Zahl 154 (Dezimal) in Binärdarstellung:

Wertigkeit der Stelle 2^7 = 128 2^6 = 64 2^5 = 32 2^4 = 16 2^3 = 8 2^2 = 4 2^1 = 2 2^0 = 1
Binärzahl 1 0 0 1 1 0 1 0

Vergleichen wir nun die Darstellung der Zahl 77 mit der Darstellung der Zahl 154, so fällt auf, dass durch die Multiplikation mit Zwei, jedes Bit um eine Stelle nach links verschoben wurde.

Bresenham-Algortihmus für Geraden

Algorithmus für Gerade mit der Steigung m <= 1

Betrachten wir die folgende Problemstellung: Wir wollen eine Gerade, welche in Hesseform gegeben ist, mit einem Plotter (z.B. auf einem Monitor) zeichnen lassen. Wir wollen für den ersten Teil nur Geraden mit einer Steigung m <= 1 betrachten.

Sei die Gerade g : \vec{n_n} \cdot ( \vec{r} - \vec{a} ) = 0 gegeben. Hierbei ist n_n = \begin{pmatrix} n_x \\ n_y \end{pmatrix} der normierte Normalenvektor, \vec{a} ein gegebener Ortsvektor eines Punktes der Geraden.
Wir geben den Startpunkt der Geraden auf unserem Plotter die Koordinaten (0,0), d.h. jede Gerade, die wir zeichnen erhält damit ein eigenes Koordinatensystem. Der erste Punkt den wir zeichnen ist natürlich der Punkt O (0,0), denn dies haben wir so festgelegt. Nun müssen wir für den nächsten Punkt entscheiden, ob wir nur ein Pixel (allgemein: einen Plotterschritt) nach rechts zum Punkt T gehen oder ein Pixel nach rechts und nach oben zum Punkt S . Um dies zu entscheiden müssen wir die Abstände, die die jeweiligen Punkte zu der idealen Geraden haben, vergleichen. Der Punkt mit dem kleineren Abstand wird dann angesteuert.
Hierfür betrachten wir die Differenz der Abstände |d_t|-|d_s|.
Da wir nur die y-Achsenabweichung der gezeichneten Geraden mit dem Auge wahrnehmen, aber der folgende Zusammenhang besteht, können wir mit den reinen Abständen, die wir aus der Hesseform gewinnen rechnen:

zu zeigen ist: d_s >= d_t \Leftrightarrow s >= t

es gilt:

d_s >= d_t \ \ d_s = s \cdot sin (\alpha) \ \ d_t = t \cdot sin (\alpha)

\Leftrightarrow d_s = s \cdot sin (\alpha) >= t \cdot sin (\alpha) = d_t

\Leftrightarrow s >= t









Nun gehen wir nicht mehr von dem ersten Punkt (Ursprung) O= \begin{pmatrix} 0 \\ 0 \end{pmatrix} aus, sondern von einem allgemeinen Punkt P = \begin{pmatrix} p_x \\ p_y \end{pmatrix} , dementsprechend lautet dann der Punkt T = \begin{pmatrix} p_x + 1 \\ p_y \end{pmatrix} und der Punkt S = \begin{pmatrix} p_x + 1 \\ p_y + 1 \end{pmatrix}




Achtung:
Wie wir unter dem Abschnitt Hesseform gesehen haben, kommt es bei dem Vorzeichen der Abständen der Punkte auf die Lage der Punkte im Bezug zur Geraden und dem Ursprung an. Da der Punkt S nicht zwischen Gerade und Ursprung liegt, ist der Abstand d_s positiv, analog ist der Abstand d_t negativ.

Also folgt mit:

|t| - |s| = -t - s = - (t+s)

= -(\vec{n_n} \cdot (\vec {t} - \vec {a}) - \vec n_n \cdot ( \vec{s} - \vec {a}))

= - ( \vec{n} \cdot ( \vec{t} + \vec{s}))

= \begin{pmatrix} n_x \\ n_y \end{pmatrix} \cdot \begin{pmatrix} p_x + 1 + p_x + 1 \\ p_y + p_y + 1 \end{pmatrix}

= \begin{pmatrix} n_x \\ n_y \end{pmatrix} \cdot \begin{pmatrix} 2 \cdot p_x + 2 \\ 2 \cdot p_y + 1 \end{pmatrix}

= - ( n_x \cdot 2 \cdot p_x \ + 2 \cdot n_x + n_y \cdot 2 \cdot p_y + n_y ) =: d

Nun entscheidet das Vorzeichen von d welcher Punkt angesteuert wird:

Für d >= 0 der Punkt S

Für d < 0 der Punkt T

Algorithmus für Gerade mit der Steigung m > 1

Wir wollen nun den Fall für Geraden betrachten deren Steigung größer ist als Eins. Die Vorausetzungen seien wie in dem Fall für die Steigung kleiner Eins. Im Fall der Steigung kleiner gleich Eins musste die Stiftposition bei jedem Zeichenschritt in x-Achsenrichtung inkrementiert werden und es wurde anhand einer Gleichung entschieden ob wir auch in y-Richtung inkrementieren müssen. Im Falle der Steigung größer Eins ist es nun genau umgekehrt, wir müssen bei jedem Zeichenschritt in y-Richtung inkrementieren und an Hand der Abstandsgleichung entscheiden ob wir dies auch in x-Richtung tun müssen.



Wir betrachten wieder die Differenz der Abstände:

|s| - |t| = s + t

=\vec{n_n} \cdot (\vec{s} - \vec{t}) )

= \begin{pmatrix} n_x \\ n_y \end{pmatrix} \cdot \begin{pmatrix} (p_x) + (p_x + 1) \\ (p_y + 1) + (p_y + 1) \end{pmatrix}

= n_x \cdot 2 \cdot p_x + n_x + 2 \cdot n_y \cdot p_y + 2 \cdot n_y =: d

Auch hier entscheidet nun wieder die Differenz d welcher Punkt angesteuert werden soll.

Für d >= 0 wird der Punkt T angesteuert.
Für d < 0 wird der Punkt S angesteuert.

Zusammenfassung

Durch die beiden Fallunterscheidungen in 2.1 und 2.2 kann nun im ersten Quadranten jede Linie mit positiver Steigung gezeichnet werden. Wollen wir nun auch die negativen Steigungen zulassen, spiegeln wir den Endpunkt der Strecke in den ersten Quadranten. Dies geschieht indem wir in die passende Gleichung die Absolutbeträge des Punktes und des Normalenvektors einsetzten.

Also für Steigungen mit |m| <= 1

= - ( n_x \cdot 2 \cdot |p_x| \ + 2 \cdot n_x + n_y \cdot 2 \cdot |p_y| + n_y ) =: d

Also für Steigungen mit |m| > 1

= n_x \cdot 2 \cdot |p_x| + n_x + 2 \cdot n_y \cdot |p_y| + 2 \cdot n_y =: d

Literaturnachweise

Olaf Müller, Ralf Kunze, Vorlesungskript SS 2002: Computergrafik, http://www-lehre.inf.uos.de/~cg/2002/skript/node30.html 11.03.2012

J. Frank, Informatik, http://www.wvs.be.schule.de/faecher/informatik/material/grafik/strecke3.html 11.03.2012

Markus Grodd, Der Bresenham-Algorithmus, http://algorithm.name/rasteralgorithmus_1.html, 11.03.2012

Von „http://geometrie.zum.de/index.php?title=Bresenham-Algorithmus_(in_Arbeit)&oldid=22107“