直线画中点算法

㈠ 求计算机图形学中的直线绘制函数法、DDA算法、中点法和Bresenham算法的优缺点以及比较.

DDA称为数值微分画线算法,是直线生成算法中最简单的一种.原理相当简单,就是最直观的根据斜率的偏移程度,决定是以x为步进方向还是以y为步进方向.然后在相应的步进方向上,步进变量每次增加一个像素,而另一个相关坐标变量则为Yk_1=Yk+m（以x为步进变量为例,m为斜率）假定直线斜率k在0~1之间,当前象素点为（xp,yp）,则下一个象素点有两种可选择点P1（xp+1,yp）或P2（xp+1,yp+1）.若P1与P2的中点（xp+1,yp+0.5）称为M,Q为理想直线与x=xp+1垂线的交点.当M在Q的下方时,则取P2应为下一个象素点；当M在Q的上方时,则取P1为下一个象素点.这就是中点画线法的基本原理Bresenham：过各行、各列像素中心构造一组虚拟网格线,按直线从起点到终点的顺序计算直线各垂直网格线的交点,然后确定该列像素中与此交点最近的像素.该算法的优点在于可以采用增量计算,使得对于每一列,只要检查一个误差项的符号,就可以确定该列所求的像素.大概就是这样,预知详细,

㈡ 四道图像图像算法题目

取X=0时，在Y轴上画点1。
取Y=0时，在X轴上画点2。
画直线通过两点。
你画的X=0时，Y是几？自己数手指头去。

㈢ 求中点画线算法的c++代码...

直线方程:a*x+b*y+c=0, p1(x1,y1), p2(x2,y2)==> a=y1-y2;b=x2-x1.

点到直线的距离：distance=|a*x0-b*y0+c|/sqrt(a*a + b*b)
设directionX,directionY分别为从(x1,y1)==>(x2,y2)的单位变化量（+/-1）

当直线偏向X轴时，当前象素为（xk， yk），下一个象素可能为：(xk+directionX, yk)或者(xk+directionX,yk+directionY)这两点到直线的距离分别为：

d1=|a*xk+b*yk+c+a*directionX|/sqrt(a*a + b*b);
d2=|a*xk+b*yk+c+a*directionX+b*directonY|/sqrt(a*a + b*b);
便于运算，定义:f(xk,yk)= d2 * d2 - d1 * d1 (将d1和d2的分母去掉了的)
= b*b + 2*b*directonY*(a*xk+b*yk+c+a*directionX) ;
当f(xk,yk)<0的时候，下一个点为(xk+directionX,yk+directionY):
f(xk+directionX,yk+directionY)=f(xk,yk) +2*b*b+2*a*b*directionX*directionY ;
当f(xk,yk)>=0的时候，下一个点为(xk+directionX, yk) :
f(xk+directionX, yk) = f(xk,yk) + 2*a*b*directionX*directionY ;

当直线偏向Y轴时，当前象素为（xk， yk），下一个象素可能为：(xk, yk+directionY)或者(xk+directionX,yk+directionY)这两点到直线的距离分别为：

d1=|a*xk+b*yk+c+b*directionY|/sqrt(a*a + b*b);
d2=|a*xk+b*yk+c+b*directionY+a*directonX|/sqrt(a*a + b*b);
便于运算，定义:f(xk,yk)= d2 * d2 - d1 * d1 (将d1和d2的分母去掉了的)
= a*a + 2*a*directonX*(a*xk+b*yk+c+b*directionY) ;
当f(xk,yk)<0的时候，下一个点为(xk+directionX,yk+directionY):
f(xk+directionX,yk+directionY)=f(xk,yk) +2*a*a+2*a*b*directionX*directionY ;
当f(xk,yk)>=0的时候，下一个点为(xk+directionX, yk) :
f(xk+directionX, yk) = f(xk,yk) + 2*a*b*directionX*directionY ;

/*
* 中点画线算法
*/
void LineMLDA(HDC& hdc, POINT ptSrc, POINT ptDec, COLORREF cr)
{
int a, b ;

a = ptSrc.y - ptDec.y ;
b = ptDec.x - ptSrc.x ;

int iDirectionX, iDirectionY ;

iDirectionX = iDirectionY = 1 ;
if(b<0)
iDirectionX = -1 ;
if(a>0)
iDirectionY = -1 ;

int iDistance,
iDeltaSmall, iDeltaBig ,
iCurrX, iCurrY ;

int iStep ;

iDeltaSmall = 2*a*b*iDirectionX*iDirectionY ;

iCurrX = ptSrc.x ;
iCurrY = ptSrc.y ;

if(abs(b) > abs(a))
{
iDeltaBig = 2*b*b + iDeltaSmall ;
iDistance = b*b + iDeltaSmall ;

iStep = abs(b) ;

while (iStep-- > 0)
{
SetPixel(hdc, iCurrX, iCurrY, cr) ;

iCurrX += iDirectionX ;
if(iDistance < 0)
{
iCurrY += iDirectionY ;

iDistance += iDeltaBig ;
}
else
{
iDistance += iDeltaSmall ;
}
}
}
else
{
iDeltaBig = 2*a*a + iDeltaSmall ;
iDistance = a*a + iDeltaSmall ;

iStep = abs(a) ;

while (iStep-- > 0)
{
SetPixel(hdc, iCurrX, iCurrY, cr) ;

iCurrY += iDirectionY ;
if(iDistance < 0)
{
iCurrX += iDirectionX ;

iDistance += iDeltaBig ;
}
else
{
iDistance += iDeltaSmall ;
}
}
}

SetPixel(hdc, ptDec.x, ptDec.y, cr) ;
}

㈣ 与DDA算法相比，中点画线法有什么优点

void DDALine(int x0,int y0,int x1,int y1,int color) {
int x；
float dx, dy, y, k；
dx = x1-x0； dy=y1-y0；
k=dy/dx,；y=y0；
for (x=x0；x< x1；x++) {
drawpixel (x, int(y+0.5), color);
y=y+k;
}
}
…… top↑

如上面代码所示，DDA算法中的y和k都必须用浮点数表示，并且每一步运算都要对y进行舍入取整，这不利于硬件实现。中点画线法只包含整数变量，并且不含乘除法，因而解决了上述问题

㈤ 图形学中的中点画线法与Bresenham算法画线的区别

个人认为最关键的区别就是那个决策参数的计算方式！
在Bresenham算法中，假设我们在（x0，y0）处画了一个点，那我们就要决定下一个点是在（x0+1，y0）还是在（x0+1，y0+1）处画，这两个点一般都不在直线上，我们要计算这两个点离直线有多远，分别设两个点离直线的距离为p1、p2，然后决策参数就是p=p2-p1，再根据p的符号来判断选择哪个点
至于中点法，我没有用它来画过直线，只用来画过圆（自我感觉画圆用这个算法比Bresenham算法要好很多），但原理应该差不多！
在中点算法中，决策参数的就是方式就是圆的方程（换成直线就是直线的方程了），比如要画x^2+y^2=r^2的圆，那决策参数p=x^2+y^2-r^2,然后就不是代入上面找到的两个点直接代进去，而是代这两个点的中点进去，求出p的值，根据p的符号来判断那个中点是在圆上、圆内还是圆外，再进一步决定选择绘哪个点！
具体的计算过程没办法在这里完整演示，但个人认为不同之处还是在于决策参数的选择与计算