Bresenham高效畫線算法

畫線的算法不少，但要作到高速、簡單并不容易。斜率相乘法是最簡單的方法之一，但計算每個點均要花費不少時間用于乘、除法運算；下面介紹的是Bresenham's高效畫線算法，對每個點的坐標計算只要加、減法就能完成。
    簡化算法用偽Pascal語言描述如下：
    procedure DrawLine(x1, y1, x2, y2: Integer);
    var
    x, y, DeltaX, DeltaY, HalfX, ErrorTerm, i: Integer;
    begin
    DeltaX := x2 - x1;
    DeltaY := y2 - y1;
    HalfX := (x2 - x1) shr 1;
    ErrorTerm := 0;
    x := x1;
    y := y1;
    for i:=0 to DeltaX do
    begin
    Plot(X, Y);
    Inc(x);
    ErrorTerm := ErrorTerm + DeltaY;
    if ErrorTerm>HalfX then
    begin
    ErrorTerm := ErrorTerm - DeltaX;
    Inc(y);
    end;
    end;
    end;
    為方便閱讀，上述程序作了簡化。實際程序應略作修正，以分別處理DeltaX與DeltaY比較大小, 必要時交換起始、結束點等。
    修正后的的偽Pascal算法如下：
    procedure DrawLine(x1, y1, x2, y2: Integer);
    var
    x, y, DeltaX, DeltaY, HalfCount, ErrorTerm, i, Flag: Integer;
    begin
    DeltaX := x2 - x1;
    DeltaY := y2 - y1;
    if Abs(DeltaY)　　begin
    if DeltaX<0 then
    begin
    i := x1; x1 := x2; x2 := i;
    i := y1; y1 := y2; y2 := i;
    DeltaX := x2 - x1;
    DeltaY := y2 - y1;
    end;
    if DeltaY<0 then Flag := -1
    else Flag := 1;
    DeltaY := Abs(DeltaY);
    HalfCount := DeltaX shr 1;
    ErrorTerm := 0;
    x := x1;
    y := y1;