中点画线算法画直线—-计算机图形学

中点画线算法：

所需绘制直线的左下端点记为
$(x_{0},y_{0})$
，右上端点记为
$(x_{1},y_{1})$

令
$dy = y_{1}- y_{0}$
,
$dx = x_{1}- x_{0}$
,则直线的斜截式为：
$y=\frac{dy}{dx}*x+B$

所以，用隐函数表示直线的方程为：
$F(x,y)=dx*y-dy*x-B*dx=0$

容易验证，点（x , y）若在直线上，F（x , y）= 0 ；若在直线上方，F（x , y）> 0 ；若在直线下方，F（x , y）< 0 。

（1）. 斜率在（0,1）区间：

假定选择了
$(x_{p},y_{p})$
处的像素 P ，现在必须在 P 的右邻像素 E 和右上方相邻像素 NE 中选取一个像素。

在中点算法中，只需计算
$F(M)=F(x_{p}+1,y_{p}+1/2)$
（M表示中点），并测试它的符号即可。

若 F（M）< 0 , 则 M 在直线下方，直线距离点 NE 更近，选择 NE ；若 F（M）> 0 , 则 M 在直线上方，直线距离点 E 更近，选择 E .

$J_{i}=F(M) = F(x_{p}+1,y_{p}+1/2) = dx*(y_{p}+1/2)-dy*(x_{p}+1)-B*dx$

如果选择的是 E ，应判断：

$J_{i+1}=F(Me) = F(x_{p}+2,y_{p}+1/2) = dx*(y_{p}+1/2)-dy*(x_{p}+2)-B*dx$

$= F(x_{p}+1,y_{p}+1/2)-dy$

$= J_{i}-dy$

如果选择的是 NE ，应判断：

$J_{i+1}=F(Mne) = F(x_{p}+2,y_{p}+3/2) = dx*(y_{p}+3/2)-dy*(x_{p}+2)-B*dx$

$= F(x_{p}+1,y_{p}+1/2)-dy+dx$

$= J_{i}-dy+dx$

因为第一个像素是端点
$(x_{0},y_{0})$
，可直接计算 J 的初始值
$J_{start}$
，以此决定是选 E 还是选 NE。

第一个中点在
$(x_{0}+1,y_{0}+1/2)$
处，有

$J_{start}= F(x_{0}+1,y_{0}+1/2) = dx*(y_{0}+1/2)-dy*(x_{0}+1)-B*dx$

$= dx*y_{0}+1/2*dx-dy*x_{0}-dy-B*dx$

$= F(x_{0},y_{0})-dy+1/2*dx$

由于
$(x_{0},y_{0})$
落在线上，因此
$F(x_{0},y_{0})=0$
，故
$J_{start}$
值为
$-dy+1/2*dx$
.

（2）. 斜率在（-1,0）区间：

假定选择了
$(x_{p},y_{p})$
处的像素 P ，现在必须在 P 的右邻像素 E 和右下方相邻像素 NE 中选取一个像素。

在中点算法中，只需计算
$F(M)=F(x_{p}+1,y_{p}-1/2)$
（M表示中点），并测试它的符号即可。

若 F（M）< 0 , 则 M 在直线下方，直线距离点 E 更近，选择 E ；若 F（M）> 0 , 则 M 在直线上方，直线距离点 NE 更近，选择 NE .

$J_{i}=F(M) = F(x_{p}+1,y_{p}-1/2) = dx*(y_{p}-1/2)-dy*(x_{p}+1)-B*dx$

如果选择的是 E ，应判断：

$J_{i+1}=F(Me) = F(x_{p}+2,y_{p}-1/2) = dx*(y_{p}-1/2)-dy*(x_{p}+2)-B*dx$

$= F(x_{p}+1,y_{p}-1/2)-dy$

$= J_{i}-dy$

如果选择的是 NE ，应判断：

$J_{i+1}=F(Mne) = F(x_{p}+2,y_{p}-3/2) = dx*(y_{p}-3/2)-dy*(x_{p}+2)-B*dx$

$= F(x_{p}+1,y_{p}-1/2)-dy-dx$

$= J_{i}-dy-dx$

因为第一个像素是端点
$(x_{0},y_{0})$
，可直接计算 J 的初始值
$J_{start}$
，以此决定是选 E 还是选 NE。

