得鹿梦鱼 得鹿梦鱼
知识库 前端技能树 面试题 学习资料 关于本人

直线的生成算法_DDA

DDA是数字微分分析式（digital differential analyzer）的缩写

为了设计DDA算法，我们需要基本的线性方程来得到直线的斜率，并在此基础上进行进一步的计算。方程是基于斜率-截距形式的直线

y=kx+by = kx + b

设直线的起点为x1,y1x_1, y_1,终点为x2,y2x_2, y_2,则斜率为
k=y2−y1x2−x1=ΔyΔxk = \frac{y_2 - y_1}{x_2 - x_1} = \frac{\Delta y}{\Delta x}

直线中的每一个点坐标都可以是有前一个点坐标变换一个增量Δx,Δy\Delta x, \Delta y 而得到，即表示为递归式
xi+1=xi+Δxyi+1=yi+Δyx_{i + 1} = x_i + \Delta x \\y_{i + 1} = y_i + \Delta y

由于递归式的初值是直线的起点x1,y1x_1, y_1,这样就可以使用加法来生成一条直线，具体方法为： 按照直线从x1,y1x_1, y_1到x2,y2x_2, y_2的方向不同，分为8个象限，如下图

直线方向的8个象限

不考虑和坐标轴平行的场景

象限Δx\Delta xΔy\Delta y
1a象限Δx=1\Delta x = 1Δy=k\Delta y = k
1b象限Δx=1k\Delta x = \frac{1}{k}Δy=1\Delta y = 1
2a象限Δx=−1\Delta x = -1Δy=−k\Delta y = -k
2b象限Δx=1k\Delta x = \frac{1}{k}Δy=1\Delta y = 1
3a象限Δx=−1\Delta x = -1Δy=−k\Delta y = -k
3b象限Δx=−1k\Delta x = -\frac{1}{k}Δy=−1\Delta y = -1
4a象限Δx=1\Delta x = 1Δy=k\Delta y = k
4b象限Δx=−1k\Delta x = -\frac{1}{k}Δy=−1\Delta y = -1

由上表可知，

  1. 当∣x2−x1∣x_2 - x_1 > ∣y2−y1∣y_2 - y_1，自增量为1的方向在x轴，否则在y轴、
  2. 自增的符号与x2−x1x_2 - x_1， y2−y1y_2 - y_1的方向相同

使用DDA算法，每生成一条直线需要做两次触发，每画线中的一点做两次加法操作，因此，使用DDA生成的直线的速度是相当快的

算法步骤

  1. 初始化点位 给定两个端点表示起点和终点x1,y1x_1, y_1和x2,y2x_2, y_2
  2. 计算斜率∣k∣k,决定自增量的方向,由于需要得是∣k∣k与1得关系，因此可以比较Δx,Δy\Delta x,\Delta y得绝对值，只用加减法来实现算法
  3. 下一个点位位置计算，如果斜率k≤1k \leq 1x轴自增1， 否则y轴自增1
  4. 绘制点
  5. 重复3,4直到所有点位绘制完成

代码实现

请参考直线的生成算法_DDA

直线的生成算法_DDA
≡