自从今年春天选修了计算机图形学课程，这朵乌云就在头顶盘旋不散。始终弄不明白计算机图形学到底在研究什么，所谓的Imaging、Modeling、Rendering和Animation各自又是什么意思。总觉得课上讲的实在太过抽象，实践的经历太少，到最后也不过是囫囵吞枣，不知其味。
我们如何在计算机程序中存储几何图形呢？比如多边形？最容易想到的方法就是保存多边形的顶点坐标。只要按顺序保存了多边形各个顶点的坐标，这个多边形就唯一确定了。另一方面，显示器是如何显示几何图形的呢？显示设备通常提供一个帧缓冲存储器（俗称显存），可以把它当做二维数组，该数组存储的值与屏幕上显示的每一像素的颜色一一对应。那么问题来了，如何把程序中的几何图形转换成显存中的几何图形？这就是扫描线算法的用途。
总结下来：扫描线算法把几何图形在计算机中的顶点表示法转换成点阵表示法。需要注意的是转换成点阵表示法后其实是对多边形进行了填充，而不是只有轮廓。
由于多边形千变万化，要想填充多边形内部的所有像素，需要找到一种合适的规则，能够沿着一个方向，一个像素不漏地把多边形内部填满，同时不污染多边形外部。于是我们发明了一条水平方向的扫描线，它从y=0开始，判断与多边形的交点，这些交点把扫描线分成了若干段，我们需要判断哪些段在多边形内部，哪些段在多边形外部，然后把内部的部分着色，完成后，令y=y+1，即扫描线上移一格，重复之前的操作，直到扫描线不再与多边形的任何部分相交。
举例说明，下图所示为多边形P1P2P3P4P5P6，而且同时画出了扫描线扫描过程中经过的四个位置y=1、y=2、y=6和y=7。
扫描线算法的难点在于如何判断扫描线被多边形分割后哪些部分在多边形内部，哪些部分在多边形外部。
让我们仔细观察上图，答案就在图中。对于未经过顶点的扫描线，如y=6，总是与多边形有偶数个交点，而且位于多边形内部的片段和位于多边形外部的片段交替存在。对于经过了顶点的扫描线，如y=1、y=2和y=7，与多边形的交点既可能是偶数，也可能是奇数。但是如果我们进一步划分，这些经过了顶点的扫描线有些经过了极值顶点，如y=1和y=7，它们的交点个数是奇数；而有些经过了非极值顶点，如y=2，它们的交点个数是偶数。这样的话，不如做一个特殊处理，把所有极值顶点当成两个点，就可以保证扫描线与多边形的交点总是偶数。
当然，把交点个数凑成偶数是有意义的，凑成偶数后就可以把这些交点从左到右两两配对，配对成功的两个点之间的像素全部着色。例如，上图的扫描线y=6与多边形的交点序列是ABCD，从左到右两两配对为AB和CD，然后将AB之间着色，CD之间着色。
基本思想就是这样，其实很容易理解。不过用代码实现起来并不那么容易，需要考虑很多细节。
首先需要提醒的是，扫描线算法的基本思想很简单，但不同的实现方式会有很大的效率差异。因此，如何设计数据结构及算法才能使扫描线算法以最快的速度完成，才是接下来我们需要面对的问题。
从以下几个方面考虑：
问题1：如何计算当前扫描线与多边形的交点？
直观做法：根据多边形的顶点求出各个边的方程，然后将扫描线的纵坐标代入方程求出横坐标，搞定！
遗憾的是，这需要对每条扫描线遍历所有边，性能肯定是吃不消的。我们需要寻找一种只遍历一次边的方法。同时，使用方程求交点会用到乘法或除法运算，对性能也是一种伤害。因此，我们提出了下面两个数据结构。
下面的代码定义了边表和活动边表。
//定义用于边表ET和活动边表AET的通用类EdgeclassEdge{public:intymax;floatx;floatdx;Edge*next;};//边表Edge*ET[windowHeight];//活动边表Edge*AET;利用这两个数据结构就很容易计算出每条扫描线与多边形的交点了。我们只需要令扫描线从下往上扫描，已知每条边的下端点x坐标和x，就可以使用增量法计算出这条边上所有点的x坐标。具体方法放到后面叙述。
问题2：如何解决前面提到的极值顶点按照两个处理的问题？
如果两条边相交，它们的交点就是一个顶点。事实上，这个点本来就是按照两个点处理的，因为它分别属于两条边。那么这个问题其实应该转换成：如何把非极值顶点按照一个处理？解决办法是把顶点处从上面断开，如下图所示。缺口在y坐标上的长度是1个像素，所以并不会产生不利影响。
在后面的代码实现中，我们会在建立边表ET时判断非极值顶点并对其做特殊处理，请稍加注意。
问题3：如何快速配对交点并着色？
活动边表AET中存储了所有与当前扫描线相交的边及其交点坐标。配对的工作就自然变得很简单，只需要遍历一遍AET即可。
解决了这三个问题，我们就可以给出下面的算法流程：
依照该流程，我在Linux下使用c++实现了这个算法。由于无法真正实现向帧缓冲存储器填色，因此代码中使用了OpenGL，但仅使用它画点。
完整代码如下。
这是一个Linux下的CMake工程，请首先安装依赖库
sudoaptinstallcmakesudoaptinstallfreeglut3-dev然后进入工程目录（将下面的
cd
扫描线算法是多边形扫描转换中的常用算法，它的特点是效率高，但算法较为复杂。本文给出了一个简单的扫描线算法，只是用作简单的示例。而对于实际情况，由于多边形的复杂性，比如自交多边形，即两条边具有顶点之外的交点，这种多边形无法使用扫描线算法，可能需要先拆分成若干个非自交多边形之后再处理。而且，简单的扫描线算法效果并不理想，从上面给出的三张效果图可以看出，边的锯齿状很严重，需要额外进行抗锯齿处理。
最后，由于作者本人也不是计算机图形学专业，文中不免有错误之处，请大家及时指出。