Parametrisierte Geradengleichung

Da $P_1$ und $P_2$ zwei Punkte auf einer Geraden sind, bietet es sich an, die ganze Linie als Teilstück einer Geraden aufzufassen und durch die Parametrisierung der Geraden mit einem Parameter $r$ die Pixel zu bestimmen.

Gesucht ist der Vektor $\vec{v}$, der von $P_1$ nach $P_2$ führt.

Es gilt

$$\begin{eqnarray*} \vec{p_1} + \vec{v} & = & \vec{p_2} \\ \Leftrightarrow \qqua... ...ft( \begin{array}{c} x_2 - x_1 \\ y_2 - y_1 \end{array} \right) \end{eqnarray*}$$

Die gesamte Gerade $g$ ergibt sich, wenn man von $O$ zu einem Punkt der Geraden geht (z.B. $P_1$) und von dort ein beliebiges Vielfaches des Richtungsvektors $\vec{v}$ abträgt (Punkt-Richtungsform):

$$g: \vec{u} = \vec{p_1} + r \cdot \vec{v} ; r \in \mathbb{R}$$

Die gesuchte Linie $l$ erhält man, wenn man $r$ auf das Intervall $\left [ 0;1 \right ]$ beschränkt:

$$l: \vec{u} = \vec{p_1} + r \cdot \vec{v} ; r \in \left [ 0; 1 \right ]$$

Jetzt muß man nur noch entscheiden, in wievielen Schritten $r$ das Intervall $\left [ 0;1 \right ]$ durchlaufen soll; d.h. wieviele Pixel man ''anschalten'' will, um die ganze Linie zu repräsentieren.

Eine von $P_1$ und $P_2$ unabhänigige Anzahl (z.B. 100 Schritte) würde bei kurzen Linien dazu führen, daß manche Pixel aufgrund der Rundung mehrfach gesetzt würden. Bei langen Linien hingegen wären die Pixel evtl. nicht benachbart.

Sinnvoll wäre es, soviele Pixel zu setzen, wie die Linie Einheiten lang ist. In der euklidischen Ebene ist die Länge $d$ einer Strecke $\overline{P_1P_2}$ als Abstand von Anfangs- und Endpunkt definiert. Die Abstandsberechnung geschieht mit Hilfe der euklidischen Norm (vgl. Pythagoras):

$$d = \Vert\overline{P_1P_2}\Vert = \sqrt{ (x_2 - x_1)^2 + (y_2 - y_1)^2}$$

Hier die draw-Methode der Klasse line.VectorLine. $x_1$, $x_2$, $y_1$ und $y_2$ sind int-Variablen, die bei der Instanziierung der Linie übergeben wurden. D.h. die Linie weiß, wo sie beginnt und wo sie aufhört und kann sich selber zeichnen.

public void draw(CGCanvas cgc) {
  int x, y, dx, dy;
  double r, step;

  dy = y2 - y1;                                // Hoehenzuwachs
  dx = x2 - x1;                                // Schrittweite

  step = 1.0 / Math.sqrt(dx*dx + dy*dy);       // Parameterschritt berechnen
  
  for(r=0.0; r < 1; r+=step) {                 // fuer jeden Parameterwert
    x = (int)(x1 + r*dx +0.5);                 // berechne neue x-Koordinate
    y = (int)(y1 + r*dy +0.5);                 // berechne neue y-Koordinate
    cgc.setPixel(x,y);                         // setze Pixel
  }
  cgc.setPixel(x2, y2);                        // letztes Pixel am Endpunkt
}

Diese Implementation hat den Nachteil, daß sehr viel Gleitkommaarithmetik durchgeführt werden muß. Gleitkommaarithmetik ist (in Java) im Gegensatz zu Integerarithmetik sehr zeitintensiv. Wir werden im Folgenden diesen Nachteil schrittweise beseitigen.