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

Aus Geometrie-Wiki
Wechseln zu: Navigation, Suche
(→‎Bresenham-Algortihmus für Kreise)
(→‎Aufstellen der Gleichungen)
Zeile 112: Zeile 112:
  
 
== Aufstellen der Gleichungen ==
 
== Aufstellen der Gleichungen ==
 +
=== 1.tes Kreisachtel ===
 +
 +
Betrachten wir das erste Kreisachtel
 +
 +
<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" />

Version vom 7. Januar 2013, 16:10 Uhr

Inhaltsverzeichnis

Allgemeines zum Bresenham 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.

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.



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



Hier sieht man dieselbe Gerade um das 8fache 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 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.

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 der Zwei ist für einen Computer eine elementare Rechenoperation, da die sogenannte Shift Operation (Verrückungsoperation) durchgeführt werden kann.

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 Graden

Bresenham-Algortihmus für Kreise

Wir denken uns für jeden Kreis den wir zeichnen ein neues kartesisches Koordinatensystem, dessen Ursprung mit dem Mittelpunkt des Kreises zusammenfällt.
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.


Tangente am Kreis


Symmetrie des Kreises

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.


Aufstellen der Gleichungen

1.tes Kreisachtel

Betrachten wir das erste Kreisachtel

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