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

摘要：

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

关键词：多边形、填充、顶点与邻边相关性

所属期刊栏目：9

分类号：TP391.41(计算技术、计算机技术)

资助基金：国家创新研究群体科学基金60021201;高等学校博士学科点专项科研项目20020335093

在线出版日期：2005-02-24（万方平台首次上网日期，不代表论文的发表时间）

页数：共6页

页码：1336-1341