一、 中点画线算法与 Bresenham 画线算法#

1. 【中点画线算法原理推导】 已知直线方程为 $F(x, y) = ax + by + c = 0$，其中 $a = y_0 - y_1$，$b = x_1 - x_0$。假定 $x$ 正向是最大位移方向（斜率在 $0 < k < 1$ 之间）。请完成以下推导：

(1) 简述中点画线算法的几何判别准则与算法基本思想。(2分)

(2) 设当前列已绘制像素点为 $(x_p, y_p)$，推导中点判别式递推公式，指出在决策变量 $d \ge 0$ 与 $d < 0$ 时，下一列决策变量 $d_{\text{next}}$ 的更新算式。(4分)

(3) 推导为消除浮点运算而经过整数双倍放大后的判别式初值 $d_0$ 公式，并给出下一个像素位置选择的决策依据。(4分)

2. 【Bresenham 画线算法原理推导】 已知直线起点为 $P_0(x_0, y_0)$，终点为 $P_1(x_1, y_1)$。假定 $x$ 正向是最大位移方向，且斜率满足 $0 < k < 1$。请完成以下推导：

(1) 简述 Bresenham 画线算法通过跟踪误差来逼近理想直线的算法基本思想。(2分)

(2) 设当前列决策变量为 $d_i$，推导下一列决策变量 $d_{i+1}$ 的误差判别递推公式。(4分)

(3) 说明如何通过消去分母与常数项，将算法改造为纯整数加减与移位运算，并给出整数型初值 $d_0$、决策更新增量以及下一步像素位置的选择依据。(4分)

3. 【直线上栅化计算（1,1 至 5,2）】 已知需要绘制从起点 $P_0(1, 1)$ 到终点 $P_1(5, 2)$ 的直线段。请分别使用中点画线算法和 Bresenham 算法进行光栅化离散点列计算：

(1) 采用中点画线算法（双倍放大形式），写出直线方程系数 $a, b$，计算决策变量初值 $d_0$，列出各步决策变量 $d$ 的值与选点结果坐标。(5分)

(2) 采用 Bresenham 算法（整数优化形式），写出误差决策变量初值 $d'_0$、增量项，并列表计算出各步的 $d$ 值判定与最终绘制的离散像素坐标点列 $(x,y)$。(5分)

4. 【直线上栅化计算（0,0 至 5,2）】 已知直线起点为 $P_0(0,0)$，终点为 $P_1(5,2)$。请分别使用中点画线算法和 Bresenham 算法进行光栅化离散点列计算：

(1) 采用中点画线算法（双倍放大形式），写出直线方程系数 $a, b$，计算决策变量初值 $d_0$，列出各步决策变量 $d$ 的值与选点结果坐标。(5分)

(2) 采用 Bresenham 算法（整数优化形式），写出误差项初值 $d'_0$，列出各步的 $d$ 值更新与绘制点坐标 $(x,y)$ 的完整递推计算过程表格。(5分)

---

二、 改进的活动边表填充算法#

5. 【改进的活动边表（AET）多边形填充】 已知某多边形的顶点坐标分别为：$A(2, 1)$、$B(6, 1)$、$C(6, 5)$、$D(4, 3)$、$E(2, 5)$、$F(1, 4)$。若采用多边形扫描转换的改进活动边表算法进行填充，且边表与活动边表的结点结构统一规定为：[y_max | x_ymin | 1/k | next]（其中 $y_{\max}$ 为边最大纵坐标，$x_{ymin}$ 为边最小纵坐标处的横坐标，$1/k$ 为边斜率的倒数）。请完成以下设计计算：

(1) 构建该多边形的完整边表（ET 表），标明每个扫描线链表的挂接边及其具体参数。(5分)

(2) 写出扫描线从下往上递增到 $y = 3$ 时的活动边表（AET 表）的各个结点参数状态（按 $x$ 值从小到大排序）。(3分)

(3) 写出扫描线 $y = 3$ 时的有效填充像素区间。(2分)

---

三、 Liang-Barsky 算法直线裁剪#

6. 【Liang-Barsky 直线段裁剪算法计算】 已知裁剪窗口为一个矩形区域，其边界值分别为：$x_{w\min} = 0$，$x_{w\max} = 2$，$y_{w\min} = 0$，$y_{w\max} = 2$。待裁剪直线段的起点坐标为 $A(1, -1)$，终点坐标为 $B(2, 3)$。请完成以下分析与计算：

(1) 写出 Liang-Barsky 算法的参数化线段表达式，并计算出直线段与四个裁剪边界对应的参数组 $p_k$ 与 $q_k \quad (k=1,2,3,4)$。(4分)

(2) 计算得出入点参数 $u_{\max}$ 与出点参数 $u_{\min}$，写出详细的边界相交类型判定过程。(4分)

(3) 根据 Liang-Barsky 算法的裁剪准则，判定该线段是否被接受，并求出窗口内部裁剪后的端点实际坐标值。(2分)