第一个中点在
$(x_{0}+1,y_{0}-1/2)$
处，有

$J_{start}= F(x_{0}+1,y_{0}-1/2) = dx*(y_{0}-1/2)-dy*(x_{0}+1)-B*dx$

$= dx*y_{0}-1/2*dx-dy*x_{0}-dy-B*dx$

$= F(x_{0},y_{0})-dy-1/2*dx$

由于
$(x_{0},y_{0})$
落在线上，因此
$F(x_{0},y_{0})=0$
，故
$J_{start}$
值为
$-dy-1/2*dx$
.

（3）. 斜率大于 1：

直线的方程用隐函数还可以表示为：
$F(x,y)=dy*x-dx*y+B*dx=0$
（即上方式子取反）

容易验证，点（x , y）若在直线上，F（x , y）= 0 ；若在直线左边，F（x , y）< 0 ；若在直线右边，F（x , y）> 0 。

假定选择了
$(x_{p},y_{p})$
处的像素 P ，现在必须在 P 的上邻像素 E 和右上方相邻像素 NE 中选取一个像素。

在中点算法中，只需计算
$F(M)=F(x_{p}+1/2,y_{p}+1)$
（M表示中点），并测试它的符号即可。

若 F（M）< 0 , 则 M 在直线左边，直线距离点 NE 更近，选择 NE ；若 F（M）> 0 , 则 M 在直线右边，直线距离点 E 更近，选择 E .

$J_{i}=F(M) = F(x_{p}+1/2,y_{p}+1) = dy*(x_{p}+1/2)-dx*(y_{p}+1)+B*dx$

如果选择的是 E ，应判断：

$J_{i+1}=F(Me) = F(x_{p}+1/2,y_{p}+2) = dy*(x_{p}+1/2)-dx*(y_{p}+2)+B*dx$

$= F(x_{p}+1/2,y_{p}+1)-dx$

$= J_{i}-dx$

如果选择的是 NE ，应判断：

$J_{i+1}=F(Mne) = F(x_{p}+3/2,y_{p}+2) = dy*(x_{p}+3/2)-dx*(y_{p}+2)+B*dx$

$= F(x_{p}+1/2,y_{p}+1)-dx+dy$

$= J_{i}-dx+dy$

因为第一个像素是端点
$(x_{0},y_{0})$
，可直接计算 J 的初始值
$J_{start}$
，以此决定是选 E 还是选 NE。

第一个中点在
$(x_{0}+1/2 , y_{0}+1)$
处，有

$J_{start}= F(x_{0}+1/2,y_{0}+1) = dy*(x_{0}+1/2)-dx*(y_{0}+1)+B*dx$

$= dy*x_{0}+1/2*dy-dx*y_{0}-dx+B*dx$

$= F(x_{0},y_{0})-dx+1/2*dy$

由于
$(x_{0},y_{0})$
落在线上，因此
$F(x_{0},y_{0})=0$
，故
$J_{start}$
值为
$1/2*dy-dx$
.

（4）. 斜率小于 -1：

假定选择了
$(x_{p},y_{p})$
处的像素 P ，现在必须在 P 的上邻像素 E 和左上方相邻像素 NE 中选取一个像素。

在中点算法中，只需计算
$F(M)=F(x_{p}-1/2,y_{p}+1)$
（M表示中点），并测试它的符号即可。

若 F（M）< 0 , 则 M 在直线左边，直线距离点 E 更近，选择 E ；若 F（M）> 0 , 则 M 在直线右边，直线距离点 NE 更近，选择 NE .

$J_{i}=F(M) = F(x_{p}-1/2,y_{p}+1) = dy*(x_{p}-1/2)-dx*(y_{p}+1)+B*dx$

如果选择的是 E ，应判断：

$J_{i+1}=F(Me) = F(x_{p}-1/2,y_{p}+2) = dy*(x_{p}-1/2)-dx*(y_{p}+2)+B*dx$

$= F(x_{p}-1/2,y_{p}+1)-dx$

$= J_{i}-dx$

如果选择的是 NE ，应判断：

$J_{i+1}=F(Mne) = F(x_{p}-3/2,y_{p}+2) = dy*(x_{p}-3/2)-dx*(y_{p}+2)+B*dx$

$= F(x_{p}-1/2,y_{p}+1)-dx-dy$

