Diskussion:Bresenham-Algorithmus

nicht rastern sondern eher plotten

Der Algo. von Bresenham ist nicht zum rastern von Gradenstücken da, sondern zum Zeichnen von Linen mithilfe eines Plotters - er läßt sich nur auch für das Rastern von Geradenstücken verwenden - siehe: http://turing.fh-landshut.de/~jamann/bresenham.html

die jetzige, allgemein gehaltene formulierung von wegen "fuer gerasterte ausgabe" ist doch ok, oder? -- seth 21:23, 27. Nov. 2006 (CET)

kompakt fehler?

Ich hab mal versucht die kompakte variante zu implementieren, das gibt bei mir aber nur müll:

void line(int x0, int y0, int x1, int y1)
{
  int dx =  abs(x1-x0), sx = x0<x1 ? 1 : -1;
  int dy = -abs(y1-y0), sy = y0<y1 ? 1 : -1; 
  int err = dx+dy, e2; /* error value e_xy */
 
  for(;;){  /* loop */
    setPixel(x0,y0);
    if (x0==x1 && y0==y1) break;
    e2 = 2*err;
    if (e2 > dy) { err -= dy; x0 += sx; } /* e_xy+e_x > 0 */
    if (e2 < dx) { err += dx; y0 += sy; } /* e_xy+e_y < 0 */
  }
}

Die englische wikipedia hat eine sehr ähnliche kompakte variante:

 function line(x0, y0, x1, y1)
   dx := abs(x1-x0)
   dy := abs(y1-y0) 
   if x0 < x1 then sx := 1 else sx := -1
   if y0 < y1 then sy := 1 else sy := -1
   err := dx-dy
 
   loop
     setPixel(x0,y0)
     if x0 = x1 and y0 = y1 exit loop
     e2 := 2*err
     if e2 > -dy then 
       err := err - dy
       x0 := x0 + sx
     end if
     if e2 <  dx then 
       err := err + dx
       y0 := y0 + sy 
     end if
   end loop

Die scheint funktioniert bei mir. kann nochmal einer die kompakte hier überprüfen? Ich glaube da in der C variante hier das vorzeichen von dy umgedreht ist, müsste die korrekte variante

void line(int x0, int y0, int x1, int y1)
{
  int dx =  abs(x1-x0), sx = x0<x1 ? 1 : -1;
  int dy = -abs(y1-y0), sy = y0<y1 ? 1 : -1; 
  int err = dx+dy, e2; /* error value e_xy */
 
  for(;;){  /* loop */
    setPixel(x0,y0);
    if (x0==x1 && y0==y1) break;
    e2 = 2*err;
    if (e2 > dy) { err += dy; x0 += sx; } /* e_xy+e_x > 0 */
    if (e2 < dx) { err += dx; y0 += sy; } /* e_xy+e_y < 0 */
  }
}

sein (also err += dy anstatt -= dy) ... wenn jemand der gut ahnung hat einverstanden ist, dann kann er das ja vielleicht ändern. (nicht signierter Beitrag von 87.155.72.209 (Diskussion) 15:48, 3. Okt. 2011 (CEST))

Ja, so ist das richtig. Ich habe es im Artikel geändert. (nicht signierter Beitrag von 87.139.40.207 (Diskussion) 14:35, 4. Okt. 2011 (CEST))

Ja, ich hatte zunächst übersehen, dass das dy ja schon als negativ initialisiert wird. Dann stimmt das jetzt so. --PeterFrankfurt 01:41, 5. Okt. 2011 (CEST)

code-beispiele

Wie wär's mit Pseudocode? --PhilippW 18:39, 28. Jun 2004 (CEST)

Wäre ich auf jeden Fall auch dafür. Und ein paar allgemeine Hinweise in Textform könnten für das grundlegende Verständnis sicher auch nicht schaden... Underdog 20:14, 28. Dez 2004 (CET)

Anregung

Die Mathematik hinter dem Uralgorithmus sollte klarer herausgestellt werden. Die für mich entscheidende Idee, nämlich jene, die Gerade stets so zu interpretieren, dass ihre Steigung 0 <= m < 1 ist kommt nicht deutlich heraus. Die englische wiki ist hier viel verständlicher, dafür finden sich dort keine Übertragung auf den Kreis.

Die Krux ist hier, dass das erste Programmbeispiel aus der älteren Artikelversion so elegant ist, dass die Beschränkung auf den ersten Oktanten wegfällt und alle Oktanten mit erfasst werden. Dadurch wird es relativ undurchschaubar. Ich habe dann, als ich später dazukam, genau deshalb noch die zweite, simplere Version hinterhergeschoben, die einfacher zu durchschauen ist und die ich im Einleitungsteil dazu auch halbwegs erklärt habe. Als Neuling damals habe ich es nicht gewagt, diese Version vor die bestehende zu stellen. Vielleicht sollte diese Umstellung doch mal stattfinden. --PeterFrankfurt 02:00, 20. Dez. 2006 (CET)

Der 1. Kreisalgorithmus kann meiner Meinung nach so nicht funktionieren.Zunächst mal : Wozu werden die x2 und y2 berechnet ?

