有向回路法和网格法:多边形内外点判别的新算法

• 作者: 王晓蒲 王洵 郭雷
• 来源期刊: 计算机工程与应用
• 学科: 工学
• 关键词: 计算机图形学 简单多边形 内外点判别
• 年，卷（期）: 2002,（19）
• 所属期刊栏目: 学术探讨
• 页码范围: 119-122
• 页数: 4页
• 分类号: TP391
• 字数: 4341字
• 语种: 中文
• DOI: 10.3321/j.issn:1002-8331.2002.19.042

摘要

该文把简单多边形视作一个有向回路,利用多边形的环绕方向和区域划分提出了两种判别内外点的新算法:有向回路法和网格法.有向回路法利用了多边形的方向性,在某些情况下可以不必遍历多边形的所有边.该算法程序简单,时间复杂度为O(n),平均性能优于复杂度为 (n)的射线法和标号法,但只能处理凸多边形.网格法是有向回路法的改进算法,利用了多边形的方向性和区域划分.网格法将n边形的包围盒划分为(n-1)×(n-1)个网格:如果待处理的点在某个网格内,则仅根据经过该网格的所有边就可以判断该点的内外性.网格法可以处理任意简单多边形,包括带孔的多边形;最坏情况下的时间复杂度为O(Ign),空间复杂度为 (n2).

作者信息

序号	姓名	单位	发文数	被引次数	H指数	G指数
1	王晓蒲	中国科学技术大学天文与应用物理系	52	1034	17.0	31.0
2	王洵	中国科学技术大学计算机科学与技术系	29	344	9.0	18.0
3	郭雷	中国科学技术大学天文与应用物理系	27	334	11.0	18.0