目录
写在前面：
DDA算法
原理：
代码实现：
中点画线算法
原理：
代码实现：
Bresenham算法
原理：
代码实现：
写在前面：
我们所认识的数学上的图形是一系列连续点构成的，但是计算机显示图形时，仅能显示一个一个离散的像素，这是由硬件显示本身造成的，无法避免。因此我们使用各种算法，目的在于利用这些算法，得到一个计算机显示的、符合人们常规认知的、看起来连续的、阶梯效应小的图形。所以我们以下所有图形绘制算法都是基于这一考量进行图形绘制的。
DDA算法
原理：
DDA算法是基于增量思想进行直线绘制的。
首先考虑直线斜率存在且绝对值<=1的情况，假设我们已知端点A坐标(x1, y1)以及端点B坐标(x2, y2)，要绘制如上图所示的直线AB。当▲x=1时，▲y=(y2-y1)/(x2-x1)。此时从A点起始，我们每次给x增加1，y就会增加k。我们每次取x以及最接近y的整数构成的坐标点进行绘制，直到绘制到达B点。 我们需要思考的第一个要点是，为什么是以x增加1为基础进行增量分析？因为我们现在分析的这种情况下，x的变化量大于y的变化量，在差距较大时，以y为基础进行增量分析就可能发生线段断开的情况。第二个要点是，直线斜率不存在或>1时怎么办？对于这个问题，我们仅需要以y每次增加1为基础进行增量绘制就可以了。
由于DDA算法种涉及到浮点数的运算，故而在时间效率上不如中点画线算法以及Bresenham算法。
代码实现：
//mfc中的实现函数
void DDALine(const pair
{
CClientDC dc(mView);
//以下是直线段的绘制（自行补充）
double x0 = start.first(), y0 = start.second(), x1 = end.first(), y1 = end.second();
double xbase = x0 + 0.5, ybase = y0 + 0.5;
double dx = x1 - x0, dy = y1 - y0;
double length;
length = (abs(dx) > abs(dy) ? abs(dx) : abs(dy));
dx /= length; dy /= length;
dc.SetPixel(xbase, ybase, color);
for (int i = 1; i <= length; i++)
{
xbase += dx;
ybase += dy;
dc.SetPixel(xbase, ybase, color);
}
}
中点画线算法
原理：
中点画线算法的主要思想是：在前一已知点位置的基础上，选择下一绘制点可能像素位置中靠近直线像素进行绘制的一种算法。
假设我们现在想要绘制斜率>0且<1的直线AB。首先，通过A、B两点的坐标我们可以获得直线方程F(x, y)=ax+by+c=0，其中a=(y1-y2),b=(x2-x1),c=(x1y2-x2y1)。 我们可以对于直线上方一点(x0,y0)有F(x0, y0)>0，对于直线下方一点(x',y')有F(x', y')<0。其次假设在从左到右绘制过程中，假设已经绘制到点(xpos, ypos)，那么下一个绘制点一定在(xpos+1,ypos+1)或(xpos+1,ypos)的位置，即或右或右上位置。基于以上两点认识，我们可以通过计算F(xpos+1, ypos+0.5)的值，若大于0，则证明该点在直线的上方，说明直线与(xpos+1, ypos)位置更加接近，应选取该点；反之，若该值小于0，则证明该点在直线的下方，直线与(xpos+1, ypos+1)位置更加接近，应选取这个点。 对于上述计算方式而言，每次计算一个2乘法3加法然后在进行与0的大小比较，时间效率较低。我们考虑将这个计算进行增量方式的简化。我们将任意点的F(x,y)计算记为d，考虑我们所求点的序列对应的d值的变化过程。考虑以下两种情况： （1）d=F(x+1, y+0.5)>=0，取像素点(x+1, y)进行绘制，然后对(x+2, y)以及(x+2,y+1)进行考虑，计算d1=F(x+2, y+0.5)=d+a。 （2）d=F(x+1, y+1.5)>=0，取像素点(x+1, y+1)进行绘制，然后对(x+2, y+1)以及(x+2,y+2)进行考虑，计算d2=F(x+2, y+1.5)=d+a+b。 （3）d初始值d0=F(x1+1, y1+0.5)=a+0.5b。 考虑到我们仅需要d与0的大小关系，为避免浮点运算，可以将d变化为2d，即，d0=2*a+b，d1=d+2*a，d2=d+2*(a+b)。
对于其它斜率直线来讲，仅需进行类似操作即可。
对于中点画线算法来讲，同样是采取逐点计算绘制的方式进行。但是在计算的过程中，仅涉及到移位与加法运算，效率比DDA算法更高。
代码实现：
void MidPointLine(const pair
{
CClientDC dc(mView);
//以下是直线段的绘制
int x1, x2, y1, y2;
if (start.first > end.first) x1 = end.first, x2 = start.first, y1 = end.second, y2 = start.second;
else x1 = start.first, x2 = end.first, y1 = start.second, y2 = end.second;
int a = y1 - y2, b = x2 - x1;
int xbase = x1, ybase = y1;
int s1 = 1, s2 = (a < 0 ? 1 : -1);
if (abs(b) >= abs(a))//dx>dy
{
int d = ((a << 1) + (a < 0 ? 1 : -1) * b), deta1 = a << 1, deta2 = (a + (a < 0 ? 1 : -1) * b) << 1;
while (xbase <= x2)
{
if ((a < 0) ^ (d >= 0))
{
xbase += s1, ybase += s2;
::SetPixel(hDC, xbase, ybase, color);
d += deta2;
}
else
{
xbase += s1;
::SetPixel(hDC, xbase, ybase, color);
d += deta1;
}
}
}
else
{
int d = ((a < 0?1:-1) * (b << 1)) + a, deta1 = (a < 0?1:-1) * (b << 1), deta2 = (a + (a < 0?1:-1) * b) << 1;
while (ybase != y2)
{
if ((a < 0) ^ (d >= 0))
{
ybase += s2;
::SetPixel(hDC, xbase, ybase, color);
d += deta1;
}
else
{
xbase += s1; ybase += s2;
::SetPixel(hDC, xbase, ybase, color);
d += deta2;
}
}
::SetPixel(hDC, x2, y2, color);
}
}
Bresenham算法
原理：
Bresenham算法与的中点直线绘制算法的主要思想类似。
同样首先对|m|<=1的情况进行考虑。首先定义▲x=x2-x1，▲y=y2-y1。对于一个已确定的点，其下一个点在右侧或右上侧，在假设选择右边点的基础上进行误差e的计算，根据e是否过半像素大小决定最终绘制点。以A为起点，那么e初始值=▲y/▲x。对于基于(xpos, ypos)的选择我们有：
（1）假设计算当前e后选择(xpos+1, ypos)，那么下一步误差e‘=e+▲y/▲x。（如上图蓝色线）误差增量deta1=▲y/▲x。 （2）假设计算当前e后选择(xpos+1, ypos+1)，那么下一步误差e‘=e+▲y/▲x-1。（如上图绿色线）误差增量deta2=▲y/▲x-1。 由于涉及到e与0.5的比较，令e初值为。于是e>0，则选择右上位置，否则选择右侧位置。 为避免浮点运算，我们可令e初值为2▲y-▲x，则deta1=2▲y，deta2=2(▲y-▲x)。其余与上述理论一致。
对于其它斜率直线来讲，仅需进行类似操作即可。
对于Bresenham画线算法来讲，同样是采取逐点计算绘制的方式进行。但是在计算的过程中，仅涉及到移位与加法运算，效率比DDA算法更高，与中点画线算法相近。
代码实现：
void BresenhamLine(const pair
{
CClientDC dc(mView); //如果hDC为0时使用
//以下是直线段的绘制（自行补充）
int x1 = start.first(), y1 = start.second(), x2 = end.first(), y2 = end.second();
int dx = x2 - x1, dy = y2 - y1;
int s1 = (dx >= 0 ? 1 : -1), s2 = (dy >= 0 ? 1 : -1);
dx = abs(dx); dy = abs(dy);
dc.SetPixel(x1, y1, color);
int xbase = x1, ybase = y1;
if (dx >= dy)
{
int e = (dy << 1) - dx, deta1 = dy << 1, deta2 = (dy - dx) << 1;
while (xbase != x2)
{
if (e >= 0)//y方向增量为1
xbase += s1, ybase += s2, e += deta2;
else xbase += s1, e += deta1;
dc.SetPixel(xbase, ybase, color);
}
}
else
{
int e = (dx << 1) - dy, deta1 = dx << 1, deta2 = (dx - dy) << 1;
while (ybase != y2)
{
if (e >= 0)//x方向增量为1
xbase += s1, ybase += s2, e += deta2;
else ybase += s2, e += deta1;
(!hDC) dc.SetPixel(xbase, ybase, color);
}
}
}