| 朱效民,刘焱,廖浩均,方金云.基于平均条带划分的点的包含性测试方法[J].高技术通讯(中文),2011,21(8): |
| 基于平均条带划分的点的包含性测试方法 |
| Point inclusion test based on averagely-divided stripes |
| |
| DOI： |
| 中文关键词: 均匀条带划分法;射线法;点包含性测试;多边形;计算几何 |
| 英文关键词: |
| 基金项目:863计划 |
| 朱效民,刘焱,廖浩均,方金云 |
1. 中国科学院计算技术研究所 北京100190;中国科学院研究生院 北京100049
2. 中国科学院计算技术研究所 北京100190 |
| 摘要点击次数: 2730 |
| 全文下载次数: 0 |
| 中文摘要: |
| 提出了一个大量点与多边形关系计算的方法.该方法首先对多边形进行简单预处理,然后采用射线法对每个点进行包含性测试.预处理将多边形的最小包围矩形划分为相同大小的竖直条带,并计算每条边在哪些条带中,该预处理过程简单快速.利用预处理信息对点进行包含性测试时,只需用当前点构造的射线和点所在的条带包含的边进行相交测试即可.每个条带内包含的边的数目是有限的,常常接近一个常数,远远小于多边形的边数,因此相交测试计算次数显著减少,从而可以快速求得点与多边形的关系.该方法已经实现,并用人造数据和真实地理数据进行测试,测试结果证明该方法正确有效. |
| 英文摘要: |
| |
|
查看全文
查看/发表评论 下载PDF阅读器 |
| 关闭 |
|
|
|
