基于线性四叉树的快速邻域查询算法  

Fast neighbor-finding algorithm based on linear quadtree

作　　者：赵慧[1] 宋星[1] 

机构地区：[1]中国航天科工集团第二研究院706所,北京100854

出　　处：《计算机工程与设计》2007年第18期4333-4335,共3页Computer Engineering and Design

摘　　要：邻域查询是位置服务系统的核心技术,它的实现取决于空间对象数据模型。根据空间对象分布构建的四叉树模型,以及线性四叉树中位置码的使用,提出了一种新的基于线性四叉树的快速邻域查询算法。该算法根据满四叉树结点编码思想对线性四叉树的Morton码进行了改进,并增加了表示四叉树所有结点状态的序列,通过网格模型的邻域查询算法实现了线性四叉树的快速邻域查询。Neighbor-finding is a core technique of location-based service whose realization is decided by the data model of spatial objects. As geographic region is partitioned by the quadtree and location-code of linear quadtree is used to represent the location of spatial object in the sub-region, a new fast neighbor-finding algorithm based on linear quadtree is introduced. It refers to an optimized morton-code which is modified according to node-code of full quadtree, a status sequence recording the status of all quadtree nodes, and a neighbor- finding algorithm based on grid. All of these make the efficiency of neighbor-fmding high in linear quadtree.

关 键 词：位置服务系统 线性四叉树 邻域查询 Morton编码 结点状态序列 

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