计算机地图制图原理与方法基本图形生成算法PPT学习教案

1、会计学1计算机地图制图原理与方法基本图形生计算机地图制图原理与方法基本图形生成算法成算法第1页/共34页几何图形几何图形i | Pi 最接近图形的象素最接近图形的象素 基本图形的生成算法任务之一就是找出所有的基本图形的生成算法任务之一就是找出所有的i .l点表示为象素（点表示为象素（Pixel），对应于显存地址单），对应于显存地址单元元l读写某一象素是硬件设备提供的最基本功能读写某一象素是硬件设备提供的最基本功能l一维图形，由一个象素宽的直线或曲线表示一维图形，由一个象素宽的直线或曲线表示l二维图形由确定区域的象素表示二维图形由确定区域的象素表示l线图元的扫描转换是基本图形生算法的基础线图元的

2、扫描转换是基本图形生算法的基础；第2页/共34页(X i+1 ,Yi + k)(X i , Int(Yi +0.5)(X i , Yi)栅格交点表示象素点位置栅格交点表示象素点位置第3页/共34页第4页/共34页起点起点终终点点未四舍五入前未四舍五入前最后选定的点最后选定的点1723456089123456780第5页/共34页缺点：缺点：浮点运算、取整浮点运算、取整废时，且不利于硬件实现。废时，且不利于硬件实现。问题：为什么问题：为什么k？，若？，若k，上述算法会出现什么情况？应如何处理？上述算法会出现什么情况？应如何处理？第6页/共34页假定直线斜率假定直线斜率k在在0 01 1之间，当前

3、象素点为之间，当前象素点为（xp,yp），则下一个象素点有，则下一个象素点有两种可选择点两种可选择点P1（xp+1,+1,yp）或）或P2 2（xp+1,+1,yp+1+1）。若）。若P1与与P2的中点（的中点（xp+1,+1,yp+0.5+0.5）称为）称为M，Q为理想直线与为理想直线与x= =xp+1+1垂线的交点。当垂线的交点。当M在在Q的的下方时，则取下方时，则取P2应为下一个象素点；当应为下一个象素点；当M在在Q的上方时，则取的上方时，则取P1为下一为下一个象素点。这就是中点画线法的基本原理个象素点。这就是中点画线法的基本原理过点过点(x0,y0)、(x1, , y1)的直线段的直线

4、段L的方程式为的方程式为F(x, y)=ax+by+c=0，欲判断中点，欲判断中点M在在Q点的点的上方还是下方，只要把上方还是下方，只要把M代入代入F（x，y），），并判断它的符号即可。为此，我们构造判别并判断它的符号即可。为此，我们构造判别式式:d=F(M)=F(xp+1, yp+0.5)=a(xp+1)+b(yp+0.5)+c 当当d0时，时，M在在L(Q点点)上方，取上方，取P1为下一为下一个象素；个象素； 当当d=0时，选时，选P1或或P2均可，约定取均可，约定取P1为下为下一个象素；一个象素；第7页/共34页若当前象素处于若当前象素处于d=d=0 0情况，则取正右方象素情况，则取正右

5、方象素P P1 1( (x xp p+1, y+1, yp p),),要判下一个象要判下一个象素位置，应计算素位置，应计算 d d1 1= =F F( (x xp p+2, +2, y yp p+0.5)=+0.5)=a a( (x xp p+2)+2)+b b( (y yp p+0.5)=+0.5)=d d+ +a a，增量为，增量为a a。 若若d d00时，则取右上方象素时，则取右上方象素P P2 2( (x xp p+1, +1, y yp p+1)+1)。要判断再下一象素，则要。要判断再下一象素，则要计算计算d d2 2= = F F( (x xp p+2, +2, y yp p+1

6、.5)=+1.5)=a a( (x xp p+2)+2)+b b( (y yp p+1.5)+1.5)+c c= =d d+ +a a+ +b b ，增量为，增量为a ab b。画线从画线从( (x x0 0, , y y0 0) )开始，开始，d d的初值的初值 d d0 0= =F F( (x x0 0+1, +1, y y0 0+0.5)=+0.5)=F F( (x x0 0, , y y0 0)+)+a a+0.5+0.5b b，因因 F F( (x x0 0, , y y0 0)=0)=0，所以，所以d d0 0= =a a+0.5+0.5b b。其中，其中，a=ya=y0 0- -

7、y y1 1, , b b= =x x1 1- -x x0 0, , c c= =x x0 0y y1 1- -x x1 1y y0 0。void MidpointLine (int x0void MidpointLine (int x0，int y0int y0，int int x1x1， int y1int y1，int color)int color) int a int a， b b， d1d1， d2d2， d d， x x， y y； a=y0-y1a=y0-y1； b=x1-x0b=x1-x0；d=2d=2* *a+ba+b； d1=2d1=2* *a a；d2=2d2=2* *

8、 (a+b) (a+b)； x=x0 x=x0；y=y0y=y0； while (x=x1)while (x=x1) SetPixel (x SetPixel (x， y y， color);color);if (d0)if (d0) x+ x+；y+y+； d+=d2; d+=d2; elseelse x+ x+； d+=d1;d+=d1; / /* * while while * */ / / /* * midPointLine midPointLine * */ / 第8页/共34页起点起点终点终点初始值：初始值：a=-4; b=7; d= 2*a+b=-1;d1=2*a=-8; d2=

9、2*(a+b)=61、X0=0, Y0=0, d=-12、X1=1, Y1=1, d=53、X2=2, Y2=1, d=-34、X3=3, Y3=2, d=35、X4=4, Y4=2, d=-56、X5=5, Y5=3, d=17、X6=6, Y6=3, d=-7712345612345678008、X6=7, Y6=4, d=-1第9页/共34页第10页/共34页假定直线斜率假定直线斜率,0k1 时时 d=d-1 ;当当d=0.5取取 (x+1,y)，否则取，否则取(x+1,y+1)。令。令e=d-0.5, 显然显然 e 的初值为的初值为-0.5。这样可用。这样可用e的符号来进行判断。的符号

10、来进行判断。dddd第11页/共34页程序如下：第12页/共34页第13页/共34页从速度考虑，还有那些可以改进？第14页/共34页起点起点终点终点初始值：初始值：dx=7; dy=4; k= 4/7 e=-7/141、X0=0, Y0=0, e=1/142、X1=1, Y1=1, e=-5/143、X2=2, Y2=1, e=3/144、X3=3, Y3=2, e=-3/145、X4=4, Y4=2, e=5/146、X5=5, Y5=3, e=-1/147、X6=6, Y6=3, e=7/14712345612345678008、X6=7, Y6=4, e=1/14讨论象素点的选取是否有规

11、律？有何用第15页/共34页第16页/共34页第17页/共34页第18页/共34页第19页/共34页第20页/共34页第21页/共34页MP1P2P（Xp ，Yp ）P为当前点亮象素，那么，下一个点亮的为当前点亮象素，那么，下一个点亮的象素可能是象素可能是P1（Xp+1，Yp）或）或P2（Xp +1，Yp +1)。第22页/共34页第23页/共34页p+3.第24页/共34页第25页/共34页该程序如何改进，提高效率？第26页/共34页第27页/共34页y j第28页/共34页在上半部分在上半部分,法向量的法向量的y分量大分量大在下半部分在下半部分,法向量的法向量的x分量大分量大上半部分上半部分下半部分下半部分法向量法向量两分量相等两分量相等M1M2在当前中点处，法向量（在当前中点处，法向量（ 2b2 (Xp+1) ，2a2 (Yp-0.5)的的y分量比分量比x分分量大量大,即：即： b2 (Xp+1) a2 (Yp-0.5), 而在下一中点，不等式改变方而在下一中点，不等式改变方向，则说明椭圆弧从上部分转入下部分向，则说明椭圆弧从上部分转入下部分第29页/共34页第30页/共34页第31页/共34页第32页/共34页程序：程序：void draw_Ellipe_Mid(int a,int b) int x,y; float d1,d2; x = 0;