基于二分法的凸多边形内外点判别算法

• 作者: 于凯 俞孟蕻
• 来源期刊: 电子设计工程
• 学科: 工学
• 关键词: 凸多边形 二分法 包含测试 递归分割
• 年，卷（期）: 2016,（16）
• 所属期刊栏目: 图像与多媒体
• 页码范围: 187-190
• 页数: 4页
• 分类号: TN0
• 字数: 3752字
• 语种: 中文

摘要

多边形内外点判定算法是图形学的基础型算法，目的是判定待测点是否在指定的多边形之内。由于传统的射线法与角度和法效率偏低，平均时间复杂度为O（n），当多边形边数或者待测点个数较多时，算法耗时较高。因此本文分析了传统的射线法与角度和法的缺点；提出了基于二分法的凸多边形内外点判别算法；最后进行实验仿真，证明该算法的平均时间复杂度为O（n/2）。该算法通过递归的分割凸多边形，判断待测点与分割线的相对位置，最终转化为三角形内外点的判别，具有快速、稳定、准确的优势。

作者信息

序号	姓名	单位	发文数	被引次数	H指数	G指数
1	俞孟蕻	江苏科技大学计算机科学与工程学院	66	242	9.0	12.0
2	于凯	江苏科技大学计算机科学与工程学院	1	1	1.0	1.0