Doch, das geht genau so. Die x2 und y2 sind die x- und y-Quadrate, wie sie in der Kreisgleichung x2+y2=r2 auftreten und für den Fehlerterm verwendet werden. Sie werden halt rekursiv berechnet, um nur shiften und nicht aufwendig multplizieren zu müssen. Und dies alles ist in den Absätzen direkt davor haarklein angekündigt und erläutert. --PeterFrankfurt 02:00, 20. Dez. 2006 (CET)

Die fehler Variable wird anfangs mit einem positiven Wert initialisiert, in der Folge wird dieser Wert nur noch erniedrigt , aber nie mehr erhöht. Ist er also erstmal < 0 bleibt er es auch.

Nein, da steht doch die Zeile "fehler = fehler+dx", die bei einem Schritt in die langsame (x-)Richtung den Fehlerterm wieder ins Positive holt. --PeterFrankfurt 02:00, 20. Dez. 2006 (CET)

Bild zur Veranschaulichung

Hallo, im englischen und französichen Artikel sind Bilder eingebunden, könnten wir Bild:Bresenham.png nicht auch einbinden? --Marco.Geisler 11:08, 2. Feb. 2007 (CET)

Gute Anregung, gleich umgesetzt, obwohl mir da noch wesentlich aufwendigere Möglichkeiten vorschweben. Dabei habe ich auch gesehen, wie in jeder Version völlig andere Implementierungen als Beispiel aufgeführt werden, und die Kreisversion gibt es nur hier :-). --PeterFrankfurt 22:20, 2. Feb. 2007 (CET)

Vielen Dank! Mit dem Bild in versteht man das viel schneller. --Marco.Geisler 20:50, 4. Feb. 2007 (CET)

Wer sich übrigens für den originalen Bresenham-Ansatz interessiert, der noch ein bisschen anders, geometrischer geht, sollte in die italienische Version reinschauen. Ich kann zwar mit meinem Mikro-Latinum kaum ein Wort lesen, die Bilder sprechen aber dafür, dass dort 1:1 nach Original-Bresenham vorgegangen wird. --PeterFrankfurt 16:07, 27. Feb. 2007 (CET)

Fehlerglied

Hallo,

Der Konsistenz halber sollte man das Fehlerglied F mit (y-ystart)*dx - (x-xstart)*dy definieren statt (x-xstart)*dy - (y-ystart)*dx. Wie man sieht wird im Algorithmus bei einem Schritt nach rechts dy vom Fehlerglied subtrahiert, statt addiert, wie die jetzige Formel vorgibt. Auch der Rest des Textes scheint sich auf die alternative Definition des Fehlerglieds zu beziehen (Fallunterscheidung: F < 0, F > 0).

Oh, in der Tat, danke für den Hinweis. Ich hatte das sogar erst letztens selbst verschlimmbessert, sorry. --PeterFrankfurt 23:57, 16. Feb. 2007 (CET)

Elegant?

Mich würde die hier angewandte Definition von "elegant" interessieren. Ich finde die erste Implementierung viel eleganter als die zweite, schon weil sie viel kürzer und einfacher ist. Natürlich ist sie weniger allgemein als die zweite, vielleicht sollte man "elegant" durch "allgemein" ersetzen?

Auch der Hinweis "..., das die Fallunterscheidung in acht Oktanten nicht ausdrücklich vornehmen muss" ergibt für mich keinen Sinn: genau das passiert doch am Anfang der Funktion mit diesen ganzen if-Klauseln (die für mich im Übrigen keineswegs unter elegante Programmierung fallen). Eriatarka 13:51, 27. Feb. 2007 (CET)

Nun ja, das ist wahrscheinlich Ansichtssache. Jene "elegante Version" ist nicht von mir, und ich wollte sie durchaus als Kontrast zu meiner Simpel-Lösung stehen lassen. Wenn ich meine eigene Komplettversion für alle Oktanten anschaue, die ich hier auch vorliegen habe (allerdings in Assembler, also kaum zur Veröffentlichung geeignet), sieht sie wesentlich umständlicher aus. Insofern fand ich das Etikett "elegant" für angemessen. Also wie gesagt: "elegant" in relativem Sinn, im Vergleich zu anderen, noch weniger eleganten Lösungen. --PeterFrankfurt 16:04, 27. Feb. 2007 (CET)

Elegantere Implementierung

Es sollte darauf hingewiesen werden, dass sich der vorgestellte Code nicht für schnelle Rasterung eignet, da der Aufruf von malloc und das Schreiben in den Array viel Zeit kostet. --Phrood 19:17, 2. Mär. 2007 (CET)

Tja, ich bin kein großer C-Guru, aber ich kann mir vorstellen, dass man das auch ein bisschen effizienter umformulieren könnte. Deswegen habe ich ja auch "elegant" drübergeschrieben, nicht "schnell" :-). --PeterFrankfurt 22:01, 2. Mär. 2007 (CET)

Eigentlich ist der Algorithmus sogar für den ernsthaften Einsatz unpraktikabel. malloc bedeutet, dass eine API-Funktion aufgerufen wird (bei Windows z.B. VirtualAlloc), die Zeit für Aufruf+Ausführung braucht. Zusätzlich ist bei modernen Prozessoren jeder Zugriff auf den Speicher, besonders, wenn sich der Speicherbereich nicht im Cache befindet, furchtbar langsam. --Phrood 22:11, 2. Mär. 2007 (CET)

