📄 2.2.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/les222.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></HEAD>
<BODY>
<H3 style="MARGIN-TOP: 0px; MARGIN-BOTTOM: 0px" align=justify><A
name="2.2.2 圆的Bresenham算法"><B><FONT face=楷体_GB2312 size=4>2.2.2
圆的Bresenham算法</FONT></B></A></H3>
<P style="MARGIN-TOP: 0px; MARGIN-BOTTOM: 0px" align=justify><FONT
face=楷体_GB2312> </FONT></P>
<P style="MARGIN-TOP: 0px; MARGIN-BOTTOM: 0px" align=justify><SUP><SPAN
style="LETTER-SPACING: 1px"><FONT face=楷体_GB2312
size=4>设圆之半径为r。先考虑圆心在（0,0），并从x=0,
y=r开始的顺时针方向的1/8圆周的生成过程。在这种情况下，x每步增加1，从x=0开始，到x=y结束。即有：</FONT></SPAN></SUP></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><SUP><SPAN
style="LETTER-SPACING: 1px"><FONT face=楷体_GB2312 size=4>相应的</FONT><FONT
face=楷体_GB2312 size=4>yi+1</FONT><FONT face=楷体_GB2312
size=4>则在两种可能中选择：</FONT></SPAN></SUP></P>
<P style="MARGIN-TOP: 0px; MARGIN-BOTTOM: 0px" align=justify><SUP><SPAN
style="LETTER-SPACING: 1px"><FONT face=楷体_GB2312
size=4>yi+1=yi</FONT></SPAN></SUP><SPAN style="LETTER-SPACING: 1px"><SUP><FONT
face=楷体_GB2312 size=4>，或者</FONT></SUP><SUP><FONT face=楷体_GB2312
size=4>yi+1=yi-1</FONT></SUP></SPAN></P>
<P style="MARGIN-TOP: 0px; MARGIN-BOTTOM: 0px" align=justify><SUP><SPAN
style="LETTER-SPACING: 1px"><FONT face=楷体_GB2312
size=4>选择的原则是考察精确值</FONT></SPAN></SUP><SPAN
style="LETTER-SPACING: 1px"><SUP><FONT face=楷体_GB2312 size=4>y</FONT><FONT
face=楷体_GB2312 size=4>靠近yi还是靠近yi-1（图2.2.2</FONT></SUP></SPAN><SUP><SPAN
style="LETTER-SPACING: 1px"><FONT face=楷体_GB2312
size=4>），计算式为</SPAN></SUP>：</FONT></P>
<BLOCKQUOTE>
<BLOCKQUOTE>
<P style="MARGIN-TOP: 0px; MARGIN-BOTTOM: 0px" align=justify><FONT
face=楷体_GB2312
size=4>y<SUP>2</SUP>=r<SUP>2</SUP>-(x<SUB>i</SUB>+1)</FONT><SUP><FONT
face=楷体_GB2312 size=4>2</FONT></P></SUP>
<P style="MARGIN-TOP: 0px; MARGIN-BOTTOM: 0px" align=justify><FONT
face=楷体_GB2312
size=4>d<SUB>1</SUB>=y<SUB>i</SUB><SUP>2</SUP>-y</FONT><SUP><FONT
face=楷体_GB2312 size=4>2</FONT></P></SUP>
<P style="MARGIN-TOP: 0px; MARGIN-BOTTOM: 0px" align=justify><FONT
face=楷体_GB2312 size=4>
=y<SUB>i</SUB><SUP>2</SUP>-r<SUP>2</SUP>+(x<SUB>i</SUB>+1)</FONT><SUP><FONT
face=楷体_GB2312 size=4>2</FONT></P></SUP>
<P style="MARGIN-TOP: 0px; MARGIN-BOTTOM: 0px" align=justify><FONT
face=楷体_GB2312
size=4>d<SUB>2</SUB>=y<SUP>2</SUP>-(y<SUB>i</SUB>-1)</FONT><SUP><FONT
face=楷体_GB2312 size=4>2</FONT></P></SUP>
<P style="MARGIN-TOP: 0px; MARGIN-BOTTOM: 0px" align=justify><FONT
face=楷体_GB2312 size=4>
=r<SUP>2</SUP>-(x<SUB>i</SUB>+1)<SUP>2</SUP>-(y<SUB>i</SUB>-1)<SUP>2</SUP></FONT></P></BLOCKQUOTE></BLOCKQUOTE>
<P style="MARGIN-TOP: 0px; MARGIN-BOTTOM: 0px" align=center><FONT
face=楷体_GB2312><IMG height=284 alt="2_2_2.gif (3311 bytes)"
src="2.2.2 圆的Bresenham算法.files/2_2_2.gif" width=317></FONT></P>
<P style="MARGIN-TOP: 0px; MARGIN-BOTTOM: 0px" align=center><FONT
face=楷体_GB2312>图2.2.2 y的位置</FONT></P><FONT face=宋体>
<P style="MARGIN-TOP: 0px; MARGIN-BOTTOM: 0px" align=justify> </P></FONT>
<P style="MARGIN-TOP: 0px; MARGIN-BOTTOM: 0px" align=justify><SUP><SPAN
style="LETTER-SPACING: 1px"><FONT face=楷体_GB2312 size=4>令pi=d1-d2，并代入d1,
d2，则有</FONT></SPAN></SUP></P>
<BLOCKQUOTE>
<P style="MARGIN-TOP: 0px; MARGIN-BOTTOM: 0px" align=justify><SUP><SPAN
style="LETTER-SPACING: 1px"><FONT face=楷体_GB2312
size=4>pi=2(xi+1)2+yi2+(yi-1)2-2r2 (2.2.1)</FONT></SPAN></SUP></P></BLOCKQUOTE>
<P style="MARGIN-TOP: 0px; MARGIN-BOTTOM: 0px" align=justify><SUP><SPAN
style="LETTER-SPACING: 1px"><FONT face=楷体_GB2312
size=4>pi称为误差。如果pi<0则yi+1=yi，否则yi+1=yi-1。pi的递归式为：</FONT></SPAN></SUP></P>
<BLOCKQUOTE>
<P style="MARGIN-TOP: 0px; MARGIN-BOTTOM: 0px" align=justify><SUP><SPAN
style="LETTER-SPACING: 1px"><FONT face=楷体_GB2312
size=4>pi+1=pi+4xi+6+2(yi2+1-yi2)-2(yi+1-yi)
(2.2.2)</FONT></SPAN></SUP></P></BLOCKQUOTE>
<P style="MARGIN-TOP: 0px; MARGIN-BOTTOM: 0px" align=justify><SUP><SPAN
style="LETTER-SPACING: 1px"><FONT face=楷体_GB2312 size=4>pi的初值由式（2.6）代入xi=0,
yi=r而得</FONT></SPAN></SUP></P>
<P style="MARGIN-TOP: 0px; MARGIN-BOTTOM: 0px" align=justify><SUP><SPAN
style="LETTER-SPACING: 1px"><FONT face=楷体_GB2312
size=4> p1=3-2r
(2.2.3)</FONT></SPAN></SUP></P>
<P style="MARGIN-TOP: 0px; MARGIN-BOTTOM: 0px" align=justify><SUP><SPAN
style="LETTER-SPACING: 1px"><FONT face=楷体_GB2312
size=4>根据上面的推导，圆周生成算法思想为：</FONT></SPAN></SUP></P>
<P style="MARGIN-TOP: 0px; MARGIN-BOTTOM: 0px" align=justify><SUP><SPAN
style="LETTER-SPACING: 1px"><FONT face=楷体_GB2312 size=4>1、求误差初值，p1=3-2r;
i=1；画点(0, r)；</FONT></SPAN></SUP></P><FONT face=System>
<P style="MARGIN-TOP: 0px; MARGIN-BOTTOM: 0px" align=justify> </P></FONT>
<P style="MARGIN-TOP: 0px; MARGIN-BOTTOM: 0px" align=justify><SUP><SPAN
style="LETTER-SPACING: 1px"><FONT face=楷体_GB2312
size=4>2、求下一个光栅位置：</FONT></SPAN></SUP></P>
<P style="MARGIN-TOP: 0px; MARGIN-BOTTOM: 0px" align=justify><SUP><SPAN
style="LETTER-SPACING: 1px"><FONT face=楷体_GB2312
size=4>xi+1=xi+1；</FONT></SPAN></SUP></P>
<P style="MARGIN-TOP: 0px; MARGIN-BOTTOM: 0px" align=justify><SUP><SPAN
style="LETTER-SPACING: 1px"><FONT face=楷体_GB2312 size=4>if pi<0
则yi+1=yi；</FONT></SPAN></SUP></P>
<P style="MARGIN-TOP: 0px; MARGIN-BOTTOM: 0px" align=justify><SUP><SPAN
style="LETTER-SPACING: 1px"><FONT face=楷体_GB2312
size=4>否则yi+1=yi-1；</FONT></SPAN></SUP></P><FONT face=System>
<P style="MARGIN-TOP: 0px; MARGIN-BOTTOM: 0px" align=justify> </P></FONT>
<P style="MARGIN-TOP: 0px; MARGIN-BOTTOM: 0px" align=justify><SUP><SPAN
style="LETTER-SPACING: 1px"><FONT face=楷体_GB2312 size=4>3、画点（xi+1,
yi+1）</FONT></SPAN></SUP></P><FONT face=System>
<P style="MARGIN-TOP: 0px; MARGIN-BOTTOM: 0px" align=justify> </P></FONT>
<P style="MARGIN-TOP: 0px; MARGIN-BOTTOM: 0px" align=justify><SUP><SPAN
style="LETTER-SPACING: 1px"><FONT face=楷体_GB2312
size=4>4、计算下一个误差：</FONT></SPAN></SUP></P>
<P style="MARGIN-TOP: 0px; MARGIN-BOTTOM: 0px" align=justify><SUP><SPAN
style="LETTER-SPACING: 1px"><FONT face=楷体_GB2312 size=4>if pi<0
则pi+1=pi+4xi+6；</FONT></SPAN></SUP></P>
<P style="MARGIN-TOP: 0px; MARGIN-BOTTOM: 0px" align=justify><SUP><SPAN
style="LETTER-SPACING: 1px"><FONT face=楷体_GB2312 size=4>否则
pi+1=pi+4(xi-yi)+10；</FONT></SPAN></SUP></P>
<P style="MARGIN-TOP: 0px; MARGIN-BOTTOM: 0px" align=justify><SUP><SPAN
style="LETTER-SPACING: 1px"><FONT face=楷体_GB2312 size=4>5、i=i+1; if
x=y则end；否则返2。</FONT></SPAN></SUP></P><FONT face=宋体>
<P style="MARGIN-TOP: 0px; MARGIN-BOTTOM: 0px" align=justify> </P></FONT>
<P style="MARGIN-TOP: 0px; MARGIN-BOTTOM: 0px" align=justify><SUP><SPAN
style="LETTER-SPACING: 1px"><FONT face=楷体_GB2312
size=4>虽然式（2.2.2）式表示pi+1的算法似乎很复杂，但因为yi+1只能取值yi或yi-1，因此在算法中，第4步的算式变得很简单，只须作加法和4的乘法。因此圆的Bresenham算法运行速度也是很快的，并适宜于硬件实现。</FONT></SPAN></SUP></P>
<P style="MARGIN-TOP: 0px; MARGIN-BOTTOM: 0px" align=justify><SUP><SPAN
style="LETTER-SPACING: 1px"><FONT face=楷体_GB2312
size=4>圆的Bresenham算法的程序实现见程序2.2.1。</FONT></SPAN></SUP></P>
<BLOCKQUOTE>
<BLOCKQUOTE>
<BLOCKQUOTE>
<P style="MARGIN-TOP: 0px; MARGIN-BOTTOM: 0px" align=justify><FONT
face=Arial>circle (xc, yc, radius, c)</FONT></P>
<P style="MARGIN-TOP: 0px; MARGIN-BOTTOM: 0px" align=justify><FONT
face=Arial>int xc, yc, radius, 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 x, y, p;</FONT></P>
<P style="MARGIN-TOP: 0px; MARGIN-BOTTOM: 0px" align=justify><FONT
face=Arial>x=0;</FONT></P>
<P style="MARGIN-TOP: 0px; MARGIN-BOTTOM: 0px" align=justify><FONT
face=Arial>y=radius;</FONT></P>
<P style="MARGIN-TOP: 0px; MARGIN-BOTTOM: 0px" align=justify><FONT
face=Arial>p=3-2*radius;</FONT></P>
<P style="MARGIN-TOP: 0px; MARGIN-BOTTOM: 0px" align=justify><FONT
face=Arial>while (x<y){</FONT></P>
<P style="MARGIN-TOP: 0px; MARGIN-BOTTOM: 0px" align=justify><FONT
face=Arial>
plot_circle_points(xc, yc, x, y, c);</FONT></P>
<P style="MARGIN-TOP: 0px; MARGIN-BOTTOM: 0px" align=justify><FONT
face=Arial> if (p<0)
p=p+4*x+6;</FONT></P>
<P style="MARGIN-TOP: 0px; MARGIN-BOTTOM: 0px" align=justify><FONT
face=Arial> else{</FONT></P>
<P style="MARGIN-TOP: 0px; MARGIN-BOTTOM: 0px" align=justify><FONT
face=Arial>
p=p+4*(x-y)+10;</FONT></P>
<P style="MARGIN-TOP: 0px; MARGIN-BOTTOM: 0px" align=justify><FONT
face=Arial>
y-=1;</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> x+=1;</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>if (x= =y)</FONT></P>
<P style="MARGIN-TOP: 0px; MARGIN-BOTTOM: 0px" align=justify><FONT
face=Arial>
plot_circle_points(xc, yc, x, y, 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> </P>
<P style="MARGIN-TOP: 0px; MARGIN-BOTTOM: 0px" align=justify><FONT
face=Arial>plot_circle_points(xc, yc, x, y, c)</FONT></P>
<P style="MARGIN-TOP: 0px; MARGIN-BOTTOM: 0px" align=justify><FONT
face=Arial>int xc, yc, x, y, c;</FONT></P>
<P style="MARGIN-TOP: 0px; MARGIN-BOTTOM: 0px" align=justify><FONT
face=Arial>{</FONT></P>
<BLOCKQUOTE>
<P style="MARGIN-TOP: 0px; MARGIN-BOTTOM: 0px" align=justify><FONT
face=Arial>set_pixel(xc+x, yc+y, c);</FONT></P>
<P style="MARGIN-TOP: 0px; MARGIN-BOTTOM: 0px" align=justify><FONT
face=Arial>set_pixel(xc+x, yc+y, c);</FONT></P>
<P style="MARGIN-TOP: 0px; MARGIN-BOTTOM: 0px" align=justify><FONT
face=Arial>set_pixel(xc+x, yc-y, c);</FONT></P>
<P style="MARGIN-TOP: 0px; MARGIN-BOTTOM: 0px" align=justify><FONT
face=Arial>set_pixel(xc-x, yc-y, c);</FONT></P>
<P style="MARGIN-TOP: 0px; MARGIN-BOTTOM: 0px" align=justify><FONT
face=Arial>set_pixel(xc+y, yc+x, c);</FONT></P>
<P style="MARGIN-TOP: 0px; MARGIN-BOTTOM: 0px" align=justify><FONT
face=Arial>set_pixel(xc-y, yc+x, c);</FONT></P>
<P style="MARGIN-TOP: 0px; MARGIN-BOTTOM: 0px" align=justify><FONT
face=Arial>set_pixel(xc+y, yc-x, c);</FONT></P>
<P style="MARGIN-TOP: 0px; MARGIN-BOTTOM: 0px" align=justify><FONT
face=Arial>set_pixel(xc-y, yc-x, c);</FONT></P></BLOCKQUOTE>
<P style="MARGIN-TOP: 0px; MARGIN-BOTTOM: 0px" align=justify><FONT
face=Arial>}</FONT><FONT face=宋体></P>
<P style="MARGIN-TOP: 0px; MARGIN-BOTTOM: 0px" align=justify></FONT> </P>
<P style="MARGIN-TOP: 0px; MARGIN-BOTTOM: 0px" align=justify>程序<FONT
face=Arial>2.2.1
Bresenham</FONT>的圆生成算法</P></BLOCKQUOTE></BLOCKQUOTE></BLOCKQUOTE>
<P><A href="http://www.ekany.com/wdg98/cg/contents/chapter2/les221.htm"><FONT
face=楷体_GB2312><上一节〉</FONT></A><FONT face=楷体_GB2312> <A
href="http://www.ekany.com/wdg98/cg/contents/chapter2/les231.htm">〈下一节〉</A>
<A
href="http://www.ekany.com/wdg98/cg/tutorial/chapter2/lesson2-2.htm">〈返回〉</A></FONT></P></BODY></HTML>
⌨️ 快捷键说明
复制代码
Ctrl + C
搜索代码
Ctrl + F
全屏模式
F11
切换主题
Ctrl + Shift + D
显示快捷键
?
增大字号
Ctrl + =
减小字号
Ctrl + -