24小时热门版块排行榜

>论坛更新日志 (3280)
>虫友互识 (848)
>文献求助 (235)
>导师招生 (162)
>休闲灌水 (159)
>考博 (131)
>教师之家 (86)
>博后之家 (81)
>硕博家园 (80)
>找工作 (77)
>论文投稿 (75)
>论文道贺祈福 (67)
>基金申请 (65)
>考研 (57)
>公派出国 (51)
>招聘信息布告栏 (36)

返回列表

当前主题已经存档。

sdlj8051

金虫 (著名写手)

应助: 0 (幼儿园)
贵宾: 0.1
金币: 1149.8
红花: 3
帖子: 2254
在线: 18.1小时
虫号: 71297
注册: 2005-05-30
专业: 电路与系统

[交流] Bresenham高效画线算法

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;
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;

[ Last edited by 幻影无痕 on 2006-11-16 at 07:30 ]

回复此楼

» 猜你喜欢

1楼 2006-08-26 09:41:31

已阅回复此楼关注TA 给TA发消息送TA红花 TA的回帖

相关版块跳转我要订阅楼主 sdlj8051 的主题更新

返回列表