判断点与简单多边形位置关系的新算法

摘要：

基于射线法提出了一种新的判断点与简单多边形位置关系的算法.该算法是通过查找简单多边形所有顶点在确定区域内中斜率最小点,以此点确定一条射线,使得这条射线不穿过简单多边形的顶点.此算法不但保持了原来射线法相对其它方法有容易理解、计算简单等优势,并在此基础上排除了射线法中特殊的射线与简单多边形的顶点相交或射线过简单多边形边的特殊情况,大大地降低了算法的时间复杂度,提高了检测速度.

关键词：点、简单多边形、射线、算法、斜率

所属期刊栏目：45

分类号：O24(计算数学)

资助基金：国家自然科学基金the National Natural Science Foundation of China under Grant 10571037;黑龙江省教育厅资助项目the Edu-cation-Funded Projects of Heilongjiang Province,China under Grant 11511027

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

页数：共3页

页码：185-186,196