admin 管理员组文章数量: 887042
X
多边形的扫描转换
多边形有两种重要的表示方法：顶点表示和点阵表示
顶点表示是用多边形的顶点序列来表示多边形。这种表示直观、几何意义强、占内存少，易于进行几何变换。
但由于它没有明确指出哪些象素在多边形内，故不能直接用于面着色
点阵表示是用位于多边形内的象素集合来刻画多边形。这种表示丢失了许多几何信息（如边界、顶点等），但它却是光栅显示系统显示时所需的表示形式。
光栅图形的一个基本问题是把多边形的顶点表示转换为点阵表示。这种转换称为多边形的扫描转换
X-扫描线算法
X-扫描线算法填充多边形的基本思想是按扫描线顺序，计算扫描线与多边形的相交区间，再用要求的颜色显示这些区间的像素，即完成填充工作
算法的核心是按X递增顺序排列交点的X坐标序列。由此，可得到X-扫描线算法步骤如下：
（1）确定多边形所占有的最大扫描线数，得到多边形顶点的最小和最大y值（ymin和ymax）
（2）从y = ymin到y = ymax，每次用一条扫描线进行填充
(3) 对一条扫描线填充的过 程可分为四个步骤：
a、求交：计算扫描线与多边形各边的交点
b、排序：把所有交点按递增顺序进行排序
c、交点配对：第一个与第二个，第三个与第四个
d、区间填色：把这些相交区间内的像素置成不同于背景色的填充色
当扫描线与多边形顶点相交时，交点的取舍问题（交点的个数应保证为偶数个）
（1）若共享顶点的两条边分别落在扫描线的两边，交点只算一个
（2）若共享顶点的两条边在扫描线的同一边，这时交点作为零个或两个
检查共享顶点的两条边的另外两个端点的y值，按这两 个y值中大于交点y值的个数来决定交点数
存在的问题
为了计算每条扫描线与多边形各边的交点，最简单的方法是把多边形的所有边放在一个表中。在处理每条扫描线时，按顺序从表中取出所有的边，分别与扫描线求交
这个算法效率低，为什么？
关键问题是求交！
而求交是很可怕的，求交的计算量是非常大的
转载于:.html
本文标签： x
版权声明：本文标题：X 内容由网友自发贡献，该文观点仅代表作者本人， 转载请联系作者并注明出处：http://www.freenas.com.cn/jishu/1686955696h50557.html， 本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌抄袭侵权/违法违规的内容，一经查实，本站将立刻删除。
发表评论