基于平均条带划分的点的包含性测试方法

• 作者: 刘焱 廖浩均 方金云 朱效民
• 来源期刊: 高技术通讯
• 学科: 工学
• 关键词: 均匀条带划分法 射线法 点包含性测试 多边形 计算几何
• 年，卷（期）: 2011,（8）
• 所属期刊栏目: 计算机与通信技术
• 页码范围: 810-816
• 分类号: TP3
• 字数: 3932字
• 语种: 中文
• DOI: 10.3772/j.issn.1002-0470.2011.08.007

摘要

提出了一个大量点与多边形关系计算的方法.该方法首先对多边形进行简单预处理,然后采用射线法对每个点进行包含性测试.预处理将多边形的最小包围矩形划分为相同大小的竖直条带,并计算每条边在哪些条带中,该预处理过程简单快速.利用预处理信息对点进行包含性测试时,只需用当前点构造的射线和点所在的条带包含的边进行相交测试即可.每个条带内包含的边的数目是有限的,常常接近一个常数,远远小于多边形的边数,因此相交测试计算次数显著减少,从而可以快速求得点与多边形的关系.该方法已经实现,并用人造数据和真实地理数据进行测试,测试结果证明该方法正确有效.

作者信息

序号	姓名	单位	发文数	被引次数	H指数	G指数
1	方金云	中国科学院计算技术研究所	79	637	12.0	21.0
2	朱效民	中国科学院计算技术研究所	17	178	6.0	13.0
6	刘焱	中国科学院计算技术研究所	3	33	2.0	3.0
10	廖浩均	中国科学院计算技术研究所	3	37	3.0	3.0