基于链码和特征形的多边形内外点判断算法

摘要：

通过对多边形各个顶点与待测点相对位置进行判别,给出了多边形的垂直(水平)链码序列生成方法.该方法根据多边形的链码将原多边形中对判别无关的冗余边或冗余点删除,形成多边形的特征形;待测点在特征形与原多边形内外位置关系上具有一致性,从而大大简化了运算.同时给出了一种点在多边形内外点判断算法,把点在原多边形内外的判断转化为点与其特征形的位置判断,特征形的提取过程是一个线性扫描及条件判断过程,可以避免大量的叉积运算,从而有效地提高了多边形内外点判断算法的效率.程序验证表明:文中算法易于实现,具有运行速度快、稳定性高等优点.

关键词：图形学算法、多边形、内外点判断、垂直链码序列、水平链码序列、特征形

所属期刊栏目：18

分类号：TP3(计算技术、计算机技术)

资助基金：国家自然科学基金3479237418;高等学校博士学科点专项科研项目20040335060

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

页数：共5页

页码：1317-1321