Linien plotten mit Bresenham

[Flogo]

Der Bresenham Algorithmus eignet sich um Linien von einem Punkt zum nächsten zu berechnen und dabei zu überprüfen, welche Punkte gezeichnet werden müssen. Da nicht jeder Punkt auf die genauen Koordinaten gezeichnet werden kann muss man entweder die exakte Formel benutzen und jedes mal runden oder eben den Algorithmus von Bresenham verwenden. Dieser kommt mit Additionen (und einer Multiplikation mit 2) und Integern aus und betrachtet jeden Punkt auf der Linie nur ein mal und ist deswegen sehr effektiv.

Das folgende Beispiel habe ich mit diesem Tutorial entwickelt und auf alle 8 Richtungen erweitert:

Delphi-Quellcode:

procedure Bresenham(P1, P2: TPoint);

  procedure TauschePunkte(var P1: TPoint; var P2: TPoint);
  var 
    Temp: TPoint;
  begin
    Temp := P1;
    P1 := P2;
    P2 := Temp;
  end;

var 
  x, y, e, dx, dy: Integer;
begin
  if P1.X > P2.X then TauschePunkte(P1,P2);
  e := 0;          // Der relative Fehler (im Tutorial e' genannt)
  x := P1.X;
  y := P1.Y;
  dx := P2.X - P1.X;
  dy := P2.Y - P1.Y;
  if dy >= 0 then     // positive Steigung
    if dx >= dy then    // leichte positive Steigung
      for x := P1.X to P2.X do
      begin
        Plot(x,y);
        if 2*(e + dy) < dx then
          Inc(e,dy)
        else
        begin
          Inc(y);
          Inc(e, dy-dx);
        end;
      end
    else                // starke positive Steigung
      for y := P1.Y to P2.Y do
      begin
        Plot(x,y);
        if 2*(e + dx) < dy then
          Inc(e,dx)
        else
        begin
          Inc(x);
          Inc(e, dx-dy);
        end;
      end
  else                // negative Steigung
    if dx >= -dy then    // leichte negative Steigung
      for x := P1.X to P2.X do
      begin
        Plot(x,y);
        if 2*(e + dy) > -dx then
          Inc(e,dy)
        else
        begin
          Dec(y);
          Inc(e, dy+dx);
        end;
      end
    else                // starke negative Steigung
    begin
      TauschePunkte(P1,P2);
      x := P1.X;
      dx := P2.X - P1.X;
      dy := P2.Y - P1.Y;
      for y := P1.Y to P2.Y do
      begin
        Plot(x,y);
        if 2*(e + dx) > -dy then
          Inc(e,dx)
        else
        begin
          Dec(x);
          Inc(e, dx+dy);
        end;
      end
    end;
end;

[edit=Matze] Mfg, Matze[/edit]