《多边形的填充——扫描线算法(原理)》由会员分享，可在线阅读，更多相关《多边形的填充——扫描线算法(原理)（2页珍藏版）》请在金锄头文库上搜索。
1、多边形的填充扫描线算法(原理) 2007 年 10 月 05 日 星期五 11:52多边形在计算机中有两种表示：点阵表示和顶点表示。顶点表示是 用多边形的顶点的序列来描述多边形，该表示几何意义强、占内存少，但它不 能直观地说明哪些像素在多边形内。点阵表示是用位于多边形内的象素的集合 来刻划多边形，该方法虽然没有多边形的几何信息，但具有面着色所需要的图 像表示形式。多边形填充就是把多边形的顶点表示转换为点阵表示，即从多边形的 给定边界出发，求出位于其内部的各个像素，并将帧缓冲器内的各个对应元素 设置为相应的灰度或颜色。多边形填充最常用的方法就是扫描线算法。下面分 两篇文章介绍这种算法的原理和具体
2、实现。这里所介绍的算法只是针对非自交多边形，这些多边形可以是凸的、 凹的或者带有空洞的。所谓扫描线算法就是找到多边形的最小 y 值和最大 y 值，然后用这个 范围内的每一条水平线与多边形相交，求得交点，再绘制线段。所以我们只需 要对一条水平线进行分析就可以。很显然，一条扫描线和多边形有偶数个交点， 将这些交点按照 x 值从小到大排列，然后取第 1、2 个绘制，第 3、4 个绘制. .直到所有交点都被取完。所以，对于一条扫描线，我们需要做的工作可以 分为三个步骤：1)求出扫描线与多边形边的交点 2)将交点按照 x 升序排列 3) 将排好序的交点两两配对，然后绘制相应线段。这三个步骤中，后两个步骤
3、很简单，没有特别的内容需要介绍。但是 第一个步骤比较麻烦。这里有几个问题需要解决。 一是当扫描线与顶点相交时，交点的取舍。当与那个顶点关联的边在扫描线同 侧时，交点自然算两次，当与那个顶点关联的边在扫描线两侧时，交点只能算 一次。我们使用“下闭上开”的办法。二是多边形边界上的像素取舍，我们采用“左闭右开”的办法。三是如何减少计算量。在绘制直线时，有一种 DDA 算法，它是利用(x,y)直接求 出下一个点位于(x+1,y+m)或者(x+1/m, y+1)。在这里可以利用这一点。当已经 得到 y = e 和多边形所有边的交点时，对于下一条扫描线 y=e+1，如果没有新边 与 y=e+1 相交，就可
4、以推出 y = e+1 和多边形所有边的交点。四是如何计算第一条扫描线与多边形各个边的交点以及扫描线与新的边相交时 的交点。可以把多边形所有边放入一个表中，对于每一条扫描线，就遍历这个 表，求得交点。但是很多情况下，一条扫描线仅与少数几条边有交点，如果每 次都遍历所有边，效率就会很低。所以我们仅对与该扫描线相交的边进行求交。 这些与当前扫描线相交的边我们称之为“活性边”，把它们放入一个“活性边 表”AEL 中，这样每次遍历 AEL 就可以了。AEL 中每一个结点都是一个边，它保 存对应边的信息，比如扫描线与该边的交点，该边的两个顶点坐标(未必是四个坐标值，有可能是其他唯一确定一条边的等价信息)
5、。五是如何构造这个 AEL 表。上面说 AEL 中存放与当前扫描线相交的各个边，但 是怎么知道所有边中哪一些和当前扫描线相交呢？显然，当前扫描线位于某条 边最小 y 值和最大 y 值之间时，扫描线和那条边有交点。所以可以这样解决： 建立一个边的分类表 ET，将所有边按照其最小 y 值分类，放在表中对应位置， 然后每一条边又包含有自己的最大 y 值，这样就可以知道是不是与扫描线有交 点了。对于每一条扫描线，都先判断是否有新的边需要加入到 AEL 中，是不是 有旧的边需要从 AEL 中删除。然后再遍历 AEL 求交点。总结一下，求扫描线算法步骤如下：建立 ET对于每一条扫描线如果有新边就向 AEL 中插入新边从 AEL 中删除最大 y 值小于等于该扫描线的边遍历 AEL 获取交点，并将交点排序更新 AEL 中各个边的 x 值，将其作为下一条扫描线与该边的 交点将交点两两配对，绘制线段对于这一程序的实现，将在下一篇文章中给出。
