Pixel auf einer Geraden

[KPBecker]

Hallo, Delphi-Praktiker,

kennt jemand eine Funktion, die in einem Feld die Pixel-Koordinaten (als x-, y-Paare) einer Geraden zwischen zwei Punkten übergibt ?

Das entspricht in etwa einem LineTo, nur daß die Pixel nicht auf einem Canvas gesetzt werden, sondern die entsprechenden Koordinaten in ein Feld geschrieben werden. Die Linienstärke sei mit "1" angenommen.

Das ist nicht ganz elementar, da je nach der Steigung der Geraden zu einem x-Wert auch mehrere Punkte (mit unterschiedlichen y-Werten) gehören können.

Vielen Dank,
K.-P. Becker

[shmia]

Bresenham-Algorithmus
Bresenham-Algorithmus

[KPBecker]

Danke, das ist's !
K.-P. Becker

[Horst_]

Hallo,

das Ergebnis des Bresenham-Algorithmus' wird immer ein Feld der Länge(MAX(ABS(DeltaX),ABS(DeltaY)) sein.

Zur Veranschaulichung:
Linie von Xu,Yu nach Xo,Yo.

Delphi-Quellcode:

unit Unit1;

interface

uses
  Windows, Messages, SysUtils, Variants, Classes, Graphics, Controls, Forms,
  Dialogs, StdCtrls;

type
  tDyn2DArray = array of Tpoint;//tPoint ist ein vordefiniertes record x,y:integer;

  TForm1 = class(TForm)
    Memo1: TMemo;
    Button1: TButton;
    procedure Button1Click(Sender: TObject);
  private
    { Private declarations }
  public
    { Public declarations }
  end;

var
  Form1: TForm1;

implementation

{$R *.dfm}
procedure LineKoor(P1,P2:Tpoint;var Dyn2DArray:tDyn2DArray);
var
  dx,dy,
  deltaX,deltaY,
  delta,
  i,
  Xu,Xo,
  Yu,Yo     :integer;
 begin
 //DeltaX und DeltaY bestimmen.
Xu:= P1.X;
Yu:= P1.Y;
Xo:= P2.X;
Yo:= P2.Y;
Form1.Memo1.Lines.Add(Format('Von x %d y %d zu x %d y %d',[xu,yu,xo,yo]));

deltaX := Xo-Xu;
deltaY := Yo-Yu;
//Sind die Delta's negativ dann Schritt dx,dy im Vorzeichen ändern
//direkt deltaX und deltaY passend positiv machen.
dx := 1;
dy := 1;

If DeltaX < 0 then
  begin
  deltaX := -deltaX;
  dx := -dx;
  end;

If DeltaY < 0 then
  begin
  deltaY := -deltaY;
  dy := -1;
  end;

If deltaX>=deltaY then
  begin
  setlength(Dyn2DArray,deltaX+1);
  //Bresenham
  delta := deltaX shr 1; 
  For i := 0 to deltaX do
    begin
    with Dyn2DArray[i] do
      begin
      X := Xu;
      Y := Yu;
      //Form1.Memo1.Lines.Add(Format('%d %d %d',[i,x,y]));
      end;
    delta := delta+deltaY;
    if delta > deltaX then
      begin
      delta := delta-deltaX;
      Yu := Yu+dy;
      end;
    Xu := Xu+dx;
    end;//For
  end
else
  begin
  setlength(Dyn2DArray,deltaY+1);
  //Bresenham
  delta := deltaY shr 1;
  For i := 0 to deltaY do
    begin
    with Dyn2DArray[i] do
      begin
      X := Xu;
      Y := Yu;
      end;
    delta := delta+deltaX;
    if delta > deltaY then
      begin
      delta := delta-deltaY;
      Xu := Xu+dx;
      end;
    Yu := Yu+dy;
    end;//For
  end;

//Jetzt stehen die Koordinaten zwar in dem Feld, aber was nun???
end;

procedure TForm1.Button1Click(Sender: TObject);
var
  Dyn2DArray:tDyn2DArray;
begin
  lineKoor(Point(0,0),Point(000,000),Dyn2DArray);
  Memo1.Lines.Add(format('Länge des Feldes %d',[length(Dyn2DArray)]));
  lineKoor(Point(0,0),Point(000,999),Dyn2DArray);
  Memo1.Lines.Add(format('Länge des Feldes %d',[length(Dyn2DArray)]));
  setlength(Dyn2DArray,0);
  lineKoor(Point(0,0),Point(1000,999),Dyn2DArray);
  Memo1.Lines.Add(format('Länge des Feldes %d',[length(Dyn2DArray)]));
  lineKoor(Point(0,-999),Point(-999,999),Dyn2DArray);
  Memo1.Lines.Add(format('Länge des Feldes %d',[length(Dyn2DArray)]));
  lineKoor(Point(0,0),Point(-999,999),Dyn2DArray);
  Memo1.Lines.Add(format('Länge des Feldes %d',[length(Dyn2DArray)]));
  setlength(Dyn2DArray,0);
end;

end.

Gruß Horst

Uups, man sollte nicht zwischendurch Kaffee trinken ;-)
Sodele, jetzt funktioniert es sogar.