概述

中點(diǎn)畫線法（Midpoint Line Algorithm）是一種畫線（Line Drawing）算法，用來在計(jì)算機(jī)屏幕上繪制線條。

它的基本思想是從線段的起點(diǎn)和終點(diǎn)出發(fā)，按照一定的規(guī)則向終點(diǎn)逐步逼近，并在途中以控制變量的方式得出每個(gè)像素點(diǎn)的坐標(biāo)，從而繪制出所需的線條。

具體實(shí)現(xiàn)中，中點(diǎn)畫線法通過計(jì)算線段斜率的變化情況，來分為斜率小于1和大于等于1兩種情況，并采用Bresenham的對(duì)稱性原理，以中點(diǎn)的顏色來控制每個(gè)像素點(diǎn)的生長(zhǎng)方向，從而獲得較高的繪制效率和圖像質(zhì)量表現(xiàn)。

總的來說，中點(diǎn)畫線法是一種高效且易于實(shí)現(xiàn)的線段繪制算法，也是計(jì)算機(jī)圖形學(xué)領(lǐng)域最基本的算法之一。

一、基本思想

當(dāng)前像素點(diǎn)為$(x_p,y_p)$，下一個(gè)像素點(diǎn)為$P1$或$P2$。
設(shè)$M=(x_p+1,y_p+0.5)$為$P1$與$P2$之中點(diǎn)，$Q$為理想直線與$x=x_p+1$垂線的交點(diǎn)。將$Q$與$M$的$y$坐標(biāo)進(jìn)行比較。
當(dāng)$M$在$Q$的下方，則$P2$應(yīng)為下一個(gè)像素點(diǎn)；當(dāng)$M$在$Q$的上方，則$P1$應(yīng)為下一個(gè)像素點(diǎn)。

二、構(gòu)造判別式:

$$d=F(M)=F(x_p+1,y_p+0.5)=a(x_p+1)+b(y_p+0.5)+c$$
其中，$a=y_0?y_1,b=x_1?x_0,c=x_0{y}_1?x_1{y}_0$.

• 當(dāng)$d<0$時(shí)，$M$在$L(Q$點(diǎn)$)$下方，取右上方$P2(x_p+1,y_p+1)$為下一個(gè)像素；
• 當(dāng)$d>0$時(shí)，$M$在$L(Q$點(diǎn)$)$上方，取右方$P1(x_p+1,y_p)$為下一個(gè)像素；
• 當(dāng)$d=0$時(shí)，選$P1$或$P2$均可，約定取$P1(x_p+1,y_p)$為下一個(gè)像素；
• 

三、遞推出增量

若當(dāng)前像素處于：

$d\ge 0$情況，則取正右方像素$P1(x_p+1,y_p)$，要判下一個(gè)像素位置，應(yīng)計(jì)算
$$d1=F(x_p+2,y_p+0.5)=a(x_p+2)+b(y_p+0.5)=d+a$$
增量為$a$。

$d<0$時(shí)，則取右上方像素$P2(x_p+1,y_p+1)$。要判斷再下一像素，則要計(jì)算
$$d2=F(x_p+2,y_p+1.5)=a(x_p+2)+b(y_p+1.5)+c=d+a+b$$
增量為$a+b$。

優(yōu)化：

由于畫線從$(x_0,y_0$)開始，$d$的初值為：
$$d_0=F(x_0+1,y_0+0.5)=F(x_0,y_0)+a+0.5b=a+0.5b$$
可以用$2d$代替$d$來避免小數(shù)，提高效率。令$d_0=2a+b,d_1=2a,d_2=2a+2b$。

總結(jié)：

如果$d>0$，則中點(diǎn)$(x_{,}{y}_m)$在$L(Q)$的上方，此時(shí)應(yīng)該取右邊的像素點(diǎn)$P1(x_p+1,y_p)$，即$x$加1、$y$不變。此時(shí)，$d$的值增加$d1$，即$d=d+d1$。

如果$d<0$，則中點(diǎn)$(x_m,y_m)$在$L(Q)$的下方，應(yīng)該取右上方的像素點(diǎn)$P2(x_p+1,y_p+1)$，即$x$和$y$均加1。此時(shí)，$d$的值增加$d2$，即$d=d+d2$。

四、例題分析

以P0（0,0）到P1（5,2）為例，使用中點(diǎn)畫線法，計(jì)算$d_0$，$d_1$和$d_2$，并畫出對(duì)應(yīng)表格。

首先，根據(jù)兩點(diǎn)坐標(biāo)求出$a$、$b$、$c$的值，有：
$a=y_0?y_1=?2$
$b=x_1?x_0=5$
$c=x_0{y}_1?x_1{y}_0=?10$

接著，根據(jù)公式得到$d_0$，$d_1$和$d_2$的初值，有：
$d_0=2a+b=1$
$d_1=2a=?4$
$d_2=2a+2b=6$

然后，根據(jù)中點(diǎn)畫線法的算法流程結(jié)合總結(jié)，可以按照如下表格計(jì)算每個(gè)像素點(diǎn)的坐標(biāo)$(x_i,y_i)$以及$d_i$的變化：

其中，$P$表示像素點(diǎn)位置，$count$表示計(jì)數(shù)，$d$表示中點(diǎn)到直線距離的判別式值（經(jīng)過放大2倍），根據(jù)$d>0$還是$d<0$判斷所選的下一個(gè)像素點(diǎn)。對(duì)于$d=0$，約定選擇右下方的像素點(diǎn)。

最終，依照算法，連線的軌跡如下：

P0 (0, 0) -> (1, 1) -> (2, 1) -> (3, 2) -> (4, 2) -> P1 (5, 2)

如下圖：
文章來源地址http://www.zghlxwxcb.cn/news/detail-762918.html

五、偽代碼

/* mid PointLine */
void Midpoint Line (int x0,int y0,int x1, int y1,int color)
     {   int a, b, d1, d2, d, x, y;
    a=y0-y1, b=x1-x0, d=2*a+b;
    d1=2*a, d2=2* (a+b);
    x=x0, y=y0;
    drawpixel(x, y, color);
    while (x<x1)
    { if (d<0)       {x++, y++, d+=d2; }
     else       {x++, d+=d1;}
     drawpixel (x, y, color);
     }  /* while */
 } 

到了這里，關(guān)于【計(jì)算機(jī)圖形學(xué)|直線生成算法】中點(diǎn)畫線法的文章就介紹完了。如果您還想了解更多內(nèi)容，請(qǐng)?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！