【计算机图形学】直线的两种生成算法（DDA算法、Bresenham算法）

首先设待画直线的起点和终点坐标分别为 ( x 1 , y 1 ) , ( x 2 , y 2 ) (x_1,y_1), (x_2,y_2) (x1​,y1​),(x2​,y2​)，则根据起点和中点坐标可以得到该直线的斜率为 k = y 2 − y 1 x 2 − x 1 k=\frac{y_2-y_1}{x_2-x_1} k=x2​−x1​y2​−y1​​。我们知道直线方程可以用 F ( x , y ) = a x + b y + c F(x, y)=ax+by+c F(x,y)=ax+by+c 的形式来表达，此时该直线的斜率 k = − a b k=-\frac{a}{b} k=−ba​，那也就是说我们可以直接令 a = y 1 − y 2 , b = x 2 − x 1 a=y_1-y_2, b=x_2-x_1 a=y1​−y2​,b=x2​−x1​（只要满足商为 − k -k −k 即可）。 此时 F ( x , y ) = x ( y 1 − y 2 ) + y ( x 2 − x 1 ) + c F(x,y)=x(y_1-y_2)+y(x_2-x_1)+c F(x,y)=x(y1​−y2​)+y(x2​−x1​)+c，我们再随意带一个点进去（比如 ( x 1 , y 1 ) (x_1, y_1) (x1​,y1​)），便可求得 c = x 1 y 2 − x 2 y 1 c=x_1y_2-x_2y_1 c=x1​y2​−x2​y1​ ，即得到该直线的方程为： { F ( x , y ) = a x + b y + c = 0 a = y 1 − y 2 b = x 2 − x 1 c = x 1 y 2 − x 2 y 1 \begin{cases} F(x,y)=ax+by+c=0 \\ a=y_1-y_2 \\ b=x_2-x_1 \\ c=x_1y_2-x_2y_1 \end{cases} ⎩ ⎨ ⎧​F(x,y)=ax+by+c=0a=y1​−y2​b=x2​−x1​c=x1​y2​−x2​y1​​

对于某个点 ( x , y ) (x,y) (x,y)，我们要知道其与直线方程 F ( x , y ) F(x,y) F(x,y) 存在如下关系： { F ( x , y ) = 0 ， 在直线上 F ( x , y ) > 0 ， 在直线上方 F ( x , y ) < 0 ， 在直线下方 \begin{cases} F(x,y)=0，& 在直线上 \\ F(x,y)>0，& 在直线上方 \\ F(x,y)0，F(x,y) 0 （表示 M 在直线上方） 取 P 2 为下一像素点， d < 0 （表示 M 在直线下方） \begin{cases} 取 P_1 和 P_2 均可（此处取 P_1），& d=0 \\ 取 P_1为下一像素点，& d>0（表示 M 在直线上方） \\ 取 P_2为下一像素点，& d0（表示M在直线上方）d