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

被引：14

作者：

郭雷

王洵

王晓蒲

机构：

[1] 中国科学技术大学天文与应用物理系,中国科学技术大学计算机科学与技术系,中国科学技术大学天文与应用物理系合肥,合肥,合肥

来源：

计算机工程与应用 | 2002年 / 19期

关键词：

计算机图形学; 简单多边形; 内外点判别;

D O I：

暂无

中图分类号：

TP391.4 [模式识别与装置];

学科分类号：

081102 [检测技术与自动化装置];

摘要：

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

引用

页码：119 / 122

页数：4