中点画线算法-原理及实现
加入技术交流群
中点画线算法-原理及实现
计算机图形学-中点画线算法
在编写的FDGK/GUI决定采用中点画线算法绘制直线。故先研究了一下算法。
中点画线算法的原则是：如下图所示，但斜率K<1时，选定一个点之后，再计算中点M。如果M>0,这线更靠近E点，下一点选择为E点。反之选择NE点。
首先：f(x,y) = ax+by+c=0,
且 y = dy/dx *x + B,
so : f(x,y) = dy*x-dx*y+Bdx =0
so: a = dy, b = -dx, c = Bdx.
假设，已经选定P点，应用中点法则选择下一点是，我们只要计算f(x+1,y+1/2),并考察是正数还是负数。
我们定义d=f(x+1,y+1/2)=a(x+1)+b(y+1/2)+c.这样，对于d>0,d<0，我们只要选择NE点和E点就可以了。
这边假设选定为E点，那么中点M的位置怎么变化和d的值如何变化呢？显然M就沿着x轴递增一步。
此时：d1 = f(x+2,y+1/2)
从d1中减去d，可以得到一个增量差。d1= a = dy。
同理：如果选定下一点为NE点，d2 = a+b = dy-dx。
基于上面的讨论，增量的中点技术可以概括为：在每一步，我们根据上一步所得到的增量的符号去选择下一个像素点。然后根据说选择的像素，判定变量增加相应的增量差d1或d2。
对于初始值，我们选择第一个端点为(x0,y0)。则M为(x0+1,y+1/2).
f(x0+1,y0+1/2) = f(x0,y0)+a+b/2.
故： d0 = a+b/2 = dy - dx/2
为去掉d0中的小数，我们对d0进行放大。（在方程两边同乘于2）
d0 = 2*dy - dx
d1 = 2*dy
d2 = 2*(dy-dx)
所以，在斜率小于1的情况下，中点画线的算法实现如下：
void GUI_DrawLine(uint16 x0,uint16 y0,uint16 x1,uint16 y1,uint16 color)
{
uint16 dx,dy,incrE,incrNE,x,y,d;
dx = x1 - x0;
dy = y1 - y0;
d = (dy<<1) - dx;
incrE = dy<<1;
incrNE = (dy - dx)<<1;
x = x0;
y = y0;
GUI_DrawPoint(x,y,color);
while(x<x1)
{
if(d > 0)
{
d += incrNE;
x++;
y++;
}
else
{
d += incrE;
x++;
}
GUI_DrawPoint(x,y,color);
}
}
以上只是在K<1的情况下即在（1）中成立。那其他情况怎么办呢？
我的处理方法是这样的：
1、把3，4，5，6情况下的两个端点调换，把它变换成1，2，7，8的情况，这样我们要考虑的情况就少一半。
2、1和8，2和7关于x轴对称。1和2关于y=x对称。这样，我们就可以把1情况下的算法，移植到其他情况下。
改进后的算法如下：
void swap(uint16 *x0,uint16 *y0,uint16 *x1,uint16 *y1)
{
uint16 x,y;
x = *x1;
*x1 = *x0;
*x0 = x;
y = *y1;
*y1 = *y0;
*y0 = y;
}
void GUI_DrawLine(uint16 x0,uint16 y0,uint16 x1,uint16 y1,uint16 color)
{
int16 dx,dy,d;
uint16 x,y;
if( x0 > x1) /* 保证x0<x1,即x0为x1左边的点。*/
{
swap(&x0,&y0,&x1,&y1);
}
dx = x1 - x0;
dy = y1 - y0;
if( dx == 0) /* 斜率为无穷大，画直竖线 */
{
LCD_DrawVLine(x0,y0,y1,color);
return;
}
if( dy == 0) /*斜率为零，画水平线 */
{
LCD_DrawHLine(x0,y0,x1,color);
return;
}
x = x0;
y = y0;
GUI_DrawPoint(x,y,color);
if((dx>=dy)&&(dy>0)) /* when 0<k<=1 */
{
d = (dy*2) - dx;
while(x<x1)
{
if(d > 0)
{
d += (dy - dx)*2; /* 选择NE点 */
x++;
y++;
}
else
{
d += dy*2; /* 选择N点 */
x++;
}
GUI_DrawPoint(x,y,color);
}
return;
}
if( (dy>dx)&&(dy>0)) /* when k>1 */
{
d = dy - (dx*2);
while(y<y1)
{
if(d < 0)
{
d += (dy - dx)*2; /* 选择 NE 点 */
x++;
y++;
}
else
{
d += (-dx)*2; /* 选择N点 */
y++;
}
GUI_DrawPoint(x,y,color);
}
return;
}
if((dx>=ABS(dy))&&(dy<0)) /* when -1=<k<0 */
{
d = (dy*2) + dx; /* d = 2a-b */
while(x<x1)
{
if(d < 0)
{
d += (dy+dx) * 2; /* 选择SE点 */
x++;
y--;
}
else
{
d += dy*2; /* 选择S点 */
x++;
}
GUI_DrawPoint(x,y,color);
}
return;
}
if( (ABS(dy)>dx)&&(dy<0)) /* when k<-1 */
{
d = dy + (dx*2); /* d = a - 2b */
while(y>y1)
{
if(d > 0)
{
d += (dy + dx)*2; /* 选择 SE 点 */
x++;
y--;
}
else
{
d += (dx)*2; /* 选择S点 */
y--;
}
GUI_DrawPoint(x,y,color);
}
return;
}
}
专栏文章内容及配图由作者撰写发布，仅供工程师学习之用，如有侵权或者其他违规问题，请联系本站处理。 联系我们
关键词：
相关推荐
TDA2030A功放电路
宽 VIN 范围降压型稳压器仅消耗 2.8µA 输入电流
44b0一个寻址的问题,请高手指点迷径...
TDA2020功放电路
日立3D全息显示设备展示
PowerCo在萨尔茨吉特启动欧洲电池单元生产
那位大师帮我算几个PCM编码样点,有谢!!!
如何编写 Linux 设备驱动程序
拍个马屁
近距离感受罗德与施瓦茨厚重企业魅力
CEATEC 2011日本东京高新技术博览会的几个亮点
嵌入式系统设计编程文档
轻型驱动微米级电机和齿轮组
住友3M展示投影式静电容量式触摸面板
嵌入式系统文章集粹1
amd29LvMtd.c文件问题
中国芯片整合升级：华虹收购华力97.5%股权，继中芯国际此前的举动之后
中国维持2026年设备换新：最高补贴500元人民币;智能手机，智能眼镜聚焦
那位大师帮我算几个PCM编码样点,有谢!!!
TDA2009功放电路
嵌入式系统及实时软件开发
博世Sensortec和Espressif扩展传感器平台与ESP SensairShuttle协同工作
深入理解Linux虚拟内存管理原书光盘1
TDA2040功放电路
中国半导体研究在内存和集成电路设计方面取得多项突破
比亚迪新晋全球纯电销冠！特斯拉2025年交付量跌逾8%至164万辆
TDA2008功放电路
据报道，中国CSOT将首次为三星Galaxy A57提供灵活的OLED设备
通过智能NoC自动化打破SoC设计的壁垒
何时、何地及为何使用芯片组