Bresenham高效画线算法

王朝other·作者佚名  2008-06-01
窄屏简体版  字體: |||超大  

画线的算法不少,但要作到高速、简单并不轻易。斜率相乘法是最简单的方法之一,但计算每个点均要花费不少时间用于乘、除法运算;下面介绍的是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;

 
 
 
免责声明:本文为网络用户发布,其观点仅代表作者个人观点,与本站无关,本站仅提供信息存储服务。文中陈述内容未经本站证实,其真实性、完整性、及时性本站不作任何保证或承诺,请读者仅作参考,并请自行核实相关内容。
 
 
© 2005- 王朝網路 版權所有 導航