基于泰森多边形的数据区域索引与检索系统.docx

基于泰森多边形的数据区域索引与检索系统

2万字 73页 包括外文翻译，原创作品，通过查重系统


摘 要
荷兰气候学家AR26;HR26;Thiessen为解决用离散气象站降雨量计算平均降雨量提出了泰森多边形。泰森多边形因为其优良的特性应用在各个领域，其中最为普遍的是最近邻点的判断，在平面上所有站点的泰森多边形生成的情况下，不需要再计算比较目标查询点与各个站点之间的距离，可以直接判断目标查询点位于哪一个泰森多边形中，该泰森多边形对应的离散点即为目标查询点的最近邻点。
本文旨在研究考虑利用泰森多边形的空间划分特性，设计实现区间索引机制，主要工作包括：
（1）实现泰森多边形的图形化展示；
（2）考虑采用高效的算法实现平面上任意点最近邻的有效检索；
（3）计算平面内给定矩形区域所覆盖的泰森多边形。
通过上述工作得出以下结论：
（1）泰森多边形在区间索引上的应用是可行的，可以有效提高检索效率；
（2）在实现泰森多边形的过程中，利用一些优化算法可以降低时间复杂度，提高图形的生成效率，在最近邻查询方面也通过优化算法减小计算量提高了查询的效率。

关键词：Delaunay三角网;泰森多边形;最近邻;区域查询