多边形光栅化
别名: 多边形扫描转换算法.
该部分算法用于将多边形的顶点表示转换为点阵表示, 该过程被称为多边形的"光栅化".
多边形可分为下面几类:
- 凸多边形: 任意两点间连线均在多边形内.
- 凹多边形: 任意两点间连线均有不在多边形内.
- 含内环的多边形: 多边形内包含多边形.
X-扫描线算法
以一条平行与光栅网格的扫描线, 逐步从多边形任意一个轴的最大值扫描到最小值. 求出所有与多边形线段相交的顶点, 进而得出扫描线与多边形相交的区间. 最后填充这些区间.
假设扫描线与x轴平行, 大致可分为一下几个步骤:
- 确定扫描范围: 多边形顶点y的最大值和y的最小值.
- 扫描.
a. 求交: 获取扫描线与多边形各边的交点.
b. 排序: 将这些交点按x坐标升序排列.
c. 配对: 第一个交点与第二个交点配对形成一个相交区间, 第三个交点和第四个交点配对形成一个相交区间, 以此类推.
d. 填色: 填充这些相交区间.
若扫描线与多边形顶点相交, 为确保顶点正常匹配, 需要保证顶点个数为偶数. 若共享顶点的两条边分别落在扫描线的两侧时, 算作一个交点; 两条边都位于扫描线上方时, 算作两个交点; 两条边都位于下方时, 算作零个顶点. 即共享顶点两条边位于扫描线上方的个数即为应该判定的交点个数.
Question
可不可以通过直线扫描转换算法计算出所有的点, 然后同一 y 坐标的点根据 x 坐标排序.