Bresenham高效画线算法

　2008-03-08 12:30:44　来源：WEB开发网　闂傚倷绶氬ḿ褍螞閹绢喖绠柨鐕傛嫹

闂傚倷绀侀幉锟犲垂閻㈠灚宕查柟鎵閸庡秵銇勯幒鎴濃偓鐢稿磻閹炬枼妲堟繛鍡楃С濞岊亞绱撻崒姘扁枌闁瑰嚖鎷�

婵犵數濮幏鍐川椤撴繄鎹曢梻渚€娼уú銈吤洪妸鈺佺劦妞ゆ帊鑳堕埊鏇㈡煏閸モ晛浠х紒杈╁仱閺佹捇鏁撻敓锟�闂傚倷绶氬ḿ褍螞閹绢喖绠柨鐕傛嫹　　闂傚倷鑳舵灙缂佺粯顨呴埢宥夊即閵忕姵鐎梺缁樺姇閻忔氨鈧凹鍓熷娲垂椤曞懎鍓伴梺閫炲苯澧紒澶婄秺瀵濡歌閸嬫捇妫冨☉娆忔殘闂佷紮缍€娴滎剟鍩€椤掑倹鏆柛瀣躬瀹曚即寮借閺嗭箓鏌ㄩ悤鍌涘

核心提示：画线的算法不少，但要作到高速、简单并不轻易，Bresenham高效画线算法，斜率相乘法是最简单的方法之一，但计算每个点均要花费不少时间用于乘、除法运算；下面介绍的是Bresenham's高效画线算法，上述程序作了简化，实际程序应略作修正，对每个点的坐标计算只要加、减法就能完成，简化算法用伪Pascal语言描述如

　　画线的算法不少，但要作到高速、简单并不轻易。斜率相乘法是最简单的方法之一，但计算每个点均要花费不少时间用于乘、除法运算；下面介绍的是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)<Abs(DeltaX) then
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;
for i:=0 to DeltaX do
begin
Plot(X, Y);
Inc(x);
ErrorTerm := ErrorTerm + DeltaY;
if ErrorTerm>HalfCount then
begin
ErrorTerm := ErrorTerm - DeltaX;
y := y + Flag;
end;
end;
end
else
begin
if DeltaY<0 then
begin
i := x1; x1 := x2; x2 := i;
i := y1; y1 := y2; y2 := i;
DeltaX := x2 - x1;
DeltaY := y2 - y1;
end;
if DeltaX<0 then Flag := -1
else Flag := 1;
DeltaX := Abs(DeltaX);
HalfCount := DeltaY shr 1;
ErrorTerm := 0;
x := x1;
y := y1;
for i:=0 to DeltaY do
begin
Plot(X, Y);
Inc(y);
ErrorTerm := ErrorTerm + DeltaX;
if ErrorTerm>HalfCount then
begin
ErrorTerm := ErrorTerm - DeltaY;
x := x + Flag;
end;
end;
end;
end;