直線畫中點演算法

㈠ 求計算機圖形學中的直線繪制函數法、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的符號來判斷那個中點是在圓上、圓內還是圓外，再進一步決定選擇繪哪個點！
具體的計算過程沒辦法在這里完整演示，但個人認為不同之處還是在於決策參數的選擇與計算