多边形扫描转换 多边形表示法 1.顶点表示法 用多边形的顶点序列表示多边形。这种表示直挂，几何意义强，占内存少，易于进行几何变换，但不能直接用于面着色 2.点阵表示法 1.X-扫描线算法 计算扫描线与多边形的相交区间，再用要求的颜色显示这些区间的像素，完成填充工作。 步骤： 1) 确定多边形占有的最大扫描线数，得到多边形顶点的最大和最小Y值 $y_{min}$ $y_{max}$ 2) 从$y_{min}$到$y_{max}$每次用一条扫描线进行填充 3) 每一条扫描线填充 a.求交：计算扫描线与多边形各边的交点 b.排序：把所有交点按递增排序进行排序 c.交点配对 ： （1）如果共享顶点的两条边方便落在扫描线的两边，那只算一个 （2）如果共享顶点的两条边方便落在扫描线的一边，那算2个或零个 d.区域填充
2.X-扫描线算法改进 1.使用增量 2.考虑扫描线的连贯性。 即当扫描线与各边的交点与下一条扫描线与各边的交点顺序很可能相同或相似。 活性边表(AET)：把与当前扫描线相加的边位活性边，并把它们按与扫描线交点x坐标递增的顺序存放在一个链表中。 链表节点内容： \(\documentclass{article} \begin{document} \begin{tabular}{|c|c|} \hline (1,1)&(1,2)\\ \hline (2,1)&(2,2)\\ \hline \end{tabular} \end{document}\) x: 当前扫描线与边的交点坐标。 $\Delta x$:从当前扫描线到下一条扫描线间x的增量 $y_{max}$： 改边所交的最高扫描线的坐标值$y_{max}$
设扫描线i与多边形的一个边交点位$(x_i,y_i)$ 与i+1的交点为$(x_{i+1},y_{i+1})$ 这条边的斜率为k
\[k=\frac{\Delta y}{\Delta x} =\frac{ y_{i+1}-y_i}{x_{i+1}-x_i}\]由于是扫描线所以 y的增量是1 可以得到
\[x_{i+1} - x_i=\frac{1}{k}\]\(x_{i+1} = x_i+\frac{1}{k}\) 即 \(\Delta x = \frac{1}{k}\) 这样AET链表中就存放 x,$\frac{1}{k}$,$y_{max}$->