首先你的初中數(shù)學(xué)要過關(guān)#####
基本上Bresenham畫線算法的思路如下:
// 假設(shè)該線段位于第一象限內(nèi)且斜率大于0小于1闻葵，斜率在這個(gè)范圍內(nèi)屬于y坐標(biāo)點(diǎn)小于x坐標(biāo)點(diǎn)的情況湿滓，如果斜率大于1小于則屬于y坐標(biāo)點(diǎn)大于x坐標(biāo)點(diǎn)情況睛琳，根據(jù)對(duì)稱性,可推導(dǎo)至全象限內(nèi)的線段员舵。
// 設(shè)起點(diǎn)為(x1, y1),終點(diǎn)為(x2, y2)黄伊。
1.畫起點(diǎn)(x1, y1)号俐。
2.準(zhǔn)備畫下個(gè)點(diǎn)。x坐標(biāo)增1救欧，判斷如果達(dá)到終點(diǎn)衰粹，則完成。否則笆怠，由圖中可知铝耻，下個(gè)要畫的點(diǎn)要么為當(dāng)前點(diǎn)的右鄰接點(diǎn)，要么是當(dāng)前點(diǎn)的右上鄰接點(diǎn)。
2.1.如果線段ax+by+c=0與x=x1+1的交點(diǎn)的y坐標(biāo)大于M點(diǎn)的y坐標(biāo)的話,下個(gè)點(diǎn)為U(x1+1,y1+1)
2.2.否則,下個(gè)點(diǎn)為B(x1+1,y1)
3.畫點(diǎn)(U或者B).
4.跳回第2步.
5.結(jié)束.
Bresenham算法主要思路說白了就是：下一個(gè)要畫的點(diǎn)該畫在哪里瓢捉，要么在斜邊频丘，要么在側(cè)邊。斜邊就是x坐標(biāo)加1的同時(shí)y坐標(biāo)也加1 泡态。側(cè)邊就是只加x或者只加y坐標(biāo)搂漠。要如何確定畫在哪個(gè)邊呢？因?yàn)橐阎瘘c(diǎn)坐標(biāo)和終點(diǎn)坐標(biāo)分別(x1, y1)某弦，(x2, y2)桐汤，所以可以確定這條線段的位置。最后根據(jù)要畫的這個(gè)點(diǎn)距離這個(gè)線段的位置的大小靶壮，來確定該畫在斜邊還是側(cè)邊怔毛。斜邊近就畫斜邊，側(cè)邊近就畫側(cè)邊腾降。
下面是求解思路
設(shè)線段方程：ax+by+c=0(x1<x<x2,y1<y<y2)
令dx=x2-x1,dy=y2-y1
則：斜率-a/b = dy/dx.
從第一個(gè)點(diǎn)開始拣度，我們有F(x,1,y1) = ax1+by1+c=0
下面求線段ax+by+c=0與x=x1+1的交點(diǎn):
由a(x1+1)+by+c = 0, 求出交點(diǎn)坐標(biāo)y=(-c-a(x1+1))/b
所以交點(diǎn)與M的y坐標(biāo)差值Sub1 = (-c-a(x1+1))/b - (y1+0.5) = -a/b-0.5，即Sub1的處始值為-a/b-0.5螃壤。
則可得條件當(dāng) Sub1 = -a/b-0.5>0時(shí)候,即下個(gè)點(diǎn)為U.
反之,下個(gè)點(diǎn)為B.
代入a/b,則Sub1 = dy/dx-0.5.
因?yàn)槭莻€(gè)循環(huán)中都要判斷Sub,所以得求出循環(huán)下的Sub表達(dá)式,我們可以求出Sub的差值的表達(dá)式.下面求x=x1+2時(shí)的Sub抗果，即Sub2
1.如果下下個(gè)點(diǎn)是下個(gè)點(diǎn)的右上鄰接點(diǎn)，則
Sub2 = (-c-a(x1+2))/b - (y1+1.5) = -2a/b - 1.5
故Sub差值Dsub = Sub2 - Sub1 = -2a/b - 1.5 - (-a/b-0.5) = -a/b - 1.代入a/b得Dsub = dy/dx -1;
2.如果下下個(gè)點(diǎn)是下個(gè)點(diǎn)的右鄰接點(diǎn)奸晴，
Sub2 = (-c-a(x1+2))/b - (y1+0.5) = -2a/b - 0.5
故Sub差值Dsub = Sub2 - Sub1 = -2a/b - 0.5 - (-a/b-0.5) = -a/b. 代入a/b得Dsub = dy/dx;
于是冤馏，我們有了Sub的處始值Sub1 = -a/b-0.5 = dy/dx-0.5,又有了Sub的差值的表達(dá)式Dsub = dy/dx -1 （當(dāng)Sub1 > 0）或 dy/dx（當(dāng)Sub1 < 0）.細(xì)化工作完成。
偽裝代碼如下：
x=x1;
y=y1;
dx = x2-x1;
dy = y2-y1;
Sub = dy/dx-0.5; // 賦初值蚁滋，下個(gè)要畫的點(diǎn)與中點(diǎn)的差值
DrawPixel(x, y); // 畫起點(diǎn)
while(x<x2)
{
x++;
if(Sub > 0) // 下個(gè)要畫的點(diǎn)為當(dāng)前點(diǎn)的右上鄰接點(diǎn)
{
Sub += dy/dx - 1; //下下個(gè)要畫的點(diǎn)與中點(diǎn)的差值
y++; // 右上鄰接點(diǎn)y需增1
}
else// 下個(gè)要畫的點(diǎn)為當(dāng)前點(diǎn)的右鄰接點(diǎn)
{
Sub += dy/dx;
}
// 畫下個(gè)點(diǎn)
DrawPixel(x,y);
}
PS:一般優(yōu)化： 為避免小數(shù)轉(zhuǎn)整數(shù)以及除法運(yùn)算宿接，由于Sub只是用來進(jìn)行正負(fù)判斷，所以可以令Sub = 2dxSub = 2dy-dx,則
相應(yīng)的DSub = 2dy - 2dx或2dy.
思考:如果Sub = 0時(shí)辕录，會(huì)產(chǎn)生取兩個(gè)點(diǎn)都可以的問題睦霎。這種情況可以任意隨機(jī)選一個(gè)點(diǎn)，或者條件判斷上Sub >= 0 作為默認(rèn)條件取其一走诞。
Bresenham算法用途：
1圖像畫線的時(shí)候副女，可以讓線條更細(xì)膩，不會(huì)出現(xiàn)鋸齒蚣旱。
2游戲里碑幅，網(wǎng)格地圖中，當(dāng)人物走斜線的時(shí)候塞绿，用這個(gè)算法生成的行走路徑更合理些沟涨。
