基于斜率的多边形内外点快速判别算法

• 作者: 洪志强
• 来源期刊: 计算机与现代化
• 学科: 工学
• 关键词: 计算机图形 斜率 简单多边形 内外点判别
• 年，卷（期）: 2013,（1）
• 所属期刊栏目: 算法设计与分析
• 页码范围: 53-56,60
• 页数: 5页
• 分类号: TP301.6
• 字数: 2528字
• 语种: 中文
• DOI: 10.3969/j.issn.1006-2475.2013.01.015

摘要

多边形的内外点判别是图形学的一个基础算法,为了更大限度地降低其算法复杂度和运算量,提出一种基于斜率的点与多边形位置关系的快速判别法.该方法只需计算该点到多边形各顶点的斜率,然后与多边形各顶点的邻边的斜率进行比较,即可对多边形的内外点快速做出判别.该算法无需复杂的点乘、叉乘、求交、三角函数等运算,在判别过程中仅需平均2n次减法运算和n/2次的除法运算,以及一些比较运算,即可对简单n多边形的内外点做出判别.经测试,该算法快速有效.

作者信息

序号	姓名	单位	发文数	被引次数	H指数	G指数
1	洪志强	江苏科技大学计算机科学与工程学院	1	1	1.0	1.0