Bresenham oder nicht?

Der von PeterFrankfurt in diesem Artikel beschriebene Algorithmus ist nicht mit dem Bresenham-Algorithmus identisch und auch nicht äquivalent, da er andere Ergebnisse liefert. Es gibt dazu eine längere Diskussion auf Benutzer Diskussion:PeterFrankfurt#Weiteres Vorgehen. Es wäre wünschenswert, wenn sich noch andere Benutzer zu dem Sachverhalt äußern würden. --Phrood 22:36, 2. Mär. 2007 (CET)

Der Algorithmus ist anders, aber doch äquivalent. Der Fehler im Vergleichstest der beiden Algorithmen wurde gerade erkannt. Der hier dargestellte Algorithmus liefert also doch identische Ergebnisse und gehört nach seinem Grundmechanismus eindeutig in die "Bresenham-Familie". Mir ist kein anderer passender Name für so einen Algorithmus bekannt. Code-Snippets zum Vergleichstest auf meiner Diskussionsseite. --PeterFrankfurt 23:21, 2. Mär. 2007 (CET)

OK, der Fehler lag bei mir. Der Algorithmus ist tatsächlich äquivalent zu Bresenham. --Phrood 23:24, 2. Mär. 2007 (CET)

Mal abgesehen davon ob er äquivalent ist oder nicht: Dieser Artikel handelt doch von Bresenham. Dann sollte auch der diskutiert werden. Andere Artikel beschäftigen sich allgemeiner mit Linienrasterisierung. -- Odx 11:20, 16. Feb. 2010 (CET)

Deswegen gibt es doch die Gegenüberstellung mit dem originalen Algorithmus, er wird ja nicht verschwiegen. Jedermann kann das über den verlinkten Originalartikel nachvollziehen. Hier geht es ja nur um eine leicht abweichende Implementierung, nicht um einen ganz anderen Algorithmus, das wäre ja nochmal was anderes. --PeterFrankfurt 01:27, 17. Feb. 2010 (CET)

Link auf Matrixanzeige

Mir scheint, der Bergriff Matrixanzeige wird nur bei kleinen Displays und nicht bei normalen Bildschirmen verwendet. --Phrood 18:57, 12. Mär. 2007 (CET)

Das sind bloß die Beispielbilder in dem Artikel, der Begriff selbst und auch der Artikeltext gilt vollkommen allgemein. --PeterFrankfurt 19:45, 12. Mär. 2007 (CET)

"Elegante" Basic-Version

Also wenn ich schon sowas einstelle, fände ich es nur höflich, mir meinen Formatierungs- und Einrückungsstil zu lassen, auch wenn der vom "konventionellen", aber in meinen Augen unlogischeren, abweicht. Pfft.

Und die SGN()-Funktion, die in Basic eine simple Anweisung ist, braucht in der angeführten C-Implementation schlappe 12 Zeilen in handaufgedröselter Form. Vielleicht sollte man das mal ein bisschen streamlinen. --PeterFrankfurt 01:50, 14. Sep. 2007 (CEST)

gudn tach!

1. format-/indentstyle (c-code): ich weiss, dass es da verschiedene standards gibt (k&r, gnu, ...), jedoch war das c-beispiel durcheinander formatiert, weshalb ich mir einfach eine klammernsetzungsart herauspickte und die dann durchgaengig anwendete. (ich vermute, dass du bloss ueber meine basic-code-aenderungen sprichst, aber ich sage es trotzdem sicherheitshalber mal dazu.)

2. beim basic-code habe ich laenger ueberlegt, ob ich tatsaechlich etwas aendern soll, da mir das "(haupt-)autorenrecht" hier in der wikipedia bekannt ist (und ich es auch in den meisten faellen unterstuetze). da jedoch deine einrueckungsart afaik sehr selten in fach-/lehrbuechern verwendet wird (oder irre ich mich diesbzgl.?), ersetzte ich den stil durch einen, der den meisten leuten eher gaengig sein sollte. und wenn mehrere arten "gleich" richtig sind, dann sollte eine einzyklopaedie doch eher die verwenden, welche die meisten leute verstehen, oder?

3. die sgn-funktion in basic macht code nicht "wesentlich" kuerzer. a=SGN(b) in basic kann in c geschrieben werden als a=(b>0)-(b<0);. ich gebe zu, dass "sgn" schneller zu verstehen ist, aber nur in bezug auf die code-laenge nimmt/gibt sich das kaum was. und ganz abgesehen davon, kann man in c natuerlich auch einfach die function sgn definieren und dann ebenfalls einfach "sgn" schreiben.

4. was genau meinst du "streamlinen"? mir persoenlich gefaellt code besser, wenn fuer klammern nicht einzelne zeilen geopfert werden (meintest du auch sowas?). aber da es nun mal sehr viele leute gibt, die viel leerraum moegen, und es sogar standards zu dieser klammernsetzung gibt, habe ich mich nicht getraut, da handanzulegen, denn schliesslich hat ja der autor ein gewisses recht auf jene formatierung. ;-) -- seth 09:56, 14. Sep. 2007 (CEST)

