计算机图形学实验报告-多边形的转换与区域填充.doc

计算机科学与技术学院 2013－2014学年第一学期 《计算机图形学》实验报告 班级： 学号： 姓名： 教师： 成绩： 实验项目（2、多边形的扫描转换与区域填充） 实验目的与要求 了解多边形扫描转换的各种算法，掌握多边形的扫描转换与区域填充算法。 进一步掌握在VC集成环境中实现图形算法的方法与过程。 实验内容 设计菜单程序，利用消息处理函数，完成以下要求： 给出凸多边形的若干顶点（3 ~ 5个），实现多边形的“x扫描算法”。 实现种子填充，泛填充算法（四邻法）。 设计程序，实现判断一个点是否在多边形区域内部。 重要算法分析 边界表示的四连通区域种子填充算法 此方法的基本思想是，从多边形内部任一像素出发，按照“左上右下”的顺序判断相邻像素，若不是边界像素且没有被填充过，则对其填充，并且重复上述过程，直到所有像素填充完毕。 从种子点出发，向左判断多边形内部颜色，如果不是填充颜色并且不是边界颜色，则填充，直到遇到边界为止。 从种子点出发，向右判断多边形内部颜色，如果不是填充颜色并且不是边界颜色，则填充，直到遇到边界为止。 将种子点的坐标y值上移一个像素，重复步骤（1）、（2）直到遇到上面边界为止。 将种子点的坐标y值下移一个像素，重复步骤（1）、（2）直到遇到上面边界为止。 判断一个点是否在多边形内部 解决方案是将测试点的y坐标与多边形的每一个点进行比较，我们会得到一个测试点所在的行与多边形边的交点的列表。如果测试点的两边点的个数都是奇数个则该测试点在多边形内，否则在多边形外。 如图1所示，判断点（红点）y值左边与多边形有5个交点，右边与多边形有3个交点，则该点在多边形内部。 图1 如图2所示，判断点（红点）y值左边与多边形有2个交点，右边与多边形有2个交点，则该点在多边形外部。 图2 但是有一种特殊情况须特别处理一下，当与多边形顶点相交时，需要将改点计算为两个交点，如图3所示： 图3 程序运行截图 种子四连通域填充法，如图4所示。 图4 种子四连通域填充 判断一个点是否在多边形内部，如图5所示： 图 5 图5所示点在多边形内部，而图6所示点不在多边形内部，如图6所示： 图 6 总结与调试经验 通过这次实验，加深了对图形学的理解，尤其对种子填充算法有了更加深入的理解，但是中途也遇到了很多问题，比如四邻域算法不能解决狭窄区域的问题。 解决判断一个点是否在多边形内部的时候，最初的想法是从该点出发通过上下左右判断是否与多边形在四个方面有交点，如果有则在多边形内部，但是后来想到如果是三角形就不能够解决了，于是查阅了很多文献，解决这个的方法有很多种，最后选择了上文中的算法来实现。 通过实验，最大的体会感受到了这门课的乐趣，在乐趣中学习！