基于顶点与邻边相关性的多边形填充算法

• 作者: 吴良 谭建荣 陆国栋 马辉
• 来源期刊: 中国图象图形学报
• 学科: 工学
• 关键词: 多边形 填充 顶点与邻边相关性
• 年，卷（期）: 2004,（11）
• 所属期刊栏目: 学术论文与技术报告
• 页码范围: 1336-1341
• 页数: 6页
• 分类号: TP391.41
• 字数: 3806字
• 语种: 中文
• DOI: 10.3969/j.issn.1006-8961.2004.11.012

摘要

为了加快多边形填充算法的运算速度,在深入挖掘顶点与相邻边关系对填充算法影响的基础上,提出了一种基于顶点与邻边相关性的多边形填充算法.该算法首先归纳了多边形顶点与邻边相关性的5种典型类型,然后依据顶点与邻边的相关性,对原有多边形进行了分割与重新组合,使其完全由简单的三角形和梯形这样的单元区域组成,这样就将复杂的多边形填充问题转化为这些单元区域的填充问题,并由此将扫描线与多边形边求交的乘除计算转化为加减运算.通过实验分析,新算法大大减少了运算的时间和复杂度,从而为多边形填充创造了一种有效的新途径.