Zu 4.: Ich meine konkret das C-Beispiel zur "eleganten Formulierung": Dort wird die Funktionalität der sgn()-Funktion von Hand in 12 oder 13 Zeilen umständlichst nachgebildet. Ich bin mit Dir einer Meinung, dass man sowas auch bei C in eine Zeile packen kann, die "Features" von Fortran und Assembler mit nur einer Anweisung je Zeile muss man ja nicht künstlich konservieren. Mir geht es dabei in diesem Fall gar nicht um die Einrückung (nur um die Umständlichkeit), die ist bei C noch viel mehr ideologiebehaftet als in anderen Sprachen, da halte ich mich raus, da ich kein großer C-Kenner und -Anwender bin (nur ein bisschen). Wenn also jemand diese Source etwas optimieren möchte, darf er es von mir aus gerne tun. Aber bei Basic habe ich eben meine eigene Ansicht. Das kommt daher, dass ich ursprünglich mit Algol 60 aufgewachsen bin, mit begin und end (wie später in Pascal), und die rückte man beide immer schön ein, weil sie halt eindeutig hierarchisch ihrer übergeordneten Klausel (for, if) untergeordnet waren. Genauso ist das END IF dem IF untergeordnet, gehört für mich also logischerweise mit eingerückt. Im Unterschied zu NEXT und FOR (die ich aus demselben Grund einrücke) ist END IF außerdem ganz verzichtbar, wenn man alles hinter das THEN quetschen kann, ein weiteres Indiz für die Untergeordnetheit. --PeterFrankfurt 11:01, 14. Sep. 2007 (CEST)

zum c-code: ich habe jetzt eine sgn-funktion eingefuehrt, die zwar nur aus einer zeile besteht, aber aufgrund des namens "sgn" besser verstaendlich sein sollte.

Ah, gut, sieht doch gleich viel besser aus.

zum basic-code: bei dem kurzen code-stueck sollte es eigentlich eh egal sein, ob nun so oder so formatiert wird, weshalb ich darauf auch gar nicht weiter rumreiten moechte. -- seth 00:43, 15. Sep. 2007 (CEST)

Danke, irgendwo habe ich halt auch meine Sensibilitäten... :-) --PeterFrankfurt 01:47, 15. Sep. 2007 (CEST)

Warum benutzen die Versionen in C und Basic verschiedene Herangehensweisen um die Oktanten zu berücksichtigen? Ich finde die C Version sollte auch die Unterscheidung in Parallel- und Diagonalschritt machen, weil dadurch die Schleife kürzer wird. 89.55.29.185 00:41, 6. Dez. 2007 (CET)

Die C-Version hat ein ganz anderer Autor eingestellt, und ich habe Skrupel, in seiner Arbeit herumzuwühlen. Bei Listings ist die Hemmschwelle für mich wesentlich höher als in reinen Textpassagen, meinen eigenen Senf auszubreiten. Die Umsetzung der Basic-Implementierung in C bleibt also als Übung dem Studenten überlassen ... --PeterFrankfurt 01:10, 7. Dez. 2007 (CET)

Egal vom wem die C-Version ist, die sgn-Funktion sollte Geändert werden:

-> return (x > 0) ? 1 : (x < 0) ? -1 : 0;

Sonst ist das im ersten Augenblick etwas schwer zu Verstehen. (Und bestimmt ein paar Millisekunden langsamer ;D)

--Noxious - Unterwegs im Auftrag des Hirn. 15:46, 22. Feb. 2008 (CET)

Implementierung des Algorithmuses für Kreise

Die Implementierung des Algorithmusses für Kreisränder in C hat eine kleine unschöne Stelle. Für den Fall x=y werden die Punkte doppelt gezeichnet. Das macht den Algorithmus nicht falsch, dennoch gefällt es mir nicht. Man sollte im Text zumindest einen Hinweis dazu schreiben. Eine Verbesserung ist meiner Ansicht nach nicht möglich, da ein Test auf Gleichheit an dieser Stelle möglicherweise mehr Rechenaufwand bedeuten würde als einfach den Pixel noch einmal zu setzen.

Ich komme darauf weil ich bei einem Datenanalyseproblem gerade die Summe aller Helligkeitswerte auf einem Kreisrand in einem Bild benötige. Mir ist dabei aufgefallen dass die vorgestellte implementierung die oben genannte Eigenschaft hat. Um anderen Benutzern mit ähnlichen Problemen zu helfen sollte zumindest erwähnt werden dass manche Punkte doppelt gesetzt werden.

Gruß, Roland Winkler (nicht signierter Beitrag von 129.247.247.238 (Diskussion) 16:22, 11. Apr 2008)

