作者投稿和查稿 主编审稿 专家审稿 编委审稿 远程编辑

计算机工程 ›› 2011, Vol. 37 ›› Issue (16): 30-32. doi: 10.3969/j.issn.1000-3428.2011.16.010

• 软件技术与数据库 • 上一篇    下一篇

基于Voronoi图的线段反向最近邻查询

杨泽雪 1,2,郝忠孝 1,3   

  1. (1. 哈尔滨理工大学计算机科学与技术学院,哈尔滨 150080;2. 黑龙江工程学院计算机科学与技术系,哈尔滨 150050;3. 哈尔滨工业大学计算机科学与技术学院,哈尔滨 150001)
  • 收稿日期:2010-12-10 出版日期:2011-08-20 发布日期:2011-08-20
  • 作者简介:杨泽雪(1978-),女,讲师、博士,主研方向:近邻查询算法,空间数据库;郝忠孝,教授、博士生导师
  • 基金资助:
    黑龙江省自然科学基金资助项目(F200601);教育部青年基金资助项目(10YJC870025)

Line Reverse Nearest Neighbor Query Based on Voronoi Diagram

YANG Ze-xue 1,2, HAO Zhong-xiao 1,3   

  1. (1. College of Computer Science and Technology, Harbin University of Science and Technology, Harbin 150080, China;2. Department of Computer Science and Technology, Heilongjiang Institute of Technology, Harbin 150050, China;3. College of Computer Science and Technology, Harbin Institute of Technology, Harbin 150001, China)
  • Received:2010-12-10 Online:2011-08-20 Published:2011-08-20

摘要: 提出一种基于平面线段的反向最近邻查询方法,用于找出线段集中以查询线段作为最近邻的线段。通过构造线段集的Voronoi图处理不相交的线段。根据其邻接特性和局部特性,给出基于Voronoi图的线段反向最近邻查询算法及相关定理和证明。实验结果表明,反向最近邻方法易于找到相交的线段,具有较高的查询效率。

关键词: 平面线段, Voronoi图, 线段反向最近邻, 空间数据库, 查询区域

Abstract: Reverse Nearest Neighbor(RNN) query between line is put forward. That is finding the line segments that have query line segment as one of their nearest neighbors. According to whether two line segments are intersected, it has two categories: intersected line segment and no intersected. For the former, the reverse nearest neighbor is easy to find. For the latter, by constructing the Voronoi diagram of line segment sets, using the adjacent property and the local property, the line segment RNN query based on Voronoi diagram algorithm is proposed, and the relevant theorem and proof are given. Experimental results demonstrate the proposed algorithms have high query efficiency.

Key words: plane line segment, Voronoi graph, Line Reverse Nearest Neighbor(LRNN), spatial database, query region

中图分类号: