中點畫線演算法
① 求計算機圖形學中的直線繪制函數法、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：過各行、各列像素中心構造一組虛擬網格線,按直線從起點到終點的順序計算直線各垂直網格線的交點,然後確定該列像素中與此交點最近的像素.該演算法的優點在於可以採用增量計算,使得對於每一列,只要檢查一個誤差項的符號,就可以確定該列所求的像素.大概就是這樣,預知詳細,
② 比較數值微分法 中點畫線法 bresenham生成直線優缺點
Bresenham演算法的特點是:
1,不必計算直線之斜率,因此不做除法;
2,不用浮點數,只用整數;
3,只做整數加減法和乘2運算,而乘2運算可以用硬體移位實現.
Bresenham演算法速度很快,並適於用硬體實現.
DDA演算法的特點:
浮點數運算
不易硬體實現
中點畫線法特點:
只有整數運算,不含乘除法
可用硬體實現
因(X0,Y0)在直線上,所以F(X0,Y0)=0
③ 分別解釋直線生成演算法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：過各行、各列像素中心構造一組虛擬網格線，按直線從起點到終點的順序計算直線各垂直網格線的交點，然後確定該列像素中與此交點最近的像素。該演算法的優點在於可以採用增量計算，使得對於每一列，只要檢查一個誤差項的符號，就可以確定該列所求的像素。
大概就是這樣，預知詳細，可以參考圖形學的書籍
④ 與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進行舍入取整，這不利於硬體實現。中點畫線法只包含整數變數，並且不含乘除法，因而解決了上述問題
⑤ 用中點畫線法掃描轉換從(1,0)到(4,7)經過的直線段,病給出每一步的判斷值.
自己做好自己的吧
⑥ 誰有中點畫線法繪直線，bresenham畫線法繪直線，多邊形，bresenham畫圓法，還有漢字生成的c語言源程序
哈哈，把我們實驗課的成就給你吧，都在實驗室里通過的。不過沒有你要的全部
#include <stdafx.h>
#include <math.h>
#define ROUND(a) ((int) (a+0.5))
void bresenham(CDC* pdc,int xs,int ys,int xe,int ye,COLORREF color)//直線
{
int dx=xe-xs;
int dy=ye-ys;
int xinc,yinc;
if(dx>0)
xinc=1;
else
xinc=-1;
if(dy>0)
yinc=1;
else
yinc=-1;
dx=abs(dx);dy=abs(dy);
int x=xs,y=ys;
int i=0;
if(dx==0&&dy==0)
pdc->SetPixel(x,y,color);
else if(dx==0)
{
for(i=0;i<dy;i++)
{
pdc->SetPixel(x,y,color);
y+=yinc;
}
}
else if(dy==0)
{
for(i=0;i<dx;i++)
{
pdc->SetPixel(x,y,color);
x+=xinc;
}
}
else if(dx>dy)
{
int p=2*dy-dx;
int inc1=2*dy,inc2=2*(dy-dx);
for(i=0;i<dx;i++)
{
pdc->SetPixel(x,y,color);
x+=xinc;
if(p<0)
p+=inc1;
else
{
y+=yinc;
p+=inc2;
}
}
}
else
{
int p=2*dx-dy;
int inc1=2*dx,inc2=2*(dx-dy);
for(i=0;i<dy;i++)
{
pdc->SetPixel(x,y,color);
y+=yinc;
if(p<0)
p+=inc1;
else
{
x+=xinc;
p+=inc2;
}
}
}
}
中點圓：
#include "stdafx.h"
void circlePlotPoints(CDC *pdc, int xc,int yc,int x,int y,COLORREF color);
void MidpointCircle(CDC* pdc,int xc,int yc,int r,COLORREF color)
{
int x=0;
int y=r;
int p=1-r;
while(x<=y)
{
circlePlotPoints(pdc, xc,yc,x,y,color);
x++;
if(p<0)
p+=2*x+1;
else
{
y--;
p+=2*(x-y)+1;
}
}
}
void circlePlotPoints(CDC *pdc, int xc,int yc,int x,int y,COLORREF color)
{
pdc->SetPixel(xc+x,yc+y,color);
pdc->SetPixel(xc+x,yc-y,color);
pdc->SetPixel(xc-x,yc+y,color);
pdc->SetPixel(xc-x,yc-y,color);
pdc->SetPixel(xc+y,yc+x,color);
pdc->SetPixel(xc+y,yc-x,color);
pdc->SetPixel(xc-y,yc+x,color);
pdc->SetPixel(xc-y,yc-x,color);
}
⑦ 求中點畫線演算法的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) ;
}
⑧ 利用C語言編寫 能夠畫出任意斜率的直線演算法程序（利用中點畫線法改編）
將DDA演算法改成中點劃線演算法即可
// DDA畫線View.cpp : implementation of the CDDAView class
//
#include "stdafx.h"
#include "DDA畫線.h"
#include "DDA畫線Doc.h"
#include "DDA畫線View.h"
#ifdef _DEBUG
#define new DEBUG_NEW
#undef THIS_FILE
static char THIS_FILE[] = __FILE__;
#endif
/////////////////////////////////////////////////////////////////////////////
// CDDAView
IMPLEMENT_DYNCREATE(CDDAView, CView)
BEGIN_MESSAGE_MAP(CDDAView, CView)
//{{AFX_MSG_MAP(CDDAView)
// NOTE - the ClassWizard will add and remove mapping macros here.
// DO NOT EDIT what you see in these blocks of generated code!
//}}AFX_MSG_MAP
// Standard printing commands
ON_COMMAND(ID_FILE_PRINT, CView::OnFilePrint)
ON_COMMAND(ID_FILE_PRINT_DIRECT, CView::OnFilePrint)
ON_COMMAND(ID_FILE_PRINT_PREVIEW, CView::OnFilePrintPreview)
END_MESSAGE_MAP()
/////////////////////////////////////////////////////////////////////////////
// CDDAView construction/destruction
CDDAView::CDDAView()
{
// TODO: add construction code here
}
CDDAView::~CDDAView()
{
}
BOOL CDDAView::PreCreateWindow(CREATESTRUCT& cs)
{
// TODO: Modify the Window class or styles here by modifying
// the CREATESTRUCT cs
return CView::PreCreateWindow(cs);
}
/////////////////////////////////////////////////////////////////////////////
// CDDAView drawing
void CDDAView::OnDraw(CDC* pDC)
{
CDDADoc* pDoc = GetDocument();
ASSERT_VALID(pDoc);
int xx,yy,x2,y2,m,n;
float dx,dy,k,x,y;
int x0=50,y0=500,x1=50,y1=50;
if(x0>x1)
{
m=x0;x0=x1;x1=m;
m=y0;y0=y1;y1=m;
}
dx=x1-x0;
dy=y1-y0;
k=dy/dx;
if(x0==x1)
{
if(y0>y1)
{
n=y0;
y0=y1;
y1=n;
}
for(y2=y0;y2<=y1;)
{
for(n=-10;n<11;)
{
pDC->SetPixel(x0+n,y2,255);
n++;
}
y2=y2+3;
}
}
if(k>=-1&&k<=1.0)
{
y=y0;
for(x2=x0;x2<=x1;)
{
yy=(int)(y+0.5);
for(n=-10;n<11;)
{
pDC->SetPixel(x2,yy+n,255);
n++;
}
y=y+k;
x2++;
}
}
else if(k>1)
{
x=x0;
k=dx/dy;
for(y2=y0;y2<=y1;)
{
xx=(int)(x+0.5);
for(n=-10;n<11;)
{
pDC->SetPixel(xx+n,y2,255);
n++;
}
x=x+k;
y2++;
}
}
else if(k<-1)
{
x=x1;
k=dx/dy;
for(y2=y1;y2<=y0;)
{
xx=(int)(x+0.5);
for(n=-10;n<11;)
{
pDC->SetPixel(xx+n,y2,255);
n++;
}
x=x+k;
y2++;
}
}
// TODO: add draw code for native data here
}
/////////////////////////////////////////////////////////////////////////////
// CDDAView printing
BOOL CDDAView::OnPreparePrinting(CPrintInfo* pInfo)
{
// default preparation
return DoPreparePrinting(pInfo);
}
void CDDAView::OnBeginPrinting(CDC* /*pDC*/, CPrintInfo* /*pInfo*/)
{
// TODO: add extra initialization before printing
}
void CDDAView::OnEndPrinting(CDC* /*pDC*/, CPrintInfo* /*pInfo*/)
{
// TODO: add cleanup after printing
}
/////////////////////////////////////////////////////////////////////////////
// CDDAView diagnostics
#ifdef _DEBUG
void CDDAView::AssertValid() const
{
CView::AssertValid();
}
void CDDAView::Dump(CDumpContext& dc) const
{
CView::Dump(dc);
}
CDDADoc* CDDAView::GetDocument() // non-debug version is inline
{
ASSERT(m_pDocument->IsKindOf(RUNTIME_CLASS(CDDADoc)));
return (CDDADoc*)m_pDocument;
}
#endif //_DEBUG
/////////////////////////////////////////////////////////////////////////////
// CDDAView message handlers