Ja, das ist ein bekanntes und nach meiner Kenntnis bisher nicht befriedigend gelöstes Problem. Es kommt nämlich auf den Radius an, nach dem es zwei Fälle gibt: Beim einen Fall liegt der letzte Punkt eines Oktanten genau auf der Diagonalen, und wenn man den Nachbaroktanten genauso zeichnet, kommt dieser Punkt doppelt. Im anderen Fall liegt der letzte Punkt eines Oktanten direkt vor der Diagonalen und der entsprechende Punkt im Folgeoktanten genau ein Pixel diagonal versetzt, so dass es dann keinen Konflikt gibt. Wie man diese Fälle sauber und trotzdem elegant erkennt, muss noch jemand vormachen, ich habe das noch nicht gesehen, und selbst finde ich auch keine richtig gute Lösung. Aber die Angelegenheit behalte ich im Auge. - Aus meiner Erfhrung, wo ich mit mechanischen Plottern zu tun hatte, ist das Problem vor allem dann akut, wenn man die Nachbaroktanten durchgehend zeichnen will und den zweiten dabei also "rückwärts" angehen muss, dann sind diese Punktdoppelungen erst recht übel. Ich hatte mich da immer mit absoluten Koordinaten und schlimmstenfalls Mehrfachanfahren desselben Punktes beholfen (Hauptsache, ich bekomme keinen ungewollten Versatz um so ein Diagonalpixel hinein), aber das war weder elegant noch schnell, eher eklig... --PeterFrankfurt 02:11, 12. Apr. 2008 (CEST)

BKL anlegen

Ich bin dafür, unter diesem Lemma eine BKL zu Rasterung von Linien und Rasterung von Kreisen anzulegen, wo die beiden Bresenham-Algorithmen bereits beschrieben werden. Erstens ist es unschön, in einem Artikel zwei verschiedene Algorithmen zu beschreiben. Zweitens ist es nicht die Aufgabe eines Artikels, verschiedene Implementierungen eines Algorithmus in unterschiedlichen Sprachen zu liefern, sondern nur das Prinzip zu demonstrieren, am besten mittels Pseudocode, und das leisten die genannten Artikel m. E. besser. --Phrood 23:04, 27. Apr. 2008 (CEST)

Hmm, eine BKL für gerade zwei Varianten halte ich für übertrieben. Im Übrigen würden die Vorschläge im Endeffekt auf eine Löschung dieses Artikels hier hinauslaufen, wofür ich natürlich nicht zu haben wäre. --PeterFrankfurt 02:09, 28. Apr. 2008 (CEST)

BKLs mit nur zwei Einträgen sind nicht unüblicher als andere. Redundanzen sollten grundsätzlich vermieden werden. Welche der hier erwähnten Informationen fehlen dir denn in den beiden anderen Artikeln? --Phrood 07:14, 28. Apr. 2008 (CEST)

Eben die konkreten Implementierungen und die Herleitung der Bresenham-Methode, wie sie hier dargestellt wird. Ich habe schon mal eine Mail von einem User bekommen, der sich ausdrücklich für das direkt benutzbare Listing bedankte, weil er es so erst richtig verstehen konnte. (Mir geht es mit sowas genauso, deshalb lege ich da auch so Wert drauf.) - Die Redundanz wird doch schon dadurch vermieden, dass in Deinen Übersichtsartikeln vor allem die Familie im Vergleich von ähnlichen Algorithmen präsentiert wird, während sich hier auf diese eine Variante und ihre Implementierung konzentriert wird. Das kann man wunderbar verantworten. --PeterFrankfurt 00:38, 29. Apr. 2008 (CEST)

Urheberrecht

Kann ich den "Bresenham" beliebig verwenden, oder kollidiere ich dann mit irgendeinem Urheberrecht ? --dreysacz 11:02, 14. Jul. 2008 (CEST)

Ein Patent wäre mittlerweile abgelaufen, ansonsten gibt es für solche Erfindungen keinen Urheberschutz, der den 75 Jahren für künstlerische Produkte vergleichbar wäre. Man kann das beruhigt benutzen. Man kann auch gern den Namen als Referenz in Kommentaren oder so erwähnen, um sich nicht mit fremden Federn zu schmücken. Aber Lizenzgebühren braucht man keine zu zahlen. --PeterFrankfurt 00:06, 15. Jul. 2008 (CEST)

Oktand?

Im Artikel ist die Rede vom ersten Oktanden aber imho ist der Bresenham doch für zwei Dimensionen. Sollte das nicht Quadrant heissen? (nicht signierter Beitrag von 91.66.119.253 (Diskussion) 21:00, 2. Nov. 2008 (CET))

(bitte unterschreiben) Jein, es geht um was anderes: Das Verfahren ist erstmal nur für Steigungswinkel von 0 bis 45 Grad geeignet. Um auf den ganzen Kreis zu kommen, muss man das 8 Mal nehmen, deswegen spricht man (in der Ebene) von 8 Oktanten = 8 Winkelsektoren a 45 Grad. Die 8 kann man als 2 hoch 3 ansehen, man braucht also 3 binäre Fallunterscheidungen, um alle diese 8 Fälle abzudecken: 1. Vorzeichen von dx, 2. Vorzeichen von dy, 3. Vertauschung der Rolle von x und y. Macht 8 Fälle/Oktanten. --PeterFrankfurt 01:54, 3. Nov. 2008 (CET)

Siehe Oktant_(Geometrie)#Oktanten im zweidimensionalen Raum. Vielleicht sollte ich dort nochmal eine Grafik zur Veranschaulichung dazupacken, was meint ihr? --RokerHRO 09:19, 3. Nov. 2008 (CET)

Ah, jetzt sehe ich erst, woher die Frage kam, weil in dem verlinkten Oktantenartikel diese 3D-Darstellung dominiert. Ich habe den Link mal auf das Unterkapitel präzisiert, was in der Praxis allerdings wegen der Kürze des Artikels nichts an der Anzeige ändert... --PeterFrankfurt 23:30, 3. Nov. 2008 (CET)

