基于拓扑映射的点集在凸多边形内外判断算法

• 作者: 李基拓 温星 陆国栋
• 来源期刊: 中国图象图形学报A辑
• 学科: 工学
• 关键词: 计算机图形学(520@6030) 点 点集 多边形 拓扑映射 映射点 射影直线
• 年，卷（期）: 2003,（4）
• 所属期刊栏目: 学术论文与技术报告
• 页码范围: 468-471
• 页数: 4页
• 分类号: TP391.72
• 字数: 2497字
• 语种: 中文
• DOI: 10.3969/j.issn.1006-8961.2003.04.019

摘要

通过拓扑映射,点在凸多边形内外的判别可以转化为映射点在射影直线上的位置关系问题.首先通过设置中心点,获取凸多边形各顶点的拓扑映射点,对于每个检测点,根据其映射点与顶点拓扑映射点的相对位置关系,即可确定检测点位于多边形哪条边的范围内;然后将检测点与该边进行包围盒测试,对于点在边包围盒外的情况,只需根据比较判别即可得到结果,对于点在边包围盒边界上或内部的情况,则需通过叉积运算进行判别.该方法几何意义清晰,实验结果表明,该算法运行可靠,对于单个点或多点组成的点集均有较高的检测速度.