基于凸剖分的点在多边形内的高效判定

• 作者: 吴恩华 李静 王文成
• 来源期刊: 自然科学进展
• 学科: 数学
• 关键词: 点 多边形 包容性检测 加速
• 年，卷（期）: 2007,（7）
• 所属期刊栏目: 研究简讯
• 页码范围: 995-1000
• 页数: 6页
• 分类号: O1
• 字数: 5406字
• 语种: 中文
• DOI: 10.3321/j.issn:1002-008X.2007.07.023

摘要

提出一种点在多边形内的快速判定算法.与这方面已知的最快算法相比,新方法在预处理时间、空间需求和判定计算等方面,均达到了相同的复杂度,且没有奇异情况,能运算更快,甚至快一倍多.其步骤是:将一个多边形剖分成一些凸多边形,并进行二叉树的组织管理;然后,判断一个点是否在该多边形内时,先根据二叉树找到最可能包含该点的凸多边形,再判断该点是否位于该凸多边形内,就可完成判定计算.

作者信息

序号	姓名	单位	发文数	被引次数	H指数	G指数
1	吴恩华	中国科学院软件研究所计算机科学国家重点实验室	114	2335	25.0	44.0
5	李静	中国科学院软件研究所计算机科学国家重点实验室	238	2528	23.0	40.0
9	王文成	中国科学院软件研究所计算机科学国家重点实验室	42	484	13.0	20.0