$= J_{i}-dx-dy$

因为第一个像素是端点
$(x_{0},y_{0})$
，可直接计算 J 的初始值
$J_{start}$
，以此决定是选 E 还是选 NE。

第一个中点在
$(x_{0}-1/2 , y_{0}+1)$
处，有

$J_{start}= F(x_{0}-1/2,y_{0}+1) = dy*(x_{0}-1/2)-dx*(y_{0}+1)+B*dx$

$= dy*x_{0} -1/2*dy-dx*y_{0}-dx+B*dx$

$= F(x_{0},y_{0})-dx -1/2*dy$

由于
$(x_{0},y_{0})$
落在线上，因此
$F(x_{0},y_{0})=0$
，故
$J_{start}$
值为
$-dx-1/2*dy$
.

核心代码：

（在实现中，为消除分数部分，将 F 乘以 2 重新定义 F，使每个常量和判断变量均乘以 2 ，但这并不影响判断变量
$J_{i}$
的符号，因此仍可作为中点检测标准。）

from PySide2.QtCore import *
class Line:
    def __init__(self, p):
        self.p = p
    def points_list_mid(self):
        points = []


        if self.p[0].y() == self.p[1].y():
            if self.p[0].x() > self.p[1].x():
                self.p.reverse()
            x = self.p[0].x()
            y = self.p[0].y()

            while x < self.p[1].x():
                points.append(QPoint(x, y))
                x = x+1
            return points

        if self.p[0].x() == self.p[1].x():
            if self.p[0].y() > self.p[1].y():
                self.p.reverse()
            x = self.p[0].x()
            y = self.p[0].y()
            while y < self.p[1].y():
                points.append(QPoint(x, y))
                y = y+1
            return points

        m = (self.p[1].y()-self.p[0].y())/(self.p[1].x()-self.p[0].x())
        if m > 0 and m <= 1:
            if self.p[0].x() > self.p[1].x():
                self.p.reverse()
            dx = self.p[1].x() - self.p[0].x()
            dy = self.p[1].y() - self.p[0].y()
            d = dx - 2*dy
            dNE = 2*dx - 2*dy
            dE = -2*dy
            x = self.p[0].x()
            y = self.p[0].y()
            while x < self.p[1].x():
                points.append(QPoint(x, y))
                if d < 0:
                    d = d + dNE
                    y = y + 1
                else:
                    d = d + dE
                x = x+1
        elif m >= -1 and m < 0:
            if self.p[0].x() > self.p[1].x():
                self.p.reverse()
            dx = self.p[1].x() - self.p[0].x()
            dy = self.p[1].y() - self.p[0].y()
            d = -dx - 2*dy
            dNE = -2*dx - 2*dy
            dE = -2*dy
            x = self.p[0].x()
            y = self.p[0].y()
            while x < self.p[1].x():
                points.append(QPoint(x, y))
                if d >= 0:
                    d = d + dNE
                    y = y - 1
                else:
                    d = d + dE
                x = x+1
        elif m > 1:
            if self.p[0].y() > self.p[1].y():
                self.p.reverse()
            dx = self.p[1].x() - self.p[0].x()
            dy = self.p[1].y() - self.p[0].y()
            d = dy - 2*dx
            dNE = 2*dy - 2*dx
            dE = -2*dx
            x = self.p[0].x()
            y = self.p[0].y()
            while y < self.p[1].y():
                points.append(QPoint(x, y))
                if d <= 0:
                    d = d + dNE
                    x = x + 1
                else:
                    d = d + dE
                y = y+1
        else:
            if self.p[0].y() > self.p[1].y():
                self.p.reverse()
            dx = self.p[1].x() - self.p[0].x()
            dy = self.p[1].y() - self.p[0].y()
            d = -dy - 2*dx
            dNE = -2*dy - 2*dx
            dE = -2*dx
            x = self.p[0].x()
            y = self.p[0].y()
            while y < self.p[1].y():
                points.append(QPoint(x, y))
                if d >= 0:
                    d = d + dNE
                    x = x - 1
                else:
                    d = d + dE
                y = y + 1

        return points

加上UI界面实现效果：

PS: 如需参考完整代码，请移步：

https://download.csdn.net/download/qq_42185999/11834675

进行下载

原文链接：https://blog.csdn.net/qq_42185999/article/details/102373104