受限区域内的单纯型连续近邻链查询方法  

Simple continuous near neighbor chain query in constrained regions

作　　者：张丽平[1] 李松[1] 赵纪桥 郝晓红[2] 

机构地区：[1]哈尔滨理工大学计算机科学与技术学院,哈尔滨150080 [2]哈尔滨理工大学计算中心,哈尔滨150080

出　　处：《计算机应用》2014年第2期406-410,共5页journal of Computer Applications

基　　金：黑龙江省教育厅科学技术研究项目(12531120)

摘　　要：由于已有的最近邻查询方法无法直接处理受限区域内的单纯型连续近邻链查询问题,针对受限区域和障碍物的复杂性,详细研究了受限区域内无障碍物和有障碍物环境下的单纯型连续近邻链查询方法,分别提出了VOR_NB_CRSCNNC算法和VOR_CB_CRSCNNC算法。算法基于计算几何中的Voronoi图和判定圆域对空间数据对象进行预先筛选和计算,每次查询仅需考虑落在数量较少的Voronoi多边形和判定圆域内的数据点,预先过滤掉大量数据,减少每次计算涉及的数据量。理论研究和实验分析表明,所提出的算法在查询过程中减少了数据逐一判断的冗余计算,受受限区域形状的影响较小,较大程度提高了查询效率。The exiting methods of the nearest neighbor query can not search the simple continuous near neighbor chain in the constrained regions. To remedy the deficiency of the existing work, according to the complexity of the constrained regions and the obstacles, the simple continuous near neighbor chain query with non obstacles and with obstacles were studied respectively. The VOR_NB_CRSCNNC algorithm and the VOR CB CRSCNNC algorithm were presented. The spatial data were filtered and computed based on the Voronoi diagram and the judging circles. The calculations of each query were reduced by only considering the points which lay in the Voronoi polygon and the juding circles. The theatrical study and the experimental results show that the redundant calculation is reduced and the query efficiency is less affected by the constrained regaons

关 键 词：空间数据库 VORONOI图 最近邻查询 单纯型连续近邻链 受限区域 

分 类 号：TP311.13[自动化与计算机技术—计算机软件与理论]