@peterfrankfurt genau daher kam meine frage =) und vielen dank für die erläuterung 88.134.219.186 19:56, 11. Nov. 2008 (CET)

Lizenz des C codes?

Unter welcher Lizenz steht der C-Code? Würde ihn gerne in einem großen open-source project nutzen, das es jedoch auch in einer proprietären version gibt (und dort auch ohne probleme nutzbar sein sollte). (nicht signierter Beitrag von 213.47.219.86 (Diskussion | Beiträge) 19:19, 11. Aug. 2009 (CEST))

Angelehnt sind diese Codebeispiele ja an jeweils aufgeführte Literaturstellen, die sollte man ggf. zumindest erwähnen. Und alle WP-Inhalte stehen sowieso unter Wikipedia:Lizenzbestimmungen, die laufen auch darauf hinaus, dass das in Open-Source-Projekten immer verwendet werden darf, aber halt mit Erhaltung der Herkunftsangabe. --PeterFrankfurt 01:47, 12. Aug. 2009 (CEST)

implementierungen auslagern

gudn tach!
mag jemand die implementierungen auslagern nach b:de:Algorithmensammlung? so wie z.b. in heapsort. -- seth 22:18, 21. Okt. 2009 (CEST)

Ist das denn auch angebracht, wenn wie hier großer Erklärungsbedarf besteht, so dass zu jeder Zeile des Algorithmus grob ein Absatz Text gehört? Und der Text ohne den nahebei stehenden Code auch nicht unbedingt sofort verständlich ist? Also ich zögere da etwas. In der Algorithmensammlung wird doch anscheinend normalerweise nicht so viel erklärt. --PeterFrankfurt 02:40, 22. Okt. 2009 (CEST)

gudn tach!

die algorithmensammlung ist noch im aufbau. erklaerungen sind da sicher nicht unwillkommen. aber ich stimme dir zu, dass der algorithmus, wenn er genau erklaert wird, auch ruhig hier (und in einer beliebigen sprache) bleiben sollte. man kann sich ueberlegen, ob man eine (abgespeckte) kopie in der algorithmussammlung unterbringt. solche redundanz schadet ja nichts.

jedoch z.b. der enzyklopaedisch redundante(?) java source code waere in der algorithmen-sammlung gut aufgenhoben. die sammlung wurde vor allem aus dem grund gebaut, um die wp-artikel von mehrfachen implementierung des gleichen algorithmus zu befreien. -- seth 21:15, 22. Okt. 2009 (CEST)

