障碍环境中线段组最近邻查询方法研究  

Group Nearest Neighbor Query Method of Line Segment in Obstacle Space

作　　者：郭莹莹[1] 张丽平[1] 李松[1] GUO Ying-ying;ZHANG Li-ping;LI Song(School of Computer Science and Technology,Harbin University of Science and Technolog)

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

出　　处：《计算机科学》2018年第6期172-175,192,共5页Computer Science

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

摘　　要：为了解决现有成果无法有效处理障碍环境下的线段组最近邻查询问题,提出了障碍环境中线段组最近邻查询方法。查询过程分为过滤阶段和精炼阶段两个部分。在过滤过程中,首先根据线段Voronoi图的性质以及线段障碍组最近邻查询的定义,提出了针对数据线段的剪枝定理,并提出了OLGNN_Line_Filter算法;根据线段障碍距离的定义,进一步提出针对障碍物的剪枝定理,并给出了OLGNN_Obstacle_Filter算法。在精炼过程中,为了得到更精确的查询结果,提出了相应的精炼定理和精炼算法STA_OLGNN。理论研究和实验表明,所提算法能够有效地处理障碍环境下的线段组最近邻查询问题。In order to make up the deficiencies of the existing research results which can not effectively deal with the group nearest neighbor query based on line segment in obstacle space,the group nearest neighbor query method of line segment in obstacle space was proposed.This query process is divided into two stages,including the filtering process and refining process.In the filtering process,according to the properties of the line segment Voronoi graph and the definition of OLGNN,corresponding pruning theorem of data line was proposed,and the OLGNN_Line_Filter algorithm was put forward.According to the definition of line obstruction distance,corresponding pruning theorem of obstruction was proposed,and the OLGNN_Obstacle_Filter algorithm was put forward.In the refining process,in order to get more accurate query results,the corresponding refining theorem and STA_OLGNN algorithm were proposed.Theoretical research and experimental results show that the proposed algorithm can effectively deal with the problem of group nearest neighbor query of line segment in obstacle environment.

关 键 词：空间数据库 线段障碍距离 线段障碍组最近邻 线段Voronoi图 

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