📄 2.1.2 直线的bresenham算法.htm
字号:
<!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 4.0 Transitional//EN">
<!-- saved from url=(0058)http://www.ekany.com/wdg98/cg/contents/chapter2/les212.htm -->
<HTML><HEAD><TITLE>2</TITLE>
<META http-equiv=Content-Type content="text/html; charset=gb2312">
<META content="MSHTML 6.00.2800.1106" name=GENERATOR>
<META http-equiv=Page-Enter
content=revealTrans(Duration=1.0,Transition=0)></HEAD>
<BODY>
<H3 align=justify><A name="2.1.2 直线的Bresenham算法"><B><FONT face=楷体_GB2312
size=4>2.1.2 直线的Bresenham算法</FONT></B></A></H3>
<P style="MARGIN-TOP: 0px; MARGIN-BOTTOM: 0px" align=justify><FONT
size=4><SUP><SPAN style="LETTER-SPACING: 1px"><FONT
face=楷体_GB2312>本算法由Bresenham在1965年提出。设直线从起点（x1, y1）到终点（x2,
y2）。直线可表示为方程y=mx+b。其中</FONT></SPAN></SUP></FONT></P>
<P style="MARGIN-TOP: 0px; MARGIN-BOTTOM: 0px" align=justify><FONT size=4><SPAN
style="LETTER-SPACING: 1px"><FONT face=楷体_GB2312><SUP>b = y1 - m *
x1, </SUP></FONT></SPAN></FONT></P>
<P style="MARGIN-TOP: 0px; MARGIN-BOTTOM: 0px" align=justify><FONT face=Arial
size=4><SPAN style="LETTER-SPACING: 1px"><SUP>m = </SUP></SPAN><IMG height=45
src="2.1.2 直线的Bresenham算法.files/Image84.gif" width=89></FONT></P>
<P style="MARGIN-TOP: 0px; MARGIN-BOTTOM: 0px" align=justify><SUP><SPAN
style="LETTER-SPACING: 1px"><FONT face=楷体_GB2312
size=4>我们的讨论先将直线方向限于1a象限（图2.1.1）在这种情况下，当直线光栅化时，x每次都增加1个单元，即</FONT></SPAN></SUP></P>
<P style="MARGIN-TOP: 0px; MARGIN-BOTTOM: 0px" align=justify><SPAN
style="LETTER-SPACING: 1px"><FONT face=Arial
size=4><SUP>xi+1=xi+1</SUP></FONT></SPAN></P>
<P style="MARGIN-TOP: 0px; MARGIN-BOTTOM: 0px" align=justify><SUP><SPAN
style="LETTER-SPACING: 1px"><FONT face=楷体_GB2312
size=4>而y的相应增加应当小于1。为了光栅化，yi+1只可能选择如下两种位置之一（图2.1.2）。</FONT></SPAN></SUP></P>
<P style="MARGIN-TOP: 0px; MARGIN-BOTTOM: 0px" align=center><FONT face=楷体_GB2312
size=4><IMG height=157 alt="2_1_2.gif (2562 bytes)"
src="2.1.2 直线的Bresenham算法.files/2_1_2.gif" width=203></FONT><FONT
face=System></P>
<P style="MARGIN-TOP: 0px; MARGIN-BOTTOM: 0px" align=center></FONT><FONT
face=楷体_GB2312 size=4>图2.1.2</FONT></P>
<P style="MARGIN-TOP: 0px; MARGIN-BOTTOM: 0px" align=justify><FONT
face=楷体_GB2312 size=4> </FONT></P>
<P style="MARGIN-TOP: 0px; MARGIN-BOTTOM: 0px" align=justify><SPAN
style="LETTER-SPACING: 1px"><SUP><FONT face=楷体_GB2312 size=4>图2.1.2
yi+1的位置选择yi-1=yi 或者 yi+1=yi+1</FONT></SUP></SPAN></P>
<P style="MARGIN-TOP: 0px; MARGIN-BOTTOM: 0px" align=justify></P>
<P style="MARGIN-TOP: 0px; MARGIN-BOTTOM: 0px" align=justify><SPAN
style="LETTER-SPACING: 1px"><SUP><FONT face=楷体_GB2312
size=4>选择的原则是看精确值y与yi及yi+1的距离d1及d2的大小而定。计算式为：</FONT></SUP></SPAN></P>
<BLOCKQUOTE>
<BLOCKQUOTE>
<P style="MARGIN-TOP: 0px; MARGIN-BOTTOM: 0px" align=justify><SPAN
style="LETTER-SPACING: 1px"><FONT face=Arial size=4><SUP>y=m(xi+1)+b
(2.1.1)</SUP></FONT></SPAN></P>
<P style="MARGIN-TOP: 0px; MARGIN-BOTTOM: 0px" align=justify><SPAN
style="LETTER-SPACING: 1px"><FONT face=Arial size=4><SUP>d1=y-yi
(2.1.2)</SUP></FONT></SPAN></P>
<P style="MARGIN-TOP: 0px; MARGIN-BOTTOM: 0px" align=justify><SPAN
style="LETTER-SPACING: 1px"><FONT face=Arial size=4><SUP>d2=yi+1-y
(2.1.3)</SUP></FONT></SPAN></P></BLOCKQUOTE></BLOCKQUOTE>
<P style="MARGIN-TOP: 0px; MARGIN-BOTTOM: 0px" align=justify><SPAN
style="LETTER-SPACING: 1px"><SUP><FONT face=楷体_GB2312
size=4>如果d1-d2>0，则yi+1=yi+1，否则yi+1=yi。因此算法的关键在于简便地求出d1-d2的符号。将式（2.1.1）、（2.1.2）、（2.1.3）代入d1-d2，得</FONT></SUP></SPAN></P>
<P style="MARGIN-TOP: 0px; MARGIN-BOTTOM: 0px" align=justify><SPAN
style="LETTER-SPACING: 1px"><FONT face=Arial size=4><SUP>d1-d2=2y-2yi-1=2<IMG
height=41 src="2.1.2 直线的Bresenham算法.files/Image85.gif"
width=22>(xi+1)-2yi+2b-1</SUP></FONT></SPAN></P>
<P style="MARGIN: 1px 0px; TEXT-INDENT: 0px; LINE-HEIGHT: 150%"
align=justify><SPAN style="LETTER-SPACING: 1px"><SUP><FONT face=楷体_GB2312
size=4>用dx乘等式两边，并以Pi=dx(d1-d2)代入上述等式，得</FONT></SUP></SPAN></P>
<P style="MARGIN: 1px 0px; TEXT-INDENT: 0px; LINE-HEIGHT: 150%"
align=justify><SPAN style="LETTER-SPACING: 1px"><FONT face=Arial
size=4><SUP>Pi=2xidy-2yidx+2dy+dx(2b-1) (2.1.4)</SUP></FONT></SPAN></P>
<P style="MARGIN: 1px 0px; TEXT-INDENT: 0px; LINE-HEIGHT: 150%"
align=justify><SPAN style="LETTER-SPACING: 1px"><SUP><FONT face=楷体_GB2312
size=4>d1-d2是我们用以判断符号的误差。由于在1a象限，dx总大于0，所以Pi仍旧可以用作判断符号的误差。Pi-1为：</FONT></SUP></SPAN></P>
<P style="MARGIN-TOP: 0px; MARGIN-BOTTOM: 0px" align=justify><SPAN
style="LETTER-SPACING: 1px"><FONT face=Arial
size=4><SUP>Pi+1=Pi+2dy-2dx(yi+1-yi) (2.1.5)</SUP></FONT></SPAN></P>
<P style="MARGIN-TOP: 0px; MARGIN-BOTTOM: 0px" align=justify><SPAN
style="LETTER-SPACING: 1px"><SUP><FONT face=楷体_GB2312 size=4>误差的初值P1，可将x1,
y1，和b代入式（2.1.4）中的xi, yi而得到：</FONT></SUP></SPAN></P>
<P style="MARGIN-TOP: 0px; MARGIN-BOTTOM: 0px" align=justify><SPAN
style="LETTER-SPACING: 1px"><FONT face=Arial
size=4><SUP>P1=2dy-dx</SUP></FONT></SPAN></P>
<P style="MARGIN-TOP: 0px; MARGIN-BOTTOM: 0px" align=justify><SPAN
style="LETTER-SPACING: 1px"><SUP><FONT face=楷体_GB2312
size=4>综述上面的推导，第1a象限内的直线Bresenham算法思想如下：</FONT></SUP></SPAN></P>
<P style="MARGIN-TOP: 0px; MARGIN-BOTTOM: 0px" align=justify> </P>
<BLOCKQUOTE>
<P style="MARGIN-TOP: 0px; MARGIN-BOTTOM: 0px" align=justify><SPAN
style="LETTER-SPACING: 1px"><SUP><FONT face=楷体_GB2312 size=4>1、画点(x1, y2);
dx=x2-x1; dy=y2-y1；</FONT></SUP></SPAN></P>
<P style="MARGIN-TOP: 0px; MARGIN-BOTTOM: 0px" align=justify><SPAN
style="LETTER-SPACING: 1px"><SUP><FONT face=楷体_GB2312 size=4>计算误差初值P1=2dy-dx;
i=1；</FONT></SUP></SPAN></P>
<P style="MARGIN-TOP: 0px; MARGIN-BOTTOM: 0px" align=justify><SPAN
style="LETTER-SPACING: 1px"><SUP><FONT face=楷体_GB2312
size=4>2、求直线的下一点位置：</FONT></SUP></SPAN></P>
<P style="MARGIN-TOP: 0px; MARGIN-BOTTOM: 0px" align=justify><SPAN
style="LETTER-SPACING: 1px"><SUP><FONT face=楷体_GB2312
size=4>xi+1=xi+1；</FONT></SUP></SPAN></P>
<P style="MARGIN-TOP: 0px; MARGIN-BOTTOM: 0px" align=justify><SPAN
style="LETTER-SPACING: 1px"><SUP><FONT face=楷体_GB2312 size=4>if Pi>0
则yi+1=yi+1；</FONT></SUP></SPAN></P>
<P style="MARGIN-TOP: 0px; MARGIN-BOTTOM: 0px" align=justify><SPAN
style="LETTER-SPACING: 1px"><SUP><FONT face=楷体_GB2312
size=4>否则yi+1=yi；</FONT></SUP></SPAN></P>
<P style="MARGIN-TOP: 0px; MARGIN-BOTTOM: 0px" align=justify><SPAN
style="LETTER-SPACING: 1px"><SUP><FONT face=楷体_GB2312 size=4>3、画点（xi+1,
yi-1）；</FONT></SUP></SPAN></P>
<P style="MARGIN-TOP: 0px; MARGIN-BOTTOM: 0px" align=justify><SPAN
style="LETTER-SPACING: 1px"><SUP><FONT face=楷体_GB2312
size=4>4、求下一个误差Pi+1；</FONT></SUP></SPAN></P>
<P style="MARGIN-TOP: 0px; MARGIN-BOTTOM: 0px" align=justify><SPAN
style="LETTER-SPACING: 1px"><SUP><FONT face=楷体_GB2312 size=4>if Pi>0
则Pi+1=Pi+2dy-2dx;</FONT></SUP></SPAN></P>
<P style="MARGIN-TOP: 0px; MARGIN-BOTTOM: 0px" align=justify><SPAN
style="LETTER-SPACING: 1px"><SUP><FONT face=楷体_GB2312
size=4>否则Pi+1=Pi+2dy；</FONT></SUP></SPAN></P>
<P style="MARGIN-TOP: 0px; MARGIN-BOTTOM: 0px" align=justify><SPAN
style="LETTER-SPACING: 1px"><SUP><FONT face=楷体_GB2312 size=4>5、i=i+1; if
i<dx+1则转2；否则end。</FONT></SUP></SPAN></P></BLOCKQUOTE>
<P style="MARGIN-TOP: 0px; MARGIN-BOTTOM: 0px" align=justify><SPAN
style="LETTER-SPACING: 1px"><SUP><FONT face=楷体_GB2312
size=4>Bresenham算法的优点是：</FONT></SUP></SPAN></P>
<P style="MARGIN-TOP: 0px; MARGIN-BOTTOM: 0px" align=justify><SPAN
style="LETTER-SPACING: 1px"><SUP><FONT face=楷体_GB2312
size=4>1、不必计算直线之斜率，因此不做除法；</FONT></SUP></SPAN></P>
<P style="MARGIN-TOP: 0px; MARGIN-BOTTOM: 0px" align=justify><SPAN
style="LETTER-SPACING: 1px"><SUP><FONT face=楷体_GB2312
size=4>2、不用浮点数，只用整数；</FONT></SUP></SPAN></P>
<P style="MARGIN-TOP: 0px; MARGIN-BOTTOM: 0px" align=justify><SPAN
style="LETTER-SPACING: 1px"><SUP><FONT face=楷体_GB2312
size=4>3、只做整数加减法和乘2运算，而乘2运算可以用硬件移位实现。</FONT></SUP></SPAN></P>
<P style="MARGIN-TOP: 0px; MARGIN-BOTTOM: 0px" align=justify><SPAN
style="LETTER-SPACING: 1px"><SUP><FONT face=楷体_GB2312
size=4>Bresenham算法速度很快，并适于用硬件实现。</FONT></SUP></SPAN></P>
<P style="MARGIN-TOP: 0px; MARGIN-BOTTOM: 0px" align=justify> </P>
<P style="MARGIN-TOP: 0px; MARGIN-BOTTOM: 0px" align=justify><SPAN
style="LETTER-SPACING: 1px"><SUP><FONT face=楷体_GB2312 size=4>
由上述算法思想编制的程序如程序2.1.2。这个程序适用于所有8个方向的直线（图2.1.1）的生成。程序用色彩C画出一条端点为（x1, y1）和（x2,
y2）的直线。其中变量的含义是：P是误差；const1和const2，是误差的逐点变化量；inc是y的单位递变量，值为1或-1；tmp是用作象限变换时的临时变量。程序以判断|dx|>|dy|为分支，并分别将2a,
3a象限的直线和3b, 4b象限的直线变换到1a, 4a和2b, 1b方向去，以求得程序处理的简洁。</FONT></SUP></SPAN></P>
<BLOCKQUOTE>
<BLOCKQUOTE>
<BLOCKQUOTE>
<P style="MARGIN-TOP: 0px; MARGIN-BOTTOM: 0px" align=justify><FONT
face=Arial>void line (x1, y1, x2, y2, c)</FONT></P>
<P style="MARGIN-TOP: 0px; MARGIN-BOTTOM: 0px" align=justify><FONT
face=Arial>int x1, y1, x2, y2, c;</FONT></P>
<P style="MARGIN-TOP: 0px; MARGIN-BOTTOM: 0px" align=justify><FONT
face=Arial>{</FONT></P>
<P style="MARGIN-TOP: 0px; MARGIN-BOTTOM: 0px" align=justify><FONT
face=Arial>int dx;</FONT></P>
<P style="MARGIN-TOP: 0px; MARGIN-BOTTOM: 0px" align=justify><FONT
face=Arial>int dy;</FONT></P>
<P style="MARGIN-TOP: 0px; MARGIN-BOTTOM: 0px" align=justify><FONT
face=Arial>int x;</FONT></P>
<P style="MARGIN-TOP: 0px; MARGIN-BOTTOM: 0px" align=justify><FONT
face=Arial>int y;</FONT></P>
<P style="MARGIN-TOP: 0px; MARGIN-BOTTOM: 0px" align=justify><FONT
face=Arial>int p;</FONT></P>
<P style="MARGIN-TOP: 0px; MARGIN-BOTTOM: 0px" align=justify><FONT
face=Arial>int const1;</FONT></P>
<P style="MARGIN-TOP: 0px; MARGIN-BOTTOM: 0px" align=justify><FONT
face=Arial>int const2;</FONT></P>
<P style="MARGIN-TOP: 0px; MARGIN-BOTTOM: 0px" align=justify><FONT
face=Arial>int inc;</FONT></P>
<P style="MARGIN-TOP: 0px; MARGIN-BOTTOM: 0px" align=justify><FONT
face=Arial>int tmp;</FONT></P>
<P style="MARGIN-TOP: 0px; MARGIN-BOTTOM: 0px" align=justify><FONT
face=Arial>dx=x2-x1;</FONT></P>
⌨️ 快捷键说明
复制代码
Ctrl + C
搜索代码
Ctrl + F
全屏模式
F11
切换主题
Ctrl + Shift + D
显示快捷键
?
增大字号
Ctrl + =
减小字号
Ctrl + -