Entwickler-Ecke

Algorithmen, Optimierung und Assembler - Linie selber zeichnen


hui1991 - Sa 08.12.07 23:54
Titel: Linie selber zeichnen
Hi,

da mir Google und das Forum nichts über das Zeichnenverfahren von Linien am PC verraten wollte, frage ich euch.
Ich habe ein Gitternetz. 800x600 Pixel. Ich habe ein Startpunkt und ein Endpunkt.
Wie zeichne ich eine Linie?

Quelltext
1:
2:
3:
4:
5:
OOOOXXX0OOOOOOOOOOOOOOOOOOOOOOOOO
OOOOO00XXXX0OOOOOOOOOOOOOOOOOOOOO
00000000000XXXX0OOOOOOOOOOOOOOOOO
OOOOOOOOOOOOOOOXXXX0OOOOOOOOOOOOO
OOOOOOOOOOOOOOOOOOOXXXXXOOOOOOOOO


Ich brauch das eigentlich nur zum verstehen, wie das die LineTo eigentlich so macht ^^

MfG
hui1991


FinnO - Sa 08.12.07 23:56


Delphi-Quelltext
1:
2:
3:
4:
begin
image1.canvas.moveto(X,Y) // Sich zu beliebigen Koordinaten in Image1 bewegen
image1.canvas.lineto(X1,Y1)// von X,Y eine Linie nach X1,Y1 zeichnen
end;


hui1991 - So 09.12.07 00:00

Kannst du mir auch erklären wie LineTo das anstellt?


FinnO - So 09.12.07 00:03

Wie wie das LineTo das anstellt? ich meine es färbt alle Pixel Linear bis zum Zielpunkt schwarz oder was meinst du ??? :?:


>M@steR< - So 09.12.07 00:07

Gelöscht


>M@steR< - So 09.12.07 00:09

Gelöscht


TGLDX - So 09.12.07 00:15

Schau dir mal den Bresenham-Algorithmus [http://de.wikipedia.org/wiki/Bresenham-Algorithmus] an.


hui1991 - So 09.12.07 11:41

Danke für die Antworten,

der Bresenham-Algorithmus war genau das was ich gesucht habe. Ich hab den C-Code einfach in Delphi geschrieben und dann war das ding schon fertig =)

Delphi-Quelltext
1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
12:
13:
14:
15:
16:
17:
18:
19:
20:
21:
22:
23:
24:
25:
26:
27:
28:
29:
30:
31:
32:
33:
34:
35:
36:
37:
38:
39:
40:
41:
42:
43:
44:
45:
46:
47:
48:
49:
50:
51:
procedure TMap.line(xstart,ystart,xend,yend: Integer);
var
  x, y, t, dx, dy, incx, incy, pdx, pdy, ddx, ddy, es, el, err: Integer;
begin
  //Entfernung in beiden Dimensionen berechnen
  dx:= xend - xstart;
  dy:= yend - ystart;

  //Vorzeichen des Inkrements bestimmen
  incx := sign(dx);
  incy := sign(dy);
  if dx<0 then dx := -dx;
  if dy<0 then dy := -dy;

  //feststellen, welche Entfernung größer ist
  if dx>dy then begin
    //x ist schnelle Richtung
    pdx:=incx; pdy:=0;      //pd. ist Parallelschritt
    ddx:=incx; ddy:=incy;  //dd. ist Diagonalschritt
    es :=dy;   el :=dy;    //Fehlerschritte schnell, langsam
  end else begin
    //y ist schnelle Richtung
    pdx:=0;    pdy:=incy; //pd. ist Parallelschritt
    ddx:=incx; ddy:=incy; //dd. ist Diagonalschritt
    es :=dx;   el :=dy;   //Fehlerschritte schnell, langsam
  end;

  //Initialisierungen vor Schleifenbeginn
  x  := xstart;
  y  := ystart;
  err:= el div 2;
  SetPixel(x,y);

  //Pixel berechnen
  For t:=0 to el do begin
    //Aktualisierung Fehlerterm
    err := err-es;
    if err<0 then begin
      //Fehlerterm wieder positiv (>=0) machen
      err := err+el;
      //Schritt in langsame Richtung, Diagonalschritt
      x := ddx+x;
      y := ddy+y;
    end else begin
      //Schritt in schnelle Richtung, Parallelschritt
      x := pdx + x;
      y := pdy + y;
    end;
    SetPixel(x,y);
  end;
end;


Funktioniert bei mir ganz schön schnell ^^

MfG
hui1991


OlafSt - Mo 10.12.07 11:55

Bresenham gehört nicht umsonst zu den schnellsten Line-Algo's, die es so gibt.


Reinhard Kern - Mo 10.12.07 15:30

user profile iconhui1991 hat folgendes geschrieben:
Danke für die Antworten,

der Bresenham-Algorithmus war genau das was ich gesucht habe. Ich hab den C-Code einfach in Delphi geschrieben und dann war das ding schon fertig =)
....
MfG
hui1991


Hallo,

dass du den nicht gefunden hast (Grundlage der Grundlage der Grundlage der Computergrafik) heisst aber, dass du gugeln noch ein wenig üben musst.

Gruss Reinhard


hui1991 - Sa 15.12.07 15:14

Hi,

ehrlich gesagt hab ich während meines suchens Bresenham zwar gelesen, aber net verstanden das es zu meinem Problem passt.
Mit Texten komme ich meist eh nie zurecht. ^^
Naja okay.

MfG
hui1991