【OpenCV】图形生成算法：多边形的扫描转换
昨天被人问到“扫描线算法”，只有个模糊的印象，好多都想不起来了。。。复习一下
多边形扫描线算法是针对计算机中多边形的显示。多边形三条或三条以上的线段首位顺次连接所组成的封闭图形，有凸多边形（任意两顶点间的连线均在多边形内）和凹多边形（任意两顶点间的连线有不在多边形内的部分）。
多边形在计算机中有顶点表示和点阵表示两种。
顶点表示就是用多边形的顶点序列来表示多边形。点阵表示是用位于多边形内的象素集合来表示多边形。顶点表示占内存少，几何意义强，易于进行几何变换；而点阵表示丢失了许多几何信息（如边界、顶点）。但光栅显示图形需要点阵表示形式。
多边形的扫描转换就是把多边形的顶点表示转换为点阵表示。
按扫描线顺序，计算扫描线与多边形的相交区间，再用要求的颜色填充这些区间的象素。步骤如下：
求交：计算扫描线与多边形各边的交点；
排序：把所有交点按x值递增顺序排序；
配对：第一个与第二个，第三个与第四个等等；每对交点代表扫描线与多边形的一个相交区间，
着色：把相交区间内的象素置成多边形颜色，把相交区间外的象素置成背景色。
其实很好理解，像下面的图：
以倒数第三条扫描线为例，有6个交点，排序之后为 A，B，C，D，E，F
然后配对：（A,B）（C,D）（E,F）也就是要填充（A,B）（C,D）（E,F）之间的部分。
这是扫描线与一条边相交，会出现问题的地方时扫描线与两条边相交，也就是与顶点相交。比如ABCD上面那条线，如果把顶点处看做一个交点，如图，配对的结果是：（G,H）（I,J）于是（H,I）之间的部分就会被填充为背景；如果吧H看做两个交点，H1,H2。配对结果：(G,H1)（H2,I）。。。把I被看成两个交点也是不科学的，正确的应该是把H看做0个交点，I看做两个。
总结说来，就是判断共享顶点的两个边：
如果共享顶点的两条边分别落在扫描线的两边，交点只算一个；
如果共享顶点的两条边在扫描线的同一边，这时交点作为零个或两个：另外两边都在下面看成0个，都在上面看成2个。
具体实现时，只需检查顶点的两条边的另外两个端点的y值。按这两个y值中大于交点y值的个数是0,1,2来决定。
还是上图GHI那条线，应看做G，I1，I2，J。配对结果：（G,I1）（I2,J）。
上图所有有交点的地方：
如果G的交点坐标是x1，假设A是下一条扫描线的交点，则交点就是x1+1/m。即：x(i+1)=x(i)+1/m。
这种性质在遇到顶点的时候会有一些改变，可以通过边的相关性总结规律。简单描述为扫描线上相邻像素的点在多边形内还是多边形外，内，外的关系在遇到顶点时会发生改变。还是上面那张图：
边相关的填充算法描述有点复杂，要维护两张表。回头再重写一章吧。
OpenCV中的函数
OpenCV中用 fillPoly() 函数绘制多边形。在core module的部分有所有的基本绘图函数：
直线 line()、圆circle()、椭圆ellipse()、矩形rectangle()、填充多边形fillPoly()
在安装目录的 OpenCV2.3.1\samples\cpp\tutorial_code\CxCore\Matrix 的文件夹下有名为 Drawing_1.cpp 的文件，有所有绘图的演示。填充多边形使用如下：
