用中点算法扫描转换直线段

电信001 李理 0052011 一．算法 教材里已有现成的算法，只要把其中的算法修改一下就行了。

应该修改的第一点是：在教材中，是根据平时的习惯将左下角左为坐标原点，而在PC机中左上角为坐标原点。因此在实际程序中，计算(x,y)时仍照教材，只是将putpixel(x,y,color) 必成putpixel(x,HEIGHT-y,color)就行了，其中变量HEIGHT为屏幕的最大分辨率，可用C系统提供的getmaxy 函数得到，它的原型为：int far getmaxy(void); 第二个问题是关于怎么按斜率的来分类。我在这里将它分为了6类： 即斜率为（0，∞），（0，1），（1,+∞），（-1,0），（-∞，-1）。将0和∞单独处理是因为这样速度会快一点（也许感觉不到）。斜率的判断，最初的考虑是用(y1-y0)/(x1-x0)，但因为在定义时这些变量都是整型，所以不能正确判断。另外考虑到教材的算法是假定起点的横坐标小于终点的横坐标的，所以在一开始就将横坐标小的作为起点。（换序来实现）这样，只要y1>y0就说明斜率大于0，而再加上(y1-y0)<(x1=x0)这个条件就说明它满足教材算法的条件了。 下面要解决的问题是斜率在（1，+∞）的算法了。

我们选y轴为计长方向（每次加一），可推出：

xi+1,r=xi,r, 当di< 0 xi+1,r=xi,r+1，当di>=0

di+1=di+2Δx, di< 0 di+1=di+2(Δx+Δy), di>=0

最后的问题就是斜率为（-1，0）和（-∞，-1）的情况。

当然也可以另写类似的算法，不过我们可以利用已有的（0，1）的算法和（1，+∞）的算法，只要作一个变换：将（x1,y1）作直线y=y0的对称点，即用（x0,y0）,(x1,2*y0-y1) 这两点满足第一种条件，在画点时只要再用（2*y0-y）代替y就行了。程序流程图见末页。

二．程序清单：

/********************************************************************** This is a program of drawing a line by middle point algorithm (Bresenham algorithm). CopyRights 2002 By LiLi.

**********************************************************************/ #include \"graphics.h\" int HEIGHT; main()

{ int x0,x1,y0,y1;int color;

void midpointline(int x0,int y0,int x1,int y1,int color); printf(\"Please the x coordinate of the first point.\\n\"); scanf(\"%d\

printf(\"The y coordinate of the first point please.\\n\"); scanf(\"%d\

printf(\"The x coordinate of the second point.\\n\"); scanf(\"%d\

printf(\"The y coordinate of the second point.\\n\"); scanf(\"%d\

printf(\"The Color of the Line :\\n\"); scanf(\"%d\

midpointline(x0,y0,x1,y1,color); }

void midpointline(int x0,int y0,int x1,int y1,int color) { int i;int temp;

int gdriver=DETECT,gmode; void line1(int,int,int,int,int); void line2(int,int,int,int,int); void line3(int,int,int,int,int); void line4(int,int,int,int,int); if(x0>x1)

{temp=x0;x0=x1;x1=temp;temp=y0;y0=y1;y1=temp;} initgraph(&gdriver,&gmode,\"\"); HEIGHT=getmaxy();

if(y0==y1) /*It's a horizontal line. */

for(i=x0;i<=x1;i++)putpixel(i,HEIGHT-y0,color); else if(x0==x1) /*It's a vertical line. */ if(y0y0&&y1-y0<=x1-x0) line1(x0,y0,x1,y1,color); else if(y1>y0&&y1-y0>x1-x0) line2(x0,y0,x1,y1,color); else if(y0-y1line3(x0,y0,x1,y1,color); else

line4(x0,y0,x1,y1,color); getch();

closegraph(); }

void line1(int x0,int y0,int x1,int y1,int color) { int dx,dy,incrE,incrNE,d,x,y;

dx=x1-x0; dy=y1-y0; d=dx-2*dy; incrE=-2*dy; incrNE=2*(dx-dy); x=x0;y=y0;

putpixel(x,HEIGHT-y,color); while(x0) d+=incrE; else

{d+=incrNE; y++; } x++;

putpixel(x,HEIGHT-y,color); } }

void line2(int x0,int y0,int x1,int y1,int color) { int dx,dy,incrE,incrNE,d,x,y;

dx=x1-x0; dy=y1-y0; d=2*dx-dy; incrE=2*dx; incrNE=2*(dx-dy); x=x0;y=y0;

putpixel(x,HEIGHT-y,color); while(y{d+=incrNE; x++; } y++;

putpixel(x,HEIGHT-y,color); } }

void line3(int x0,int y0,int x1,int y1,int color) { int dx,dy,incrE,incrNE,d,x,y; y1=2*y0-y1;

dx=x1-x0; dy=y1-y0; d=dx-2*dy; incrE=-2*dy; incrNE=2*(dx-dy); x=x0;y=y0;

putpixel(x,HEIGHT-y,color); while(x0) d+=incrE; else

{d+=incrNE; y++; } x++;

putpixel(x,HEIGHT-2*y0+y,color); } }

void line4(int x0,int y0,int x1,int y1,int color) { int dx,dy,incrE,incrNE,d,x,y; y1=2*y0-y1;

dx=x1-x0; dy=y1-y0; d=2*dx-dy; incrE=2*dx; incrNE=2*(dx-dy); x=x0;y=y0;

putpixel(x,HEIGHT-y,color); while(y{d+=incrNE; x++; } y++;

putpixel(x,HEIGHT-2*y0+y,color); } }󰀀

三.测试： 输入为（50,400）,(500,40),15,结果如下图，程序在Windows Me + Tc2.0下测试通过。