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

摘要：

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

关键词：均匀条带划分法、射线法、点包含性测试、多边形、计算几何

所属期刊栏目：21

分类号：TN9;TM9

资助基金：863计划2009AA12Z226

在线出版日期：2012-01-14（万方平台首次上网日期，不代表论文的发表时间）

页数：共7页

页码：810-816