Aha, hört sich vernünftig an. Allein, ich fürchte noch ein bisschen die Redundanz-Falle, dass einem das dann nachträglich doch unter dem Hintern weg gelöscht wird, die Löschfanatiker sind gerade wieder unterwegs :-(. --PeterFrankfurt 02:21, 23. Okt. 2009 (CEST)

verstehe, koenntest ja den code ohne die erklaerung ins algo-buch rueberverfrachten. -- seth 20:09, 23. Okt. 2009 (CEST)

Ok, mache ich demnächst mal, wenn ich zu normaleren Zeiten dazu komme. --PeterFrankfurt 02:29, 24. Okt. 2009 (CEST)

Fehler in der "eleganten" Implementierung?

Habe versucht, das Ding aus dem Basic-Code nachzuprogrammieren und bin über die Variablen es und el (Fehlerschritte schnell bzw. langsam) gestolpert. Liegt hier eine Vertauschung vor? Sollte nicht, wenn x die schnelle Richtung ist auch es = adx sein (dito bei y als schnelle Richtung). Wenn immer ein Pixel in die schnelle Richtung gezeichnet wird, sollte die Schleife bis es laufen, oder? Bin mir nicht sicher, ob es mit einer konsistenten Umbennenung getan ist. --Rat 11:38, 9. Sep. 2010 (CEST)

Nein, das ist ja gerade der Trick, dass die Koordinaten "überkreuz" verwendet werden: Vom Fehlerglied wird bei jedem Schritt die kleinere Absolutdifferenz es abgezogen und nur bei den Diagonalschritten die größere Absolutdifferenz el wieder draufaddiert. Dieses Überkreuzsubtrahieren und -addieren entspricht (wie irgendwo im Artikel erläutert) der Rückführung der Division (für den Steigungsfaktor m=dy/dx) auf Subtraktion und Addition. --PeterFrankfurt 03:18, 10. Sep. 2010 (CEST)

Einfache C Variante

Die Formulierung kannte ich noch nicht, sieht ja ultrakompakt aus. Gibt es dazu vielleicht noch irgendwelche Quellenangaben? --PeterFrankfurt 00:52, 13. Dez. 2010 (CET)

Nein. Ich habe nur meine Variante des Bresenham-Algorithmus gepostet weil mir die anderen so langwierig schienen. -- Alois zingl 17:07, 14. Dez. 2010 (CET)

Nach einigem Meditieren über dieser Formulierung habe ich auch den Haken an der Sache gefunden: Für jedes Pixel werden in der Hauptschleife hier ZWEI IFs ausgeführt, in der längeren Version davor nur eines. Ich bin bei der Performance so auf IFs fixiert, weil sie relativ viel Performance kosten, das kann bei so einer kompakten Schleife schon in zweistellige Prozentunterschiede reichen. --PeterFrankfurt 01:36, 13. Dez. 2010 (CET)

Also ich bin der Meinung in Wikipedia sollten eher anschauliche Beispiele stehen. Falls solch hochoptimierter Code tatsächlich nötig sein sollte, wäre zudem eine Variante überhaupt ohne IFs in der Schleife (bzw. nur der Abbruchbedienung) noch ratsamer. Dies kann erreicht werden indem die Variante mit Fließkommaberechnung des Bresenham-Algorithmus (Inkrement) mit Festkommazahlen realisiert wird:

void line(int x0, int y0, int x1, int y1)
{
    int sx, sy;
    x1 -= x0; y1 -= y0;
    if (abs(y1)>abs(x1))
    {
        sy = y1<0 ? -1 : 1; /* grosse Schrittweite: +/-1 */
        sx = abs(y1);  /* kleine Schrittweite ... */
        if (sx!=0) sx = (x1<<16)/sx; /* ... als Festkommazahl */
        for (x1 = 0; ; y0 += sy, x1 += sx) 
        {
            setPixel(x0+(x1>>16),y0);
            if (y0==y1) break;
        }
    } else 
    {
        sx = x1<0 ? -1 : 1;
        sy = abs(x1);
        if (sy!=0) sy = (y1<<16)/sy;
        for (y1 = 0; ; x0 += sx, y1 += sy)
        {
            setPixel(x0,y0+(y1>>16));
            if (x0==x1) break;
        }
    }
}

-- Alois zingl 17:07, 14. Dez. 2010 (CET)

Ähm, zu "anschaulich": Deine ultrakompakte Version erscheint mir allerdings überhaupt nicht anschaulich. Erst nach langem Studieren (war zu faul, es schnell mal in den Compiler zu werfen) habe ich mich dazu aufgerafft zu glauben, dass das wirklich funktioniert, vor allem auch in allen acht Oktanten. - Zur neuen Formulierung oben: Das Ganze in zwei Schleifen je nach Rolle von x und y aufzuteilen, war mir auch schon mal in den Sinn gekommen, aber das verwirrt den Laien m. E. auch eher mehr. Und diese Fließkommaarithmetik mit den vollkommen willkürlichen 16 Bitstellen Skalierungsfaktor (eine Linie darf nicht länger als 64 K Pixelschritte sein!) finde ich erstens abenteuerlich und zweitens langsam, weil die wilden Shiftereien und Fließkommarechnungen in der Hauptschleife stattfinden, davon hat uns Bresenham ja gerade erlöst. Übersichtlicher wird es dadurch nicht. Und die Abbruchbedingung ist in dieser Form auch arg merkwürdig, wenn man schon eine for-Schleife hat. - Wie gesagt, die andere Formulierung im Artikel finde ich wegen ihrer Kompaktheit attraktiv, aber performancemäßig und übersichtsmäßig nicht so optimal. --PeterFrankfurt 01:57, 15. Dez. 2010 (CET)

Die Variante oben ist eine spezielle Lösung für besondere Anforderungen - nicht für Wikipedia gedacht. Die einfache Variante ist aber entsprechend nach dem Prinzip Bresenham. Die vier Quadranten werden über das Vorzeicheninkrement (sx, sy) abgedeckt. Die Akkumulation des Fehlerglieds löst bei Überschreitung des Schwellwertes den bedingten Schritt aus, im Unterschied zur ursprünglichen Variante eben simultan in beide Richtungen: positive Fehlerwerte für x und negative für die y-Achse. Ich finde sie zeigt damit auch elegant die xy-Symmetrie des Bresenham-Algorithmus. Vielleicht aber wäre kompakt wirklich die passendere Bezeichnung dafür. -- Alois zingl 16:34, 16. Dez. 2010 (CET)

Elegant: keine Frage. Aber diese simultane Aktion in beide Koordinatenrichtungen ist erstmal extrem undurchsichtig, denn obwohl ich mich seit vielen Jahren mit der Materie beschäftige und schon einige Varianten zu sehen bekommen und ein paar selber verbrochen habe, musste ich hier erst lange meditieren, bevor ich das überhaupt "geglaubt" habe. --PeterFrankfurt 03:17, 17. Dez. 2010 (CET)

Die neue Kreisvariante habe ich noch nicht kapiert, habe aber großes Vertrauen, dass sie ok ist. Allerdings sehe ich da noch Optimierungspotential: Die dauernd neu berechneten Quadrate a*a und b*b schreien doch nach eigenen, vorab einmalig berechneten Variablen. Und kann man diese Quadratberechnung hier nicht auch wie weiter oben ausgeführt durch Rekursion und lineare Rechnung ersetzen? --PeterFrankfurt 02:46, 23. Dez. 2010 (CET)

So großartig sind die Optimierungsmöglichkeiten nun auch nicht. Ich sehe den Schwerpunkt eher darin das Prinzip des Bresenham-Algorithmus darzustellen und nicht jedes Quäntchen Geschwindigkeit rauszupressen. Optimierungen wie Werte im voraus zu berechnen oder das Programm durch zusätzliche Variablen zu Beschleunigen sind leicht zu implementieren und überlasse ich gerne dem Leser, dadurch wird das Programm aus meiner Sicht aber nur unübersichtlicher. Für mich ist der kompakteste Code auch der einfachste :-) Zudem sind Optimierungen von der Programmiersprache, der Zielsetzung und -platform etc. abhängig. Die momentane 'Rohfassung' ist also auch leichter an andere Erfordernisse anzupassen.

Ist das Prinzip des Algorithmus wirklich so schwer verständlich? Für die Fehlerberechnung des Viertelkreises e=x²+y²-r² wird ein Diagonalschritt angenommen e_xy=(x+1)²+(y-1)²-r²=e+2x-2y+2 und korrigiert wenn der benachbarte Punkt oben e_x=e+2x+1 oder daneben e_y=e-2y+1 einen geringeren Fehler aufweist. Bei e_xy+e_x<0 wird also x erhöht, bei e_xy+e_y>0 y erniedrigt. Ähnliches kann man für Linie bzw. Ellipse formulieren. -- Alois zingl 17:13, 23. Dez. 2010 (CET)

Ah, mit diesen Erklärungen dämmert es langsam. Vielleicht werde ich den Text noch etwas ergänzen. - Dass Du mehrere Anweisungen in eine Zeile packst, was C ja erlaubt, heutzutage aber angesichts Politischer Korrektheit sowas von verpönt ist, macht Dich richtig sympathisch. Ich habe das nur ganz vorsichtig in der Basic-Version gewagt. So finde ich es im Prinzip auch übersichtlicher, weil mehr auf einen Blick erfassbar wird. - Aber ist diese Formulierung nun von Dir selber oder geht sie auf irgendwelche Quellen zurück? --PeterFrankfurt 02:12, 28. Dez. 2010 (CET)

Fehler in Bresenham-Kreis-Abbildung

Die Abbildung zur Kreisvariante des Algorithmus (Untertitel "Rastern einer Kreislinie nach dem Bresenham-Verfahren") ist nicht korrekt. Der von links gezählt achte Pixel (der letzte vor dem auf der Diagonalen) muss um einen Pixel weiter nach unten versetzt werden. Der Grund ist, dass für x=7 (was der betrachteten Spalte entspricht) ein exakter y-Wert von Sqrt(11^2-7^2)=8,485... herauskommt, also ein Wert, der gerundet eben nicht 9, sondern 8 ergibt, was der um eins nach unten versetzten y-Position entspricht. Für jeden ganzzahligen x-Wert muss der y-Wert des idealen Kreises nämlich einfach auf den nächsten Ganzzahlwert gerundet werden, um einen Pixel zu bekommen, der nach dem Bresenham-Algorithmus erstellt werden würde. Dies gilt für alle Bresenhamartigen Algorithmen, da diese die sog. Grid-Intersection-Digitization implementieren.

Dies deckt sich auch mit dem tatsächlichen Ergebnis, das sich mit der angegebenen Implementation ergibt. Wenn man diese durchlaufen lässt, ergbt sich eine Kurve der folgenden Form:

x x x x
        x x
            x
              x x
                x 
                  x
                  x
                    x
                    x
                    x
                    x

Dasselbe gilt übrigens für den englischen "Midpoint circle algorithm"-Artikel und ggf. für weitere Sprachen.

--Plotin3D (Diskussion) 12:33, 9. Okt. 2012 (CEST)

Der gleiche "Fehler" tritt auch unter Windows (GDI-Funktion Ellipse(), ab 2.x) auf. Aber das Doppelpunktproblem haben die irgendwie gelöst. --134.109.9.75 15:54, 20. Mär. 2013 (CET)

Zum Abschnitt: "Zeichnen nicht-vollständiger Oktanten"

Meiner Ansicht nach ist dies, so wie es dort beschrieben steht, nicht ganz richtig. Man kann so einen Kreisbogen von alpha bis beta nämlich doch ohne Trigonometrie/Wurzelrechnung zeichnen, indem man einen ganzen Kreis entlang läuft, die Wertpaare (x,y) zwischenspeichert (z.B. als Array) und hinterher dieses Array nochmal durchläuft, wobei man nur die Punkte tatsächlich zeichnet, für die a <= i <= b mit a < b gilt. Dabei ist i der Arrayindex, a ist gerundet "N * alpha/2*Pi" und b ist gerundet "N * beta/2*Pi". Die int-Variable N steht wiederum für die Gesamtanzahl an Paaren (x,y), die man ja beim Durchlaufen des Kreises ermitteln kann. Ich hoffe ihr versteht, was ich meine. Ob das ganze wirklich schneller ist, als mit trigonometrischen Funktionen und Wurzelberechnungen, wage ich jedoch zu bezweifeln, denn es müssen wiederholt eine Menge Daten kopiert werden. Ich habe es selbst so implementiert und könnte bei Bedarf meine Lösung mal hochladen.--130.75.180.129 23:58, 6. Aug. 2013 (CEST)

Du hast vollkommen recht. Dass da im Artikel steht, man "muss" es so und so machen, ist in der Tat nicht korrekt. Mach aus dem Obigen doch einfach mal einen koonkreten Formulierungsvorschlag, da kann man sich bestimmt einigen. --PeterFrankfurt (Diskussion) 00:05, 8. Aug. 